Previous  Up  Next

Module List


module List: sig .. end
リスト操作

いくつかの関数は末尾再帰的ではありません。 末尾再帰の関数のスタック使用量は一定で、非末尾再帰の関数はリストの長さに比例したスタックを使用します。 非常に長いリストに対しては末尾再帰でないことが問題になる可能性があります。 関数が複数のリストを引数に取る場合には、近似的なスタック使用量を（何らかの適当な単位で）括弧書きで示します。

引数のリストが 10000 要素を越えない場合には、通常上のようなことは無視してかまいません。

val length : 'a list -> int
与えられたリストの長さ（要素数）を返します。
val hd : 'a list -> 'a
与えられたリストの先頭要素を返します。リストが空の場合には Failure "hd" 例外が発生します。
val tl : 'a list -> 'a list
与えられたリストから先頭要素を除いたものを返します。リストが空の場合には Failure "tl" 例外が発生します。
val nth : 'a list -> int -> 'a
与えられたリストの n 番目の要素を返します。最初の要素（リストの先頭）を 0 番目とします。 リストが空の場合には Failure "nth" 例外が発生します。
val rev : 'a list -> 'a list
リストの反転。
val append : 'a list -> 'a list -> 'a list
ふたつのリストを連結します。 中置演算子 @ と同じ関数です。 末尾再帰ではありません（最初の引数の長さに比例します）。 @ 演算子も末尾再帰ではありません。
val rev_append : 'a list -> 'a list -> 'a list
List.rev_append l1 l2 は l1 を反転して l2 に連結します。 これは List.rev l1 @ l2 と等価ですが、 rev_append は末尾再帰で、より効率的です。
val concat : 'a list list -> 'a list
リストのリストを連結します。引数リストの要素を（与えられた順番で）連結したものが結果になります。 末尾再帰ではありません（引数リストの長さ + 部分リストの長さの最大値に比例します）。
val flatten : 'a list list -> 'a list
concat と同じです。 末尾再帰ではありません（引数リストの長さ + 部分リストの長さの最大値に比例します）。

繰り返し


val iter : ('a -> unit) -> 'a list -> unit
List.iter f [a1; ...; an] は関数 f を a1; ...; an に順に適用します。 これは begin f a1; f a2; ...; f an; () end と等価です。
val map : ('a -> 'b) -> 'a list -> 'b list
List.iter f [a1; ...; an] は関数 f を a1; ...; an に適用し、 f の戻り値を使ってリスト [f a1; ...; f an] を作成します。 末尾再帰ではありません。
val rev_map : ('a -> 'b) -> 'a list -> 'b list
List.rev_map f l は List.rev (List.map f l) と同じ結果を返しますが、末尾再帰で、より効率的です。
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
List.fold_left f a [b1; ...; bn] は f (... (f (f a b1) b2) ...) bn になります。
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
List.fold_right f [a1; ...; an] b は f a1 (f a2 (... (f an b) ...)) になります。 末尾再帰ではありません。

ふたつのリストに対する繰り返し


val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
List.iter2 f [a1; ...; an] [b1; ...; an] は f a1 b1; ...; f an bn を順に呼び出します。 ふたつのリストの長さが異なる場合は Invalid_argument 例外が発生します。
val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
List.map2 f [a1; ...; an] [b1; ...; bn] は [f a1 b1; ...; f an bn] になります。 ふたつのリストの長さが異なる場合は Invalid_argument 例外が発生します。
val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
List.rev_map2 f l1 l2 は List.rev (List.map2 f l1 l2) と同じ結果を返しますが、末尾再帰で、より効率的です。
val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] は f (... (f (f a b1 c1) b2 c2) ...) bn cn になります。 ふたつのリストの長さが異なる場合は Invalid_argument 例外が発生します。
val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
List.fold_right2 f [a1; ...; an] [b1; ...; bn] c は f a1 b1 (f a2 b2 (... (f an bn c) ...)) になります。 ふたつのリストの長さが異なる場合は Invalid_argument 例外が発生します。 末尾再帰ではありません。

リストの走査


val for_all : ('a -> bool) -> 'a list -> bool
for_all p [a1; ...; an] はリストのすべての要素が述語 p を満たすか検査します。 すなわち、 (p a1) && (p a2) && ... && (p an) を返します。
val exists : ('a -> bool) -> 'a list -> bool
exists p [a1; ...; an] はリストの要素のうち少なくともひとつは述語 p を満たすか検査します。 すなわち、 (p a1) || (p a2) || ... || (p an) を返します。
val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
List.for_all と同じですが、 2 引数の述語を取ります。 ふたつのリストの長さが異なる場合は Invalid_argument 例外が発生します。
val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
List.exists と同じですが、 2 引数の述語を取ります。 ふたつのリストの長さが異なる場合は Invalid_argument 例外が発生します。
val mem : 'a -> 'a list -> bool
mem a l は a が l の要素と等しい場合、かつその場合にかぎり真を返します。
val memq : 'a -> 'a list -> bool
List.mem と同じですが、リストの要素を比較するのに構造等価性ではなく、物理的等価性を使います。

リストの探索


val find : ('a -> bool) -> 'a list -> 'a
find p l はリスト l の要素で、述語 p を満たす最初のものを返します。 リスト l に p を満たす要素がない場合には Not_found 例外が発生します。
val filter : ('a -> bool) -> 'a list -> 'a list
filter p l はリスト l の要素で、述語 p を満たすものをすべて返します。 入力リスト内での要素の順番は保存されます。
val find_all : ('a -> bool) -> 'a list -> 'a list
find_all は List.filter の別名です。
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
partition p l はリストのペア (l1, l2) を返します。 ここで、 l1 は l の要素のうち、述語 p を満す要素のリストで、 l2 は l の要素のうち p を満たさないもののリストです。 入力リスト内での要素の順番は保存されます。

連想リスト


val assoc : 'a -> ('a * 'b) list -> 'b
assoc a l はペアのリスト l 内でキー a に対応する値を返します。 すなわち、 (a, b) がリスト l 内での a の最左の束縛であれば、 assoc a [...; (a, b); ...] = b になります。 リスト l 内に a に対応する値がない場合には Not_found 例外が発生します。
val assq : 'a -> ('a * 'b) list -> 'b
List.assoc と同じですが、キーの比較に構造等価性ではなく物理的等価性を使います。
val mem_assoc : 'a -> ('a * 'b) list -> bool
List.assoc と同じですが、束縛が存在した場合には単純に真を返し、与えられたキーに対する束縛がない場合には偽を返します。
val mem_assq : 'a -> ('a * 'b) list -> bool
List.mem_assoc と同じですが、キーの比較に構造等価性ではなく物理的等価性を使います。
val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
remove_assoc a l はペアのリスト l から、もし存在すれば、キーとして a を持つ最初のペアを除いたものを返します。 末尾再帰ではありません。
val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
List.remove_assoc と同じですが、キーの比較に構造等価性ではなく物理的等価性を使います。 末尾再帰ではありません。

ペアのリスト


val split : ('a * 'b) list -> 'a list * 'b list
ペアのリストをリストのペアに変換します。 split [(a1,b1); ...; (an,bn)] は ([a1; ...; an], [b1; ...; bn]) になります。 末尾再帰ではありません。
val combine : 'a list -> 'b list -> ('a * 'b) list
リストのペアをペアのリストに変換します。 combine [a1; ...; an] [b1; ...; bn] は [(a1,b1); ...; (an,bn)] になります。 ふたつのリストの長さが異なる場合には Invalid_argument 例外が発生します。 末尾再帰ではありません。

整列


val sort : ('a -> 'a -> int) -> 'a list -> 'a list
リストの要素を与えられた比較関数に関して昇順に整列させます。 比較関数は、引数が等しい場合には 0 を返し、第一引数の方が大きい場合には正の整数を、第一引数の方が小さい場合には負の整数を返さなければなりません（完全な仕様については Array.sort を参照してください）。 例えば、 compare は適切な比較関数です。 結果のリストの要素は昇順に整列しています。 List.sort は一定のヒープ空間（に結果のリストのサイズを加えたもの）に対数オーダーのスタック空間で実行できることが保証されています。

現在の実装ではヒープソートを使っていいます。これは一定のヒープ空間に対数オーダーのスタック空間で実行できます。

val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
List.sort と同じですが、整列アルゴリズムが安定であることが保証されています（すなわち、等しい要素の順番はもとのリスト内での前後関係が保存されるということです）。

現在の実装ではヒープソートを使っていいます。これは一定のヒープ空間に対数オーダーのスタック空間で実行できます。

val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
List.sort や List.stable_sort のうち、典型的な入力に対してより高速な方と同じです。
val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
ふたつのリストを併合します。 l1 と l2 が比較関数 cmp に関して整列しているとすると、 merge cmp l1 l2 は l1 と l2 のすべての要素を含む、整列したリストを返します。 等しい要素が複数ある場合には l1 の要素が l2 の要素より先に現れます。 末尾再帰ではありません（引数のリストの長さの和に比例します）。