これまで，構造のあるデータを表現するための手段としては組 を用いてきた．ここではリスト(lists)という， 「データの(有限)列」を表現するデータ構造をみていく． リストは構造自体が再帰的である．また，格納するデータの種類 が変わりうるという意味で多相的であるという特徴をもっている．
まずは簡単なリストの例を見てみよう．リストはデータ列を構成する 要素を ; で区切り，[]で囲むことで構成される．
# [3; 9; 0; -10];; - : int list = [3; 9; 0; -10] # let week = ["Sun"; "Mon"; "Tue"; "Wed"; "Thu"; "Fri"; "Sat"];; val week : string list = ["Sun"; "Mon"; "Tue"; "Wed"; "Thu"; "Fri"; "Sat"]
リストの式には “⟨ 要素の型 ⟩ list” という 型が与えられる．これが意味するのは「(Objective Caml では)一つの リストに並ぶ要素の型は同じ」でなければならない，という ことである．また別の見方をすると，リスト式はその列の長さに関わらず，要 素の型が同じであれば，同じリスト型に属するということである．
# [1; 'a'];; [1; 'a'];; ^^^ This expression has type char but is here used with type int # (* compare with the type of [3; 9; 0; -10] *) [-3];; - : int list = [-3]
このことは組とリストの決定的な違いであるので注意すること． 組の型は各要素の型を並べることで記述されるため，各要素の型は 異ってもよいが，大きさの違う組は同じ型に属し得ない(すなわち， 組の大きさの情報が型に現れている)．
リストの構造は，組のように「要素を並べたもの」と思う代りに， 以下のように再帰的に定義されている構造とも考えられる．つまり
と定義することもできる．この定義は二番目の節が再帰的になっている． :: のことをcons オペレータ(または単に cons)と呼ぶこともある． このようにリストを構築する例を見てみよう．
# let oddnums = [3; 9; 253];; val oddnums : int list = [3; 9; 253] # let more_oddnums = 99 :: oddnums;; val more_oddnums : int list = [99; 3; 9; 253] # (* :: is right associative, that is, e1 :: e2 :: l = e1 :: (e2 :: l) *) let evennums = 4 :: 10 :: [256; 12];; val evennums : int list = [4; 10; 256; 12] # [];; - : 'a list = []
要素を列記する方法と :: を用いる方法を混ぜることもできる． evennums の例に見るように，:: は右結合する(e1 :: e2 :: l は e1 :: (e2 :: l) と読む)． 空リスト [] は要素がなく，どのような要素 のリストとも見なせること ができるため，'a list という多相型が与えら れている．もちろん，空リストには様々な型の要素を追加することができる．
# let boollist = true :: false :: [];; val boollist : bool list = [true; false] # let campuslist = "Yoshida" :: "Uji" :: "Katsura" :: [];; val campuslist : string list = ["Yoshida"; "Uji"; "Katsura"]
ちなみに Objective Caml では「要素を並べる」定義は，(内部的には)再帰的な定義の 略記法である．つまり，
[e1; e2; ⋯ ; en] = e1 :: e2 :: ⋯ :: en :: []
である．
cons オペレータ :: は，あくまで「一要素の(先頭への)追加」 を行うもので，リストにリストを追加(連結)するという操作や，リストの最後 尾へ要素を追加するといった操作は :: で行えない．
# [1; 2] :: [3; 4];; [1; 2] :: [3; 4];; ^ This expression has type int but is here used with type int list # [1; 2; 3] :: 4;; [1; 2; 3] :: 4;; ^ This expression has type int but is here used with type int list list
:: は文法キーワードなので，:: の型を見ることはできないが， 敢えて型を考えるなら 'a -> 'a list -> 'a list と思うのがよいだろう． リストはどんな値でも要素にでき，関数のリスト，リストのリスト等を考える ことも可能である．
# [(fun x -> x + 1); (fun x -> x * 2)];; - : (int -> int) list = [<fun>; <fun>] # [1; 2; 3] :: [[4; 5]; []; [6; 7; 8]];; - : int list list = [[1; 2; 3]; [4; 5]; []; [6; 7; 8]]
2番目の例は，整数リストのリストに整数リストを :: で追加している．
さて，リストの要素にアクセスするときには組と同様にパターンを用いる． リストパターンは
[⟨ パターン1 ⟩; ⟨ パターン2 ⟩; ...; ⟨ パターンn ⟩]
で n 要素のリスト(n が 0 なら空リスト)にマッチさせることができ る．また，:: を使ってパターンを記述することもできる．
⟨ パターン1 ⟩ :: ⟨ パターン2 ⟩
と書いて，先頭の要素を ⟨ パターン1 ⟩ に，残りのリストを ⟨ パターン2 ⟩にマッチさせることができる．次の関数は， 三要素の整数リストの要素の和を計算する関数である．
# (* equivalent to
let sum_list3 (x :: y :: z :: []) = x + y + z *)
let sum_list3 ([x; y; z]) = x + y + z;;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
let sum_list3 ([x; y; z]) = x + y + z;;
^^^^^^^^^^^^^^^^^^^^^^^
val sum_list3 : int list -> int = <fun>
リスト式の場合と同様，[x; y; z] というパターンは :: と [] を 使ったパターンで表すことができる．ここで，重要なことはこの関数を コンパイルをするとコンパイラから警告が発せられていることである． この “nonexhaustive pattern” と呼ばれる警告は，「パターンの表す型に 属する値でありながら，パターンにマッチしない値が存在する」という 意味であり，コンパイラはマッチしない値の例を示してくれる． たしかにこの例では引数の型は int list であるにも関わらず 三要素のリストにしかマッチしない．実際，マッチしない値に関数を適用すると マッチングに失敗したという例外が発生する．
# sum_list3 [4; 5; 6];;
- : int = 15
# sum_list3 [2; 4];;
Exception: Match_failure ("", 27, 14).
では，任意の長さの整数リストの要素の和を取る関数を書くにはどうすれば よいのだろうか? 例え，二要素のリストの和を取る関数，四要素リストの和を 取る関数などなどを定義し，それを何らかの手段で組み合わせることができた としても，それでは不十分である．関数定義の大きさが無限に長くなってしま う! ここで，リストが再帰的な定義をされた構造であることが非常に重要な意味を持っ てくる．つまり，リストの再帰的な定義から，要素の和を取る定義を導くこと ができるのである．それが以下の定義である．
ポイントは，長いリストの全要素の和はより短いリストの全要素の和 から計算できることである．(fact などの定義と比べてみよ．) これを Objective Caml の定義とするためには，与えられたリストが空かそうでない かを判断する手段が必要であるが，ひとまず例を見て，その判断をどのように行うか 見てみよう．
# let rec sum_list l =
match l with
[] -> 0
| n :: rest -> n + (sum_list rest);;
val sum_list : int list -> int = <fun>
まず，sum_list は再帰関数になっている． match 以下が l が空リストかそうでないかを判断し，分岐処理を行っている部分で match式と呼ばれる．match式の一般的な文法は，
match ⟨ 式0 ⟩ with ⟨ パターン1 ⟩ -> ⟨ 式1 ⟩ | … | ⟨ パターンn ⟩ -> ⟨ 式n ⟩
という形で与えられ，⟨ 式0 ⟩を評価した結果を，⟨ パターン1 ⟩ から順番にマッチさせていき，⟨ パターンi ⟩でマッチが成 功したら，⟨ 式i ⟩を評価する．全体の値は⟨ 式i ⟩の値である． 各パターンで導入された変数 (上の例では n, rest) は対応する式の中だけで有効で ある．上の Objective Caml による定義が，自然言語による定義に対応していることを 確かめよ．多くのリストを操作する関数は sum_list のように， 空リストの場合の処理と，cons の場合の処理を match で組み合わせて 書かれる．
match 式がマッチングを順番に行う，というのは非常に重要な 点である．もしも，同じ値が複数のパターンにマッチする場合は先に 書いてあるパターンにマッチしてしまう．このような例は特に定数パ ターンを使用すると発生しやすい．定数パターンは整数，文字列定数を パターンとして用いるもので，その定数にのみマッチする．また， 前に書いてあるパターンのせいで，パターンにマッチする値がない場合， コンパイラは “this match case is unused.” と警告を発する．
# let f x =
match x with (1, _) -> 2 | (_, 1) -> 3 | (1, 1) -> 0 | _ -> 1;;
Warning U: this match case is unused.
match x with (1, _) -> 2 | (_, 1) -> 3 | (1, 1) -> 0 | _ -> 1;;
^^^^^^
val f : int * int -> int = <fun>
# f (1, 1);;
- : int = 2
(1, 1) は最初のパターンにマッチする．また，3番目のパターンは 決して使われないので警告が出ている．
さて，一般的なリスト操作関数の例を見ていく前に，もうひとつ例をみていこ う．(空でない)整数リストのなかから最大値を返す関数 max_list は
# let rec max_list l =
match l with
[x] -> x
| n1 :: n2 :: rest ->
if n1 > n2 then max_list (n1 :: rest) else max_list (n2 :: rest);;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
..match l with
[x] -> x
| n1 :: n2 :: rest ->
if n1 > n2 then max_list (n1 :: rest) else max_list (n2 :: rest)..
val max_list : 'a list -> 'a = <fun>
のように定義される．
さて，リストに対する基本的な操作(構成と要素アクセス)をみたところで， 様々なリスト操作を行う関数を見ていこう．多くの関数がリストの構造に関し て再帰的に定義される．また，ほとんどすべての関数が要素型によらない定義 をしているため，多相型が与えられることに注意しよう．
リストの先頭要素，リストの先頭を除いた残りを返す関数 hd (head の略), tl (tail の略) は以下のように定義され，
# let hd (x::rest) = x let tl (x::rest) = rest;; Warning P: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: [] Characters 29-45: Warning P: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: [] let hd (x::rest) = x ^^^^^^^^^^^^^ let tl (x::rest) = rest;; ^^^^^^^^^^^^^^^^ val hd : 'a list -> 'a = <fun> val tl : 'a list -> 'a list = <fun>
空リストに対しては働けない nonexhaustive な関数である．null は 与えられたリストが空かどうかを判定する関数である．
# let null = function [] -> true | _ -> false;; val null : 'a list -> bool = <fun>
function キーワードは fun と match を組み合わせて匿名関数を定 義するもので，
function ⟨ パターン1 ⟩ -> ⟨ 式1 ⟩ | ... | ⟨ パターンn ⟩ -> ⟨ 式n ⟩
で
fun x -> match x with ⟨ パターン1 ⟩ -> ⟨ 式1 ⟩ | ... | ⟨ パターンn ⟩ -> ⟨ 式n ⟩
を示す．最後に受け取った引数に関して即座にパターンマッチを行うような 関数定義の際に便利である．
次は，n番目の要素を取り出す nth, n番目までの要素の 部分リストを取り出す take，n番目までの要素を抜かした 部分リストを取り出す drop である．リストの要素は先頭を一番目とする．
# let rec nth n l =
if n = 1 then hd l else nth (n - 1) (tl l)
let rec take n l =
if n = 0 then [] else (hd l) :: (take (n - 1) (tl l))
let rec drop n l =
if n = 0 then l else drop (n - 1) (tl l);;
val nth : int -> 'a list -> 'a = <fun>
val take : int -> 'a list -> 'a list = <fun>
val drop : int -> 'a list -> 'a list = <fun>
これらの関数はリストの構造でなく，nに関しての再帰関数に なっている．
# let ten_to_zero = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0];;
val ten_to_zero : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0]
# nth 4 ten_to_zero;;
- : int = 7
# take 8 ten_to_zero;;
- : int list = [10; 9; 8; 7; 6; 5; 4; 3]
# drop 7 ten_to_zero;;
- : int list = [3; 2; 1; 0]
# take 19 ten_to_zero;;
Exception: Match_failure ("", 48, 7).
次はリストの長さを返す関数 length である．
# let rec length = function
[] -> 0
| _ :: rest -> 1 + length rest;;
val length : 'a list -> int = <fun>
length の型は _ パターンを使って先頭要素を使用してないことからわか るように，どんなリストに対しても使うことができる．実際，型をみると 入力の要素型が型変数になっている．
# length [1; 2; 3];; - : int = 3 # length [[true; false]; [false; false; false;]];; - : int = 2
また length はふたつめの結果にみられるように，一番外側のリスト の長さを計算するものである(結果は 5 ではない)．
次に示す append 関数はリスト同士を連結する関数である．append l1 l2 の 再帰的定義は
と考えることができる．
# let rec append l1 l2 =
match l1 with
[] -> l2
| x :: rest -> x :: (append rest 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]
この append の定義は，l1 の長さが長くなるほど 再帰呼び出しが深く行われ，l2 の長さには関係がない． ちなみに append 関数は，もともと Objective Caml 起動時に中置オペレータ @ として 定義されている．
# [1; 2; 3] @ [4; 5; 6];; - : int list = [1; 2; 3; 4; 5; 6]
また append を使ってリストを反転させる reverse 関数を定義できる．
# let rec reverse = function
[] -> []
| x :: rest -> append (reverse rest) [x];;
val reverse : 'a list -> 'a list = <fun>
リストの最後に要素を追加することは直接はできないので，一要素リストを作っ て append している．しかし，この関数はあまり効率的ではない．なぜなら， reverse の呼び出し一度につき，append が一度呼ばれるが，この時 append の第一引数の長さは「反転させようとする引数の長さ−1」であ りappend を計算するのにその長さ分の計算量を必要とする．reverse の 再帰呼び出し回数は与えたリストの長さなので，リストの長さの自乗に比例し た計算時間がかかってしまう．
これを改善したのが次の定義である．
# let rec revAppend l1 l2 =
match l1 with
[] -> l2
| x :: rest -> revAppend rest (x :: l2)
let rev x = revAppend x [];;
val revAppend : 'a list -> 'a list -> 'a list = <fun>
val rev : 'a list -> 'a list = <fun>
最初の再帰関数 revAppend が第一引数を先頭から順に l2 に追加して行く 関数である．先頭から追加していくため，l1 の順が逆になって l2 に連結される．
# revAppend [1; 2; 3] [4; 5; 6];; - : int list = [3; 2; 1; 4; 5; 6]
この関数も append と同じく，第一引数の長さだけに比例した時間がかかる． リストの反転は revAppend の第二引数が空である特別な場合である．
# rev ['a'; 'b'; 'c'; 'd'];; - : char list = ['d'; 'c'; 'b'; 'a']
map はリストの各要素に対して同じ関数を適用した結果のリストを求める ための高階関数である．
# let rec map f = function
[] -> []
| x :: rest -> f x :: map f rest;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
たとえば，整数リストの各要素を2倍する式は map を使って，
# map (fun x -> x * 2) [4; 91; 0; -34];; - : int list = [8; 182; 0; -68]
と書くことができる．map の型は今まで見た中でかなり複雑である． まず，'a -> 'b で「何らかの関数」が第一引数であることがわかる． カリー化関数とみるならば，第二引数は「何らかの関数」の定義域 の値を要素とするリストで，結果が「何らかの関数」の値域の値を 要素とするリストとなる．または「何らかの関数」を与えた時点で リストからリストへの関数が返ってきていると解釈してもよい．
forall はリストの要素に関する述語(要素から bool への関数)と，リス トをとり，全要素が述語を満たすかどうかを，exists は同様に述語と リストをとって，述語を満たす要素があるかどうかを返す関数である．
# let rec forall p = function
[] -> true
| x :: rest -> if p x then forall p rest else false
let rec exists p = function
[] -> false
| x :: rest -> (p x) or (exists p rest);;
val forall : ('a -> bool) -> 'a list -> bool = <fun>
val exists : ('a -> bool) -> 'a list -> bool = <fun>
# forall (fun c -> 'z' > c) ['A'; ' '; '+'];;
- : bool = true
# exists (fun x -> (x mod 7) = 0) [23; -98; 19; 53];;
- : bool = true
上で見た sum_list, append はリストの要素すべてを用いた演算をするも のである．実はこの二つの関数は共通の計算の構造を持っている． sum_list は [i1; i2; ...; in], つまり
i1 :: i2 :: ... :: in :: []
から
i1 + (i2 + (... + (in + 0)...))
を計算し， append [e1; e2; ...; en] l2 は
e1 :: (e2 :: ... :: (en :: l2)...)
を計算している． このふたつの計算の共通点は，
ことである．このような「右から畳み込む」計算構造を一般化した高階関数を fold_right と呼ぶ．逆に左から畳み込むのを fold_left と呼ぶ． rev は fold_left の例である．何故なら， rev [e1; e2; ...; en] は l ::: x を x :: l として，
(...(([] ::: e1) ::: e2) ... ::: en)
と表現できるからである．
以下が fold_right, fold_left の定義である．
fold_right f [e1; e2; ...; en] e =⇒ f e1 (f e2 (... (f en e)...)) fold_left f e [e1; e2; ...; en] =⇒ f (... (f (f e e1) e2) ...) en
を計算する．
# let rec fold_right f l e =
match l with
[] -> e
| x :: rest -> f x (fold_right f rest e)
let rec fold_left f e l =
match l with
[] -> e
| x :: rest -> fold_left f (f e x) rest;;
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
# fold_right (fun x y -> x + y) [3; 5; 7] 0;;
- : int = 15
# fold_left (fun x y -> y :: x) [] [1; 2; 3];;
- : int list = [3; 2; 1]
fold_left, fold_right は要素はそのままで cons を適当な演算子に 読み替えて，計算をするものと思うことができる．一方， map 関数はリストの構造はそのままで，要素だけを操作する ような計算構造を抽象化した高階関数であった．実はリストに関する 再帰関数はほとんど map と fold_left または fold_right を組み合わせて 定義することができる．例えば，length は全要素をまず map を使って 1 に置換えて，足し算による畳み込みを行えばよいので，
# let length l = fold_right (fun x y -> x + y) (map (fun x -> 1) l) 0;; val length : 'a list -> int = <fun>
と定義することも可能である．
辞書における見出しと説明文，データベースにおけるデータ検索のためのキー とデータ，のような「関係」を表現するのに連想リスト(association list) というデータ構造を用いる．連想リストは構造的にはペアのリストで表現される． 各要素 (a, b) はキー a の データ b への関連付けを表現する．
例えば，以下は，都市の名前をキー，市外局番をデータとした 連想リストの例である．
# let city_phone = [("Kyoto", "075"); ("Osaka", "06"); ("Tokyo", "03")];;
val city_phone : (string * string) list =
[("Kyoto", "075"); ("Osaka", "06"); ("Tokyo", "03")]
このような連想リストとキーから，関連づけられたデータを取り出す 関数 assoc は以下のように定義できる．
# let rec assoc a = function
(a', b) :: rest -> if a = a' then b else assoc a rest;;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
..................function
(a', b) :: rest -> if a = a' then b else assoc a rest..
val assoc : 'a -> ('a * 'b) list -> 'b = <fun>
# assoc "Osaka" city_phone;;
- : string = "06"
# assoc "Nara" city_phone;;
Exception: Match_failure ("", 124, 18).
連想リストにないキーで問い合わせを行うと，再帰呼び出しがリストの末端まで 到達した末にマッチングに失敗して例外を発生する．
リストを使ったソートアルゴリズムをいくつかみていこう．以下では リストを < に関する昇順(小さい方から順)に並べ替えることを考える． (比較演算子 < は多相的であるため，ソート関数も多相的に使える．)
まずは準備として，ソートの対象として用いる，疑似乱数列を生成するため の関数を定義する．
# let nextrand seed =
let a = 16807.0 and m = 2147483647.0 in
let t = a *. seed
in t -. m *. floor (t /. m)
let rec randlist n seed tail =
if n = 0 then (seed, tail)
else randlist (n - 1) (nextrand seed) (seed::tail);;
val nextrand : float -> float = <fun>
val randlist : int -> float -> float list -> float * float list = <fun>
# randlist 10 1.0 [];;
- : float * float list =
(2007237709.,
[1458777923.; 1457850878.; 101027544.; 470211272.; 1144108930.; 984943658.;
1622650073.; 282475249.; 16807.; 1.])
挿入ソート(insertion sort)は，既にソート済のリストに 新しい要素をひとつ付け加える操作を基本として，各要素を 順に付け加えていくものである．基本操作 insert は
# let rec insert (x : float) = function
(* Assume the second argument is already sorted *)
[] -> [x]
| (y :: rest) as l -> if x < y then x :: l else y :: (insert x rest);;
val insert : float -> float list -> float list = <fun>
# insert 4.5 [2.2; 9.1];;
- : float list = [2.2; 4.5; 9.1]
と書くことができる．パターン中に出現する
⟨ パターン ⟩ as ⟨ 変数 ⟩
は as パターンと呼ばれるもので，パターンにマッチした値全体を ⟨ 変数 ⟩で参照できるものである．ここでは x :: y :: rest と 書く代りに x :: l としている．この insert を使ってソートを 行う関数は
# let rec insertion_sort = function
[] -> []
| x :: rest -> insert x (insertion_sort rest);;
val insertion_sort : float list -> float list = <fun>
と定義できる．
挿入ソートは insert, insertion_sort ともに入力に比例する回数の再帰呼出 しを行うため，計算には与えられたリストの長さの自乗に比例した時間がかかる． クイックソート(quick sort)はC.A.R. Hoareが発明した効率の良いソー トアルゴリズムで，分割統治(divide and conquer)法に基づき，下のよ うな要領でソートを行う．
# let rec quick = function
[] -> []
| [x] -> [x]
| x :: xs -> (* x is the pivot *)
let rec partition left right = function
[] -> (quick left) @ (x :: quick right)
| y :: ys -> if x < y then partition left (y :: right) ys
else partition (y :: left) right ys
in partition [] [] xs;;
val quick : 'a list -> 'a list = <fun>
この quick の定義は append を使用しているのでまだ効率の悪い点が 残っている．(append を使用しない定義は練習問題．) クイックソートは リストの長さを n として，平均で nlogn に比例した時間で 行えることが知られている．
insert_sort (snd (randlist 10000 1.0 []))
と
quick (snd (randlist 10000 1.0 []))
を試してみよ．(snd はペアから第二要素を取り出す定義済の関数である．)
roman [(1000, "M"); (500, "D"); (100, "C"); (50, "L");
(10, "X"); (5, "V"); (1, "I")] 1984
=⇒ "MDCCCCLXXXIIII"
4, 9, 40, 90, 400, 900 などの表現にも注意して，
roman [(1000, "M"); (900, "CM"); (500, "D"); (400, "CD");
(100, "C"); (90, "XC"); (50, "L"); (40, "XL");
(10, "X"); (9, "IX"); (5, "V"); (4, "IV"); (1, "I")] 1984
=⇒ "MCMLXXXIV"
となるようにせよ．concat [[0; 3; 4]; [2]; [5; 0]; []] = [0; 3; 4; 2; 5; 0]
# let positive x = (x > 0);; val positive : int -> bool = <fun> # filter positive [-9; 0; 2; 5; -3];; - : int list = [2; 5] # filter (fun l -> length l = 3) [[1; 2; 3]; [4; 5]; [6; 7; 8]; [9]];; - : int list list = [[1; 2; 3]; [6; 7; 8]]
let rec quicker l sorted = ...