4. 組とリスト
プログラミング言語には、既存の型から新たな型を作る機能がある。このことを型構成子(type constructor)という。例えばCには次のような型構成子がある。
-
構造体を作る構文 struct
-
参照型(ポインタ型)を作る構文*
-
配列を作る構文 []
MLには、Cよりも強力な型構成子が用意されている。ここでは、そのうち最も重要な組(tuple)とリスト(list)について述べる。
組
組は、2つ以上の式の並びである。これらの式の型は異なっていてもよい。Cの構造体と似た概念であるが、構造体と異なり、それぞれの式には名前(メンバ名)はなく、組の中で出現した順番で区別される。
val t = (4, 5.0, "six");
val t = (4, 5.0, "six") : int * real * string
MLからの応答に注意されたい。(4, 5.0, "six")の型がint * real * stringという型であると言っている。このような型のことを積型(product type)という。積型の記法の定義は以下のようになる。
T
1, T
2, …, T
kを型とするとき、T
1 * T
2 * … * T
kは積型であり、その値は組(v
1, v
2, …, v
k)である。ただしv
i (i = 1, 2,…, k)の型はT
iである。
積型構成子 * では、結合則が成り立たない。つまり、以下の2つの式はまったく異なる型である。
-
int * int * int * int型の式 (1, 2, 3, 4)
-
int * (int * int * int)型の式 (1, (2, 3, 4))
組tのi番目の要素を得るには、関数 #i を用いる。
val t = (4, 5.0, "six");
val t = (4, 5.0, "six") : int * real * string
#1(t);
val it = 4 : int
#3(2.0, 3, true);
val it = true : bool
リスト
0個以上の同じ型の式の並びをリスト(list)という。例えば [1, 2, 3] は整数のリストである。組と異なり、要素がすべて同じ型でなければエラーになる。
[1, 2, 3];
val it = [1,2,3] : int list
["a"];
val it = ["a"] : string list
[#"a", #"b", "c"];
Error: operator and operand don't agree [tycon mismatch]
operator domain: char * char list
operand: char * string list
in expression:
#"b" :: "c" :: nil
型Tに対し、T型の式を要素とするリストの型は、Tに型構成子listを適用して得られる型T listである。
リストの記法、演算子
いずれも極めて重要である。
-
空リスト(empty list)…要素が1つもないリスト。nilまたは[]。
-
頭部(head)…空でないリストの先頭の要素。関数hdで得られる。
-
尾部(tail)…空でないリストから、先頭の要素を取り除いて得られるリスト。関数tlで得られる。
-
リストの連結(concatenation)…2つのリストを順につないだリスト。演算子@。
-
コンス(cons)…リストLの先頭に、要素aを挿入したリストを得る。演算子::。
リストの連結、コンスは右結合の演算子である。例えば1::2::3::nilは1::(2::(3::nil))の意味となる。
練習問題
-
次の型を持つ式の例を示せ。
-
(int * char) * string * int
-
bool list
-
次の式の型を示せ。
-
(3, 6.0, [1, 2])
-
[(4, "a"), (5, "b"), (6, "c")]
-
次の式の値を示せ。
-
#2(3, 4, 5)
-
tl([3, 4, 5])
-
"c" :: ["a", "t"]
-
次の式の型を示せ。
-
(1.5, ("3", [4, 5]))
-
[[1, 2], nil, [3]]
-
次の型を持つ式の例を示せ。
-
(int * char) list
-
string list * (int * (real * string)) * int