リスト

リスト操作関数

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

関数 説明
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.nthList.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)] を返す

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

リストの畳み込み

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