☰

パラメトリック多態性と高階型の違いは何ですか? 質問する

tag-icon • tag-icon haskell rust higher-kinded-types type-theory parametric-polymorphism
パラメトリック多態性と高階型の違いは何ですか? 質問する

これらは同じではないことは確かです。しかし、私は「Rustは高階型（HKT）をサポートしていない」という一般的な考えにとらわれています。代わりに、パラメトリック多態性私はそれを理解しようとし、これらの違いを理解しようとしましたが、ますます混乱していきました。

私の理解では、はRust の高階型、少なくとも基本。「*」表記法を使用すると、HKT には の種があります* -> *。たとえば、Maybeは の種であり* -> *、Haskell では次のように実装できます。

data Maybe a = Just a | Nothing

ここ、

  • Maybeは型コンストラクタであり、種類「*」の具体的な型になるためには具体的な型に適用する必要があります。
  • Just aこれらはNothingデータ コンストラクターです。

Haskellの教科書では、これは高階型の例によく使われます。しかし、Rustでは、これは単に列挙型として実装することができ、結局のところ、合計型:

enum Maybe<T> {
    Just(T),
    Nothing,
}

違いはどこにあるのでしょうか? 私の理解では、これは高次の型の完璧な例です。

  1. Haskell ではこれが HKT の教科書的な例として使用されているのに、なぜ Rust には HKT がないと言われるのでしょうか? enum はMaybeHKT として適格ではないのでしょうか?
  2. Rustは完全にHKTを応援しますか？
  3. HKT とパラメトリック多態性の根本的な違いは何ですか?

Maybeこの混乱は関数を見ると続きます。 、および私の理解では HKT を関数の引数として受け取るパラメトリック関数を記述できます。

fn do_something<T>(input: Maybe<T>) {
    // implementation
}

再びHaskellでは次のようになります

do_something :: Maybe a -> ()
do_something :: Maybe a -> ()
do_something _ = ()

これが4番目の質問につながります。

  1. 高階型のサポートはどこで終わるのでしょうか? Rust の型システムが HKT を表現できない最小限の例は何ですか?

関連する質問:

私はこのトピックに関連する多くの質問（ブログ投稿へのリンクなどを含む）を調べましたが、私の主な質問（1 と 2）に対する答えを見つけることができませんでした。

  1. Haskell では、「高次の型」は本当に型なのでしょうか? それとも、単に具体的な型のコレクションを示すだけで、それ以上のものではありませんか?
  2. 型パラメータのないジェネリック型上のジェネリック構造体
  3. Scala における高階型
  4. 「高次多態性」はどのような種類の問題をよりうまく解決するのに役立ちますか?
  5. Haskell における抽象データ型とパラメトリック多態性

アップデート

非常に詳細で非常に役立つ多くの良い回答をありがとうございました。Andreas Rossberg の説明が私を正しい方向に導くのに最も役立ったので、彼の回答を受け入れることにしました。特に用語に関する部分です。

私は本当に、すべての種類* -> * ... -> *は高等な* -> * -> *との違いを強調した説明は(* -> *) -> *私にとって非常に重要でした。

ベストアンサー1

いくつかの用語:

  • この種類*は、地面0次と考えることができます。
  • * -> * -> ... -> *少なくとも1つの矢印があるフォームは最初の注文。
  • あ高次の種類は「左側にネストされた矢印」を持つものです。例: (* -> *) -> *。

の注文本質的には、矢印の左側のネストの深さです。たとえば、(* -> *) -> *は 2 次、((* -> *) -> *) -> *は 3 次などです。(参考までに、同じ概念が型自体にも当てはまります。2 次関数とは、その型がたとえば という形式である関数です(A -> B) -> C。)

非基底種（次数>0）の型は型とも呼ばれる。コンストラクタ(一部の文献では、基底種の型のみを「型」と呼んでいます)。高階種型 (コンストラクタ) は、その種が高階 (次数 > 1) である型です。

したがって、高階型とは、非基底型の引数を取る型です。これには非基底型の型変数が必要ですが、これは多くの言語ではサポートされていません。Haskell の例:

type Ground = Int
type FirstOrder a = Maybe a  -- a is ground
type SecondOrder c = c Int   -- c is a first-order constructor
type ThirdOrder c = c Maybe  -- c is second-order

後者の 2 つはより高次のものです。

同じく、高次の多態性基礎とならない型を抽象化する (パラメータ的に) 多態的な値の存在を記述します。これも、サポートしている言語はほとんどありません。例:

f : forall c. c Int -> c Int  -- c is a constructor

Rust が高階型の代わりにパラメトリック多態性をサポートするという主張は意味をなさない。両者は互いに補完し合う異なる次元のパラメータ化である。そして両者を組み合わせると高階型多態性が得られる。

おすすめ記事