日: 2008年1月13日

あいだが開いてしまった。多相や型推論の部分はどうにも頭の整理できないので，先に進もう。

リストは全体を [ と ] で囲って，要素を ; で区切る。[]は空リストを表す。

# [1;2;3];;
- : int list = [1; 2; 3]
# [];;
- : 'a list = []
||<
::（コンスオペレーター）で要素をリストの先頭に追加する。
>||
# 1 :: [2;3;4;5];;
- : int list = [1; 2; 3; 4; 5]

引数のパターンマッチには match式をつかう。リストパターンは :: を使える。たとえば：

# let rec sum l =
match l with
[] -> 0
| hd::tl -> hd + sum tl
;;
val sum : int list -> int = <fun>
# sum [1;3;5;7;9];;
- : int = 25

List.length はリストの長さを返す。

# List.length [1;2;3;4;5];;
- : int = 5

実装してみる。

# List.length [1;2;3;4;5];;
- : int = 5
# let rec length' l =
match l with
[] -> 0
| hd :: tl -> 1 + length' tl
;;
val length' : 'a list -> int = <fun>
# length' [1;2;3;4;5];;
- : int = 5

List.append は2つのリストを連結する。

# List.append [1;2;3] [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]

実装してみる。

# let rec append' l1 l2 =
match l1 with
[] -> l2
| hd::tl -> hd :: append' tl l2
;;
val append' : 'a list -> 'a list -> 'a list = <fun>
# append' [1;2;3] [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]

リストの連結は中置演算子 @ でもできる。

# ['a';'b';'c'] @ ['d';'e';'f'];;
- : char list = ['a'; 'b'; 'c'; 'd'; 'e'; 'f']

reverse はリストを逆順にする。

# let rec reverse l =
match l with
[] -> []
| hd::tl -> (reverse tl) @ [hd]
;;
val reverse : 'a list -> 'a list = <fun>
# reverse [1;2;3;4;5];;
- : int list = [5; 4; 3; 2; 1]