異なるタイプのものを含むようにリストを特別な方法で定義できますか?

https://cs.stackexchange.com/questions/129264

29-09-2020
|

質問

で https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf と書かれています

A型 $\タウ$ list は、次のタイプの要素を持つリストのタイプです。 $\タウ$

なぜリストには同じ型の要素が含まれなければならないのでしょうか?異なるタイプの要素を含めることができないのはなぜですか?型付きラムダ計算でリストを多態的に定義し、任意の型の要素を受け取るようにする方法はありますか?

それでは、多態的に定義されたリストに対して List モナドを使用できるでしょうか?

解決

短い回答は、 $ \ taw \ \ \ \ text {list} $ は、型コンストラクタとしての定義です。形成と排除、そして私たちは、異なるタイプの用語を許容するタイプのコンストラクタと同様にを定義することができ、単一の「可変型のリスト」を形成することができます。ただし、単に単一のタイプに関して定義されているため、リストは定義に異なるタイプを取り込むことはできません。どちらの場合でも、リストの追加、または変数型のリストには、 any $ \ lambda "> $ \ lambda"> $ \ lambda $ calculusの拡張が含まれます。 >種類は通常の発表には存在しません。

単純に入力された $ \ lambda $ -calculusよりもわずかに豊かなタイプのシステムがある場合は、標準 $ \ TAU \ \ text {list} $ s。

依存shum types （ $ \ sigma $ -types）とa ユニバースタイプ $ \ mathcal u $ （つまり、 "タイプのタイプ"）、type $を形成することができます（ \ sigma_ {a：\ mathcal u} a）\ \ text {list} $ 。その要素は、型 $ a $ とaのペアです。そのタイプの用語

最後に、多型が異種リストを望んでいる場合は私たちを助けることができないことに注意してください。 $ \ tau $ より効果的に。多態型は何らかの意味で、ここでは代わりに依存関係が必要な理由です。< / P>

フォローアップの質問に答えるために：依存型アプローチを使用して2つの可変ソートリストがある場合は、通常のリストと同様にリストを連結して平坦化することができます。

$ \ mathrm {list} $ monadは $ \ mathrm {join} $ です。（Haskellの言語で）、変動的に型付けされたリストのリスト、 $$ l= [[（a、a）、（b、b）]、[（c）、c）、（d、d）]]：（\ sigma_ {x：\ mathcal u} x）\ \ text {list list} $$ を実行できます。 $ \ mathrm {join} $ 新しいリストを取得するには： $$ \ mathrm {join}（l）= [（a、a）、（b、b）、（C、C）、（D、D）]：（\ sigma_ {x：\ mathcal u}} x）\ \ text {list} $$

同様に、 $ \ taw \ \ \ text {list} $ は連結操作を装備することができます $ + \！前の例の2つのリストを考えると、+ $ では、同様の結果について連結できます。 $$ [（a、a）、（b、b）] \ {+ \！+} \ [（c、c）、（d、d）]= [（a）、a）、（b、b）、（c、c）、（d、d）]：（\ sigma_ {x：\ mathcal u}} x）\ \ text {list} $$

他のヒント

いいえ、少なくとも有用な方法では不可能です。headのタイプが何であるかについて考えてください。すべての要素に同じタイプがある場合、headはtype $ \ tau \を持ちます。\ mathsf {list} \ to \ tau $ 。その保証がなければ、headにコヒーレントタイプを書き込む方法はありません。リストタイプが役立つようにするには、headの出力のタイプが何であるかについての有用な結論を描くことができるようにしたいです。それはリストのすべての要素が同じタイプを持つ必要があります。

私はあなたがが「リスト」を定義することができますが、その他の方法ではありませんでしたが、それは役に立ちませんでした（headでそれから抜け出す価値の種類について理由ができませんでした）あるいは、コンピュータの科学者が「リスト」と呼ぶものに対応しないでしょう。

型を有効に定義できない $\mathsf{リスト}$ それはその要素のタイプを示しません。これは、異なるタイプのものを含むリストを作成できないという意味ではありません。それはまだです $ au \, \mathsf{リスト}$, 、ただし、「異なるタイプのものを含む」部分を $\タウ$.

(これらの基本的なアイデアはすでに組み込まれています) D.W. そしてヴァルコールさんの答え。これらの答えは矛盾していないことを理解することが重要です。彼らは全体像のさまざまな側面を見ています。)

型システムで型を定義できる場合 $\mathsf{リスト}$ 任意の型の要素を含めることができる場合は、次のようなデストラクターの戻り値の型を検討してください。 $\mathsf{頭}$ または $\mathsf{nth}$, 、または関数の引数の型 $\mathsf{倍}$. 。要素のタイプに関する情報がないため、任意のタイプを許可する必要があります。これは、たとえば、 $\ラムダ x.\mathsf{頭}(\mathsf{短所}(x, \mathsf{nil}))$ と同じ型の値は返されません $x$ （または $x \, \mathsf{オプション}$, 、となることによって $\mathsf{頭}$ 戻れる $\mathsf{なし}$ 空のリスト上)。でも、それで何が返ってくるの？ $\mathsf{頭}$?

もし $\mathsf{頭}$ 呼び出し元が戻り値の型を指定できるようにすると、型システムはほとんど役に立ちません。型間の任意の強制が許可されるからです。 $\ラムダ x.\mathsf{頭}(\mathsf{短所}(x, \mathsf{nil}))$. 。ロジックとしては役に立たないので、カリーとハワードの通信型間の任意の強制を、すべての命題が他のすべての命題を暗黙的に示すようにマップするため、一貫性のないロジックが得られます。
そうでない場合は、元の型の値を取得することはできません。 $\ラムダ x.\mathsf{頭}(\mathsf{短所}(x, \mathsf{nil}))$. 。したがって、リストを構築することはできるかもしれませんが、そこから要素を取得することはできません。

上記の両方の動作を実際に示す実際の例は次のとおりです。初期のバージョンのジャワ, 、以前はジェネリック医薬品. 。Java には静的型システムと動的型システムの両方があります。静的型システムでは、任意の¹ 値を透過的に強制することができます。 Object, 、なぜなら Object すべてのスーパータイプとみなされます。したがって、任意の値を List. 。しかし、そこから得られるものは、キャストされた元の価値です。 Object, 、元の値そのものではありません。動的型システムでは、任意の型を他の型に強制できるため、実際には、リストから値を取得するには、その値を目的の型に強制します。しかし、強制を行うと、型システムの目的が無効になります。この問題は、Java がジェネリックスを取得した主な理由です。彼らは言語が持つことを許可します $ au \, \mathsf{リスト}$ の代わりに $\mathsf{リスト}$ (または Java 表記では、 List<T> の代わりに List).

リストには要素の型があるという理由だけで、$ au \, \mathsf{リスト}$ 型の要素のリストです。 $\タウ$ — 異なる型の値を同じリストに入れることができないという意味ではありません。リスト型を定義できる言語のほとんどは、代数データ型定義は次のようなものです。$$ au \, \mathsf{list} ::= \mathsf{nil} \mid \mathsf{cons} \:\タウ\:( au \, \mathsf{リスト}) $$整数と文字列の両方を同じリストに入れたいとします。タイプを定義する$$ U ::= \mathsf{I} \:\mathsf{int} \mid \mathsf{S} \:\mathsf{文字列} $$今 $U \, \mathsf{リスト}$ 整数と文字列の混合を含めることができるリストのタイプです。 $[\mathsf{I}(3), \mathsf{S}( exttt{"foo"}), \mathsf{I}(4)]$.

型システムが異種の型を許可する範囲で、この方法で異種のリストを作成できます。「異種リスト」は完全に正確ではないことに注意してください。リスト自体は同種です。それは type の要素のリストです $U$. 。異質性はタイプにあります $U$. 。リストに要素を入れるには、次のコンストラクターを適用します。 $U$ 初め。リストから要素を取得したら、次のデストラクターを適用します。 $U$ 元の型で元の値を取得します。

これは、言語がサポートする任意の型で実行できます。完全に異種のリストが必要な場合は、「any」型をサポートする言語が必要です。それは Object たとえばJavaでは。厳密に型指定されたものは、実行時に必要な型情報を保持している場合、「任意の」型を持つことができます。Java は常にそれを実行します。静的に型指定される言語 (OCaml や他の ML 方言、Haskell、Clean、Swift、Rust など) では、 $\mathsf{dyn}$ 実行時表現に値の型が含まれる型。このようなタイプだと、 $\mathsf{dyn} \, \mathsf{リスト}$ は、任意の型の値を含めることができるリスト型です。この型は、次のような他のリスト型と共存します。 $\mathsf{int} \, \mathsf{list}$ (リスト要素には実行時の型情報が含まれません)。

異種データ構造を構築するための関連アプローチは次のとおりです。実存型. 。存在型を使用すると、その型の値を含む型をパッケージ化できます。 $(\exists au :P(\タウ)。a)$ どこ $a$ ある種の式です $T$ そのような $P(T)$ それは本当です。例えば、 $\mathsf{dyn}$ 特別なケースとしてモデル化できます。 $P$ すべてのタイプ (境界のない存在) に当てはまります。存在型の一般的な使用法は、次のようになります。 $\タウ$ いくつかの特定の要素またはメソッドを含むレコード、モジュール、またはクラスですが、詳細はすべて示されていません。存在型は、抽象型をモデル化する方法です。境界付きの存在を使用すると、実行時の型情報がなくても、その値を使用していくつかの便利な操作を行うことができます (例:メソッドを呼び出すことができます $P$ で説明されています）が、元の型は取得できません。要素が存在型を持つリスト $T_E = (\exists au \ldots)$ (要素が異なる「実際の」型を持っているため) 異種リストとして見なすこともできますが、リストから値を取得した場合にわかるのはそのパッケージタイプだけであるという意味では依然として同種です $T_E$.

言語に依存型, を使用すると、元の値を復元できるように値をその型とともにパッケージ化できます。 $\mathsf{パッケージ} ::= \sum_{ au:\mathsf{TYPE}} au$ どこ $\mathsf{タイプ}$ タイプのタイプです。これは依存合計タイプここで、最初のコンポーネントはたまたま型です。の $\mathsf{パッケージ}$ type は、依存型型言語で無制限の存在情報を実装する方法です。制約を追加することで、境界のある実存情報を構築できます。 $\タウ$. 。もう一度言いますが、次のような意味で異種リストを構築できます。 $\mathsf{パッケージ} \, \mathsf{リスト}$ 「実際の」型が異なる要素が含まれていますが、各リスト要素が型を持つという意味では、リスト自体は同種です。 $\mathsf{パッケージ}$. 。存在型の場合と同様、リストから値を抽出して、その「実際の」型を直接復元することはできません。type の値を破棄することができます $\mathsf{パッケージ}$ 2 番目の要素の射影を適用しますが、結果についてわかっているのは、その型が最初の要素の射影であるということだけです。 $p :\mathsf{パッケージ} \vdash \pi_2(p) :\pi_1(p)$.

これまで、非縮退型システムではリストが同種であることを見てきました。異種のリストを構築することは可能ですが、リスト型コンストラクター自体は同種です。異質性は要素のタイプに由来します。代数データ型と整数 (または自然数と同型のもの) に依存する型の両方を持つ言語では、真に異種のリスト型を定義することが可能です。型ファミリーが与えられた場合 $(T_n)_{n \in \mathbb{N}}$, 、リストのタイプを定義できます。 $n$番目の要素には型があります $T_n$. 。このような言語での定義は次のとおりです。帰納構文の微積分, 、特に Coq 構文で。まず、整数によってインデックス付けされた型ファミリーの例を定義します。 tuple A n のタイプです n-要素タプルのコンポーネントはすべて次の型を持つ A. 。定義を単純にするために、すべてのタプルには追加の値があります。 U ユニットタイプの先頭にあります。次に、帰納型を定義します hlist_ これは型ファミリーの両方によってパラメータ化されます T そして整数 n, 、これは異種リストです。 k番目の要素には型があります n + k. 。パラメータ n 定義を建設的に保つために必要です。最後に、型の用語の例をいくつか示します。 hlist (tuple bool), 、つまり、誰が n番目の要素は nth-要素タプルの bool 値 ( U 先頭に追加されます）。

Inductive unit : Type := U : unit.
Fixpoint tuple (A : Type) (n : nat) : Type :=
  match n with
    | 0 => unit
    | S m => (tuple A m) * A
  end.

Inductive hlist_ (T : nat -> Type) n :=
  | Hnil : hlist_ T n
  | Hcons : (T n) -> hlist_ T (S n) -> hlist_ T n.
Definition hlist T := hlist_ T 0.

Check (Hcons (tuple bool) 0 U (Hnil _ _) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hnil _ _)) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hcons _ 2 (U, true, true) (Hnil _ _))) : hlist (tuple bool)).

¹ _{実際には、一部のプリミティブデータ型を除きますが、それはここでは重要ではありません。この回答で Java について「任意」と言うときは、プリミティブデータ型ではなく、オブジェクトのみを意味します。}

ライセンス： CC-BY-SA と帰属

所属していません cs.stackexchange