配列

前の章で、参照はサイズが 1 の配列であると説明しました。 サイズ n の配列とは連続して確保された n 個の参照であると言うこともできます。 これらの参照はセルとも呼ばれ、それらは 0 から n-1 までの番号が付けられています。

サイズ n の配列が与えられた時、n よりも小さい自然数であれば、その整数値はこの配列に対する有効なインデックスです。 そうでない場合、その整数値は配列の範囲の外を指すことになります。 A という名前のついた配列について、i が A に対する有効なインデックスである場合、 A[i] 式はAの i 番目のセルの中身を取り出します。 A[i] 式は左辺値として使うこともできます。 例えば (A[i] := exp) という代入は exp を評価して値にした後、i が有効なインデックスであればその値を A の i 番目のセルに書き込みます。

もし A[i] のインデックス i が有効でなかったら、つまり配列 A の範囲外であったら何が起きるのでしょうか？ この場合、A[i] は out-of-bounds array subscription と呼ばれ、 A[i] の評価は ArraySubscriptExn() 例外を引き起こします。 与えられた配列に対して整数値が有効なインデックスであるかどうか判定する簡単で確実な方法の一つは、 実行時に配列 のサイズと比較することです。 型 T が与えられた時、型 arrszref(T) は配列と型 T の要素が収められているサイズのペアです。 これ以降、 arrszref(T) 型の値のことを漠然と配列を呼びます。 また、混乱する可能性を避けるために、array0 値と呼ぶこともあります。

array0 値に関する様々な関数と関数テンプレートが arrayref.sats ファイルで宣言されています。 このファイルは atsopt によって自動的に読み込まれます。 例えば、配列に関する3つの関数テンプレートと1つの多相関数が次のインターフェイスで表現されます:

//
fun{a:t@ype} // template
arrszref_make_elt
  (asz: size_t, x: a): arrszref a // array creation
//
// polymorphic fun:
//
fun arrszref_get_size
  {a:t@ype} (A: arrszref a): size_t // size of an array
//
fun{a:t@ype} // template
arrszref_get_elt_at (A: arrszref a, i: size_t): a // A[i]
//
fun{a:t@ype} // template
arrszref_set_elt_at (A: arrszref a, i: size_t, x: a): void // A[i] := x
//

C言語と同じように、ATS言語には多くの整数型があります。 size_t 型は本質的に unsigned long の整数です。 int と size_t を相互に変換する関数は g0int2uint_int_size と g0uint2int_size_int です。 型 T と型 size_t と T の値としてそれぞれ asz と init が与えられたとき、 arrszref_make_elt<T> (asz, init) は arrszref(T) 型の配列を返します。 この配列のサイズは asz で、それぞれのセルは値 init で初期化されます。 型 T と型 arrszref(T) の配列 A が与えられた時、 arrszref_get_size(A) は A のサイズを型 size_t で返します。 利便性のために arrszref_get_size(A) は A.size と書くこともできます。 配列へのアクセスと更新のために、 関数 arrszref_get_elt_at と arrszref_set_elt_at を呼び出すことができます。 利便性のために、これらの関数を角括弧表記で呼び出すこともできます。

次のプログラムでは、 一般的な配列の挿入ソートを関数テンプレート insertion_sort として実装しています:

fun{
a:t@ype
} insertion_sort
(
  A: arrszref (a)
, cmp: (a, a) -> int
) : void = let
  val n = g0uint2int_size_int (A.size)
  fun ins (x: a, i: int):<cloref1> void =
    if i >= 0 then
    (
      if cmp (x, A[i]) < 0
        then (A[i+1] := A[i]; ins (x, i-1)) else A[i+1] := x
      // end of [if]
    ) else A[0] := x // end of [if]
  // end of [ins]
  fun loop (i: int):<cloref1> void =
    if i < n then (ins (A[i], i-1); loop (i+1)) else ()
  // end of [loop]
in
  loop (1)
end // end of [insertion_sort]

この章に出てくるコードの全体とテストのための追加コードは オンライン から得られます。