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
2 つのリストを連結します。中置演算子の @ も同様の関数です。この関数は末尾再帰になっていません (第一引数のリストの長さ) 。@ もまた末尾再帰になっていません。
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 と同じです。この関数は末尾再帰になっていません (引数の長さ + 引数の要素のなかで最長のリストの長さ) 。


Iterators 


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.map f [a1; ...; an] は関数 f を a1, ..., an に適用して、その結果で [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) ...)) です。末尾再帰になっていません。


Iterators on two lists 


val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
List.iter2 f [a1; ...; an] [b1; ...; bn] は f a1 b1; ...; f an bn の順に関数を評価します。2 つのリストの長さが異なる場合、例外 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] です。2 つのリストの長さが異なる場合、例外 Invalid_argument を発生します。この関数は末尾再帰になっていません。
val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
List.rev_map2 f l は List.rev (List.map2 f l) と同じ結果を返しますが、末尾再帰になっていて高速です。
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 です。2 つのリストの長さが異なる場合、例外 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) ...)) です。2 つのリストの長さが異なる場合、例外 Invalid_argument を発生します。この関数は末尾再帰になっていません。


List scanning 


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] はリストの要素に少なくとも 1 つ述語 p を満たすものがあるかどうかチェックします。つまり (p a1) || (p a2) || ... || (p an) を返します。
val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
List.for_all と同じですが、2 引数の述語に使います。2 つのリストの長さが異なる場合、例外 Invalid_argument を発生します。
val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
List.exists と同じですが、2 引数の述語に使います。2 つのリストの長さが異なる場合、例外 Invalid_argument を発生します。
val mem : 'a -> 'a list -> bool
mem a l は l に a と等しい要素が存在するとき、またそのときだけ true を返します。
val memq : 'a -> 'a list -> bool
List.mem と同じですが、リストの要素と比較する際に構造的等価ではなく物理的等価を用います。


List searching 


val find : ('a -> bool) -> 'a list -> 'a
find p l は述語 p を満たす先頭の要素を返します。もし l のなかに p を満たす要素がなかった場合は例外 Not_found を発生します。
val filter : ('a -> bool) -> 'a list -> 'a list
filter p l は述語 p を満たす l の全ての要素を返します。入力リストの要素順序は保存されます。
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 は述語 p を満たす l の全ての要素のリストで、l2 は p を満たさない l の全ての要素のリストです。入力リストの要素順序は保存されます。


Association lists 


val assoc : 'a -> ('a * 'b) list -> 'b
assoc a l はペアのリスト l でキー a に対応する値を返します。つまり assoc a [ ...; (a,b); ...] = b です (ただしリスト l 中で (a,b) が最も左にある a のバインディングであるとします) 。リスト l で a に対応する値がない場合は例外 Not_found を発生します。
val assq : 'a -> ('a * 'b) list -> 'b
List.assoc と同じですが、キーを比較する際に構造的等価ではなく物理的等価を用います。
val mem_assoc : 'a -> ('a * 'b) list -> bool
List.assoc と同じですが、与えられたキーに対応するバインディングが存在する場合は true を、存在しない場合は false を返すだけです。
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 と同じですが、キーを比較する際に構造的等価ではなく物理的等価を用います。この関数は末尾再帰になっていません。


Lists of pairs 


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)] になります。2 つのリストの長さが異なる場合、例外 Invalid_argument を発生します。この関数は末尾再帰になっていません。


Sorting 


val sort : ('a -> 'a -> int) -> 'a list -> 'a list
リストを昇順にソートします。比較関数は引数が同じ時 0 を、1 つ目の要素が大きいときは正の数を、1 つ目の要素が小さい時は負の数を返します (完全な詳細は Array.sort を見てください) 。たとえば、Pervasives.compare は比較関数としてふさわしいです。結果のリストは昇順にソートされています。List.sort は (結果のリストのサイズを加えた) ヒープ量一定で、対数分のスタック量で実行されることが保証されています。

現在の実装はマージソートです。これは一定のヒープ量と対数分のスタック量で実行されます。

val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
List.sort と同じですが、アルゴリズムが stable です (比較が等しいときは元の順を保ちます) 。

現在の実装はマージソートです。これは一定のヒープ量と対数分のスタック量で実行されます。

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
2 つのリストをマージします。l1 と l2 は比較関数 cmp でソートされていることが前提です。merge cmp l1 l2 は l1 と l2 の要素全てを含むソートされたリストを返します。等しい要素がある場合、l1 の要素が l2 の要素より先に配置されます。この関数は末尾再帰になっていません (引数のリストの和) 。