リスト

1. リストとは

リスト（list）は，複数のデータを一列に並べたデータ構造のひとつです． ML では，複数のデータを扱う際には，配列よりもリストがよく使われます．

リストの概念図

これは，リスト [1, 2, 3] の概念的な構造を表した図です． リストはこの図のように，値をもつ単位（LISP ではこれを "cons セル" とよぶ）を一列に並べた構造となっています． 最後は空リスト（nil）で終わります．

配列と違って注意しないといけないのは，リストは "n 番目の要素を取り出す" みたいな処理が不得意という点です． 配列ではこの操作は一瞬ですが，リストの場合には，列を先頭から順番に辿っていかなければならないため，時間がかかります． ただし，Haskell ではインデックスを指定して要素を取り出す操作はあまり書かないため，このことはそれほど問題になりません．

2. ML のリスト

ML では，次の 2 通りの方法でリストを書くことができます． 構文上はまるで見た目が違いますが，どちらも同一のリストを表します．

1 :: 2 :: 3 :: nil  -- cons 構成子による書き方
[1, 2, 3]           -- リストリテラルによる書き方

すべてのリストは nil と :: という2つの構成子を用いて記述できます． 角括弧を用いたリストの式 [1, 2, 3] は 1 :: 2 :: 3 :: nil の構文糖という位置づけです．

:: はしばしば "cons" と呼ばれ（"construct" の意），第 1 引数に先頭要素，第 2 引数に後続のリストをとります． :: は右結合なので，1 :: 2 :: 3 :: nil の結合は 1 :: (2 :: (3 :: nil)) です．

ML で扱うリストは，同一の型の要素のみで構成されるリストです． つまり，[1, 1.0, #"a"] のようなリストは許されません． 型が 'a である要素から構成されるリストの型を 'a list と書きます．

- 1 :: 2 :: 3 :: nil;
val it = [1,2,3] : int list
ML が採用しているような，すべて同じデータ型の要素からなるリストは，等質的 (homogeneous) なリストとよばれます．

3. リストを扱う関数

リストを扱う標準関数のうち，トップレベルで定義されているものは以下の通りです．

関数 型 説明

null xs

'a list -> bool

空リストであれば true

hd xs

'a list -> 'a

先頭要素を返す

tl xs

'a list -> 'a list

先頭要素を除去する

length xs

'a list -> int

リストの長さを返す

map f xs

('a -> 'b) -> 'a list -> 'b list

各要素に関数 f を適用する

rev xs

'a list -> 'a list

要素の並びを逆にする

xs @ ys

'a list * 'a list -> 'a list

リストを連結する

foldr f z xs

('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

右から左へリストを畳み込む

foldl f z xs

('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

左から右へリストを畳み込む

型を見ればだいたいどんな関数なのか想像がつくのが面白いですね．

他にも，リストを操作する様々な関数が List ストラクチャで定義されています． 主なものには以下のようなものがあります． これらの関数は List.nth や List.concat のように書けばアクセスできます．

関数 型 説明

last xs

'a list -> 'a

最終要素を返す

nth (xs, n)

'a list * int -> 'a list

先頭から n 番目の要素を返す

take (xs, n)

'a list * int -> 'a list

先頭から n 要素分のリストを返す

drop (xs, n)

'a list * int -> 'a list

先頭から n 要素分を除去する

concat xss

'a list list -> 'a list

要素のリストを連結する

filter p xs

('a -> bool) -> 'a list -> 'a list

述語 p を満たす要素を残す

exists p xs

('a -> bool) -> 'a list -> bool

述語 p を満たす要素があれば true

all p xs

('a -> bool) -> 'a list -> bool

すべての要素が述語 p を満たせば true

tabulate (n, f)

int * (int -> 'a) -> 'a list

リスト [f 0, f 1, …​, f (n-1)] を返す

いくつか使用例を見てみましょう．

  • map f xs: リストの各要素に関数 f を適用します． 
     - map (fn x => x * x) [1, 2, 3, 4, 5];
 val it = [1,4,9,16,25] : int list
  • xs @ ys: リストを連結します（@ はおそらく "append" の意）． 
     - [1, 2] @ [3, 4, 5];
 val it = [1,2,3,4,5] : int list
  • filter p xs: 述語 p が真を返す要素だけを残します． 
     - List.filter (fn x => x mod 2 = 1) [1, 2, 3, 4, 5];
 val it = [1,3,5] : int list

4. リストの畳込み

foldr は二項演算子を使って右からリストを畳み込む関数です． 二項演算子を ⊕ とすると，式 foldr ⊕ 0 [1, 2, 3] は 1 ⊕ (2 ⊕ (3 ⊕ 0)) と展開されます．

- foldr (op +) 0 [1, 2, 3]  (* 1 + (2 + (3 + 0)) = 6 *) ;
val it = 6 : int

- foldr (op -) 0 [1, 2, 3]  (* 1 - (2 - (3 - 0)) = 2 *) ;
val it = 2 : int

foldl は逆に，二項演算子を使って左からリストを畳み込みます． 二項演算子を ⊕ とすると，式 foldl ⊕ 0 [1, 2, 3] は，3 ⊕ (2 ⊕ (1 ⊕ 0)) と展開されます．

- foldl (op +) 0 [1, 2, 3]  (* 3 + (2 + (1 + 0)) = 6 *) ;
val it = 6 : int

- foldl (op -) 0 [1, 2, 3]  (* 3 - (2 - (1 - 0)) = 2 *) ;
val it = 2 : int

畳込み関数はかなり表現力が高く，リストを操作するだいたいの関数は foldr を使って記述できます． 例えば，map 関数は foldr を使って以下のように書くこともできます．

- fun map' f = foldr (fn (x, s) => f x :: s) nil;
val map' = fn : ('a -> 'b) -> 'a list -> 'b list

- map' (fn x => x * x) [1,2,3,4,5];
val it = [1,4,9,16,25] : int list