Array

このページは最後に更新されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

Chapter 20 標準ライブラリ

module Array: sig .. end

配列処理です。

---

val length : 'a array -> int

与えられた配列の長さ (要素数) を返します。

val get : 'a array -> int -> 'a

Array.get a n は配列 a の n 番目の要素を返します。先頭の要素は 0 番目で、終端の要素は Array.length a - 1 番目になります。

n が 0 から (Array.length a - 1) の範囲内にない場合、例外 Invalid_argument "Array.get" を発生します。Array.get a n と書く代わりに、a.(n) と書くことも出来ます。

val set : 'a array -> int -> 'a -> unit

Array.set a n x は配列 a の n 番目の要素を x と置き換えます。

n が 0 から (Array.length a - 1) の範囲内にない場合、例外 Invalid_argument "Array.set" を発生します。Array.set a n x と書く代わりに、a.(n) <- x と書くことも出来ます。

val make : int -> 'a -> 'a array

Array.make n x は x で初期化された、長さ n の新規配列を返します。この配列の全ての要素は物理的に x と等値 (つまり ==) です。よって x が可変 (mutable) だった場合、x の内容は配列のすべての要素が共有するので、x を書き換えると同時に他すべての要素も書き換えられます。

n < 0 や n > Sys.max_array_length だった場合、例外 Invalid_argument を発生します。x が浮動小数だった場合、配列の最大長は Sys.max_array_length / 2 になります。

val create : int -> 'a -> 'a array

推奨されていません (Deprecated) 。 Array.create は Array.make に飛ばされます (alias) 。

val init : int -> (int -> 'a) -> 'a array

Array.init n f は長さ n の配列を返します。i 番目の要素には f i の結果が初期値として入っています。 つまり、Array.init n f は f に整数 0 to n-1 を適用した結果を並べます。

n < 0 や n > Sys.max_array_length だった場合、例外 Invalid_argument を発生します。f の出力する型が float だった場合は、配列の最大長は Sys.max_array_length / 2 になります。

val make_matrix : int -> int -> 'a -> 'a array array

Array.make_matrix dimx dimy e は dimx × dimy サイズの 2 次元配列 (配列の配列) を返します。要素はすべて e と物理的に等しいです。(x,y) の要素は m.(x).(y) としてアクセス出来ます。

dimx や dimy が負であったり Sys.max_array_length より大きかったりする場合は例外 Invalid_argument を発生します。e が浮動小数だった場合、配列の最大長は Sys.max_array_length / 2 になります。

val create_matrix : int -> int -> 'a -> 'a array array

推奨されていません (Deprecated) 。 Array.create_matrix は Array.make_matrix に飛ばされます (alias) 。

val append : 'a array -> 'a array -> 'a array

Array.append v1 v2 は配列 v1 と配列 v2 を結合した新規配列を返します。

val concat : 'a array list -> 'a array

Array.append と同じですが、こちらは配列のリストの各要素 (配列) を結合した新規配列を返します。

val sub : 'a array -> int -> int -> 'a array

Array.sub a start len は配列 a の start 番目から start + len - 1 番目までの要素を長さ len の新規配列にして返します。

start と len が a の部分配列としてとれないような値の場合、つまり 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 の ofs 番目から ofs + len - 1 番目の要素までを x に書き換えます。

ofs と len が a の部分配列としてとれないような値の場合、例外 Invalid_argument "Array.fill" を発生します。

val blit : 'a array -> int -> 'a array -> int -> int -> unit

Array.blit v1 o1 v2 o2 len は、配列 v1 の o1 番目の要素から len 個分の要素を読み、配列 v2 の o2 番目の要素から len 個分の要素へ上書きします。この関数は配列 v1 と配列 v2 が同じ配列で、読み込み元と書き込み先が重なっていても正常に動作します。

o1 と len が v1 の部分配列としてとれないような値の場合や、o2 と len が v2 の部分配列としてとれないような値の場合、例外 Invalid_argument "Array.fill" を発生します。

val to_list : 'a array -> 'a list

Array.to_list a は配列 a のすべての要素をリストにして返します。

val of_list : 'a list -> 'a array

Array.of_list l はリスト l のすべての要素を新規配列にして返します。

val iter : ('a -> unit) -> 'a array -> unit

Array.iter f a は配列 a のすべての要素に f を適用します。f a.(0); f a.(1); ...; f a.(Array.length a - 1); () と同値です。

val map : ('a -> 'b) -> 'a array -> 'b array

Array.map f a は配列 a のすべての要素に f を適用し、その結果を配列にして返します。[| f a.(0); f a.(1); ...; f a.(Array.length a - 1) |] と同値です。

val iteri : (int -> 'a -> unit) -> 'a array -> unit

Array.iter と同じですが、1 つ目の引数には要素のインデックスを、2 つ目の引数に要素を入れて関数を呼び出します。

val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array

Array.map と同じですが、1 つ目の引数には要素のインデックスを、2 つ目の引数に要素を入れて関数を呼び出します。

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a

Array.fold_left f x a は f (... (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 x は f a.(0) (f a.(1) ( ... (f a.(n-1) x) ...)) を計算します (n は配列 a の長さです) 。

Sorting

val sort : ('a -> 'a -> int) -> 'a array -> unit

配列を昇順にソートします。比較関数は引数が同じ時 0 を、1 つ目の要素が大きいときは正の数を、1 つ目の要素が小さい時は負の数を返します (比較関数の詳細は後述) 。たとえば、Pervasives.compare は適切な比較関数です (データのなかに浮動小数の NaN 値がない場合ですが) 。Array.sort を実行すると、配列は昇順にソートされて置き換えられます。Array.sort はヒープ量一定で、(最大でも) 対数分のスタック量で実行されることが保証されています。

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

比較関数を詳しく説明します。a を配列、cmp を比較関数としたとき、配列 a の要素 x 、y 、z に対して次の 2 つの条件が常に成り立つ必要があります。

• cmp y x < 0 が成り立ち、また成り立つときに限り cmp x y > 0 が成り立つ
• cmp x y >= 0 と cmp y z >= 0 が成り立つ時 cmp x z >= 0 が成り立つ

Array.sort が終了すると、配列 a は以前と同じ要素を、すべてのインデックス i と j に対して以下が成り立つように再配置されています。

• i >= j が成り立ち、また成り立つときに限り cmp a.(i) a.(j) >= 0

val stable_sort : ('a -> 'a -> int) -> 'a array -> unit

Array.sort と同じですが、アルゴリズムが stable です (比較が等しいときは元の順を保ちます) 。また、ヒープ量が一定であることを保証していません。

現在の実装はマージソートです。これは配列の長さを n として、n/2 ワード分のヒープ量で実行されます。こちらのほうが大抵の場合において現在の Array.sort の実装より速いです。

val fast_sort : ('a -> 'a -> int) -> 'a array -> unit

典型的な入力に対して Array.sort か Array.stable_sort の速い方と同じ処理をします。