Module Array


module Array: sig .. end
配列の操作

val length : 'a array -> int
与えられた配列の長さ(要素数)を返します。
val get : 'a array -> int -> 'a
Array.get a n は配列 an 番目の要素を返します。 最初の要素は 0 番目で、最後の要素は Array.length a - 1 番目です。 Array.get a n の代わりに a.(n) と書くこともできます。

n が 0 から (Array.length a - 1) の範囲にない場合には Invalid_argument "index out of bounds" 例外が発生します。

val set : 'a array -> int -> 'a -> unit
Array.set a n xa を破壊的に変更し、 n 番目の要素を x で置き換えます。 Array.set a n x の代わりに a.(n) <- x と書くこともできます。

n が 0 から (Array.length a - 1) の範囲にない場合には Invalid_argument "index out of bounds" 例外が発生します。

val make : int -> 'a -> 'a array
Array.make n x は長さ n の配列を新たに作り、その要素を x で初期化します。 この配列の要素はすべて x と(述語 == の意味で)物理的に等価です。 そのため、 x が変更可能な場合、 x はこの配列の全要素で共有されるため、 配列の要素のいずれかを介して x を変更すると配列の要素がすべて同時に変更されます。

n < 0n > Sys.max_array_length の場合には Invalid_argument 例外が発生します。 xfloat 型である場合には、配列の最大サイズは Sys.max_array_length / 2 になります。

val create : int -> 'a -> 'a array
Deprecated.Array.createArray.make の別名です。
val init : int -> (int -> 'a) -> 'a array
Array.init n f は長さ n の配列を作成し、 i 番目の要素を f i の戻り値で初期化します。 言い換えると、 f を整数 0 から n - 1 に適用して、その結果を表にします。

n < 0n > Sys.max_array_length の場合には Invalid_argument 例外が発生します。 xfloat 型である場合には、配列の最大サイズは Sys.max_array_length / 2

val make_matrix : int -> int -> 'a -> 'a array array
Array.make_matrix dimx dimy は、最初の次元が dimx、二番目の次元が dimy であるような二次元配列(配列の配列)を返します。 この行列の要素はすべて e に物理的に等価な要素で初期化されます。 行列 m(x, y) 要素は m.(x).(y) でアクセスできます。

dimxdimy のいずれかが負であるか Sys.max_array_length より大きい場合には Invalid_argument 例外が発生します。 e の値が浮動小数点数であった場合には、最大要素数は Sys.max_array_length / 2 になります。

val create_matrix : int -> int -> 'a -> 'a array array
Deprecated.Array.create_matrixArray.make_matrix の別名です。
val append : 'a array -> 'a array -> 'a array
Array.append v1 v2 は配列 v1v2 を連結した新しい配列を返します。
val concat : 'a array list -> 'a array
Array.append と同じですが、配列のリストを連結します。
val sub : 'a array -> int -> int -> 'a array
Array.sub a start len は、長さ len で、配列 astart 番目から start + len - 1 番目の要素までを含む新しい配列を返します。

startlena の有効な部分配列を表さない場合、すなわち、 start < 0 である場合や、 len < 0 の場合、 start + len > Array.length a である場合には Invalid_argument "Array.sub" 例外が発生します。

val copy : 'a array -> 'a array
Array.copy a は配列 a のコピー、すなわち、 a と同じ要素を格納した新しい配列を返します。
val fill : 'a array -> int -> int -> 'a -> unit
Array.fill a ofs len x は配列 a を破壊的に変更し、 aofs から ofs + len - 1 番目に x を格納します。

ofslena の有効な部分配列を表さない場合には Invalid_argument "Array.fill" 例外が発生します。

val blit : 'a array -> int -> 'a array -> int -> int -> unit
Array.blit v1 o1 v2 o2 len は配列 v1o1 番目の要素から len 個の要素を、配列 v2o2 番目にコピーします。 この関数は v1v2 が同一の配列で、コピー元とコピー先の区間に重なりがあった場合にも正しく動作します。

o1lenv1 の有効な部分配列を表さない場合や、 o2lenv2 の有効な部分配列を表さない場合は Invalid_argument "Array.blit" 例外が発生します。

val to_list : 'a array -> 'a list
Array.to_list aa の全要素のリストを返します。
val of_list : 'a list -> 'a array
Array.of_list ll のすべての要素を格納した新たな配列を返します。
val iter : ('a -> unit) -> 'a array -> unit
Array.iter f a は関数 fa のすべての要素に順に適用します。 これは、 f a.(0); f a.(1); ...; f a.(Array.length a - 1); () と等価です。
val map : ('a -> 'b) -> 'a array -> 'b array
Array.map f aa の全要素に関数 f を適用し、その戻り値で配列を作ります。 [| f a.(0); f a.(1); ...; f a.(Array.length a - 1) |] と等価です。
val iteri : (int -> 'a -> unit) -> 'a array -> unit
Array.iter と同じですが、関数の第一引数として要素の添字を渡し、第二引数として要素自体を渡します。
val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
Array.map と同じですが、関数の第一引数として要素の添字を渡し、第二引数として要素自体を渡します。
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
Array.fold_leftf (... (f (f x a.(0)) a.(1)) ...) a.(n-1) を計算します。 ここで n は配列 a の長さです。
val fold_right : ('a -> 'b -> 'b) -> 'a array -> 'b -> 'b
Array.fold_right f a xf a.(0) (f a.(1) ( ... (f a.(n-1) x) ...)) を計算します。 ここで n は配列 a の長さです。

整列


val sort : ('a -> 'a -> int) -> 'a array -> unit
配列を比較関数に関して昇順に整列させます。 比較関数は引数が等しい場合には 0 を返し、第一引数がより大きい場合には正の整数を返し、第一引数がより小さい場合には負の整数を返さなければなりません(完全な仕様については下を見て下さい)。 例えば compare は、浮動小数点数の NaN がデータに現れない場合には適切な比較関数です。 Array.sort を呼び出すと、配列は昇順に破壊的に変更されます。 Array.sort は一定のヒープ空間を使い、(最悪の場合)対数オーダーのスタック空間を使います。

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

比較関数の仕様: a を配列とし、 cmp を比較関数とします。 a 中のすべての xyx について以下を満たさなければなりません。

Array.sort から返ると、 a はもとと等しい要素を格納し、有効な添字 i、 j について要素が次の条件を満たすように並べ換えられたものになります。


val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
Array.sort と同じですが、整列アルゴリズムが安定で(すなわち、等しいと判定された要素はもとの順序が保たれます)、一定のヒープ空間で実行できることが保証されません。

現在の実装はマージソートです。 この実装は、配列の長さを n としたとき、 n / 2 語のヒープ空間を使います。 多くの場合、 Array.sort の実装よりも高速です。

val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
Array.sortArray.stable_sort のうち、典型的な入力に対してより高速な方と同じです。