ATSプログラミング入門:
Prev	Chapter 6. 効果 (effect) を持つプログラミングの機能	Next

例: 順序をつけた置換 (Ordering Permutations)

自然数 n が与えられた時、1 から n までの整数からなる置換 (permutation) をすべて印字することを考えます。さらに、整数列を辞書順で印字したいとしましょう。例えば n が 3 の時、次のような出力が得られることを期待しています：

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

次のような整数の配列を印字する関数を定義しましょう:


fun print_intarray
  (A: arrszref (int)): void = let
  val asz = g0uint2int_size_int (A.size)
//
// The integers are to be separated by the string [sep]
//
  fun loop (i: int, sep: string):<cloref1> void =
    if i < asz then
      (if i > 0 then print sep; print A[i]; loop (i+1, sep))
    // end of [if]
in
  loop (0, ", ")
end // end of [print_intarray]

次に、与えられた配列の要素を再配置するために、 2つの関数 lrotate と rrotate を実装します:

fun lrotate (
  A: arrszref int, i: int, j: int
) : void = let
  fun lshift (
    A: arrszref int, i: int, j: int
  ) : void =
  if i < j then (A[i] := A[i+1]; lshift (A, i+1, j))
in
  if i < j then let
    val tmp = A[i] in lshift (A, i, j); A[j] := tmp
  end // end of [if]
end // end of [lrotate]

fun rrotate (
  A: arrszref int, i: int, j: int
) : void = let
  fun rshift (
    A: arrszref int, i: int, j: int
  ) : void =
  if i < j then (A[j] := A[j-1]; rshift (A, i, j-1))
in
  if i < j then let
    val tmp = A[j] in rshift (A, i, j); A[i] := tmp
  end // end of [if]
end // end of [rrotate]

配列と2つの有効なインデックスiとjに適用され、i が j 以下であるとき、 lrotate はいっせいにセル i の中身をセル j へ移動し、セル k の中身をセル k-1 へ移動します。このとき k は i+1 から j の範囲の数値です。 rrotate 関数は要素を反対方向に移すことを除いて、 lrotate に似ています。

自然数 n が与えられたとき、次に定義する関数 permute は 1 から n までの整数からなるすべての置換を印字します。このとき出力は整数列の辞書順で並べられます。

fun permute
  (n: int): void = let
//
  #define i2sz g0int2uint_int_size
//
// Creating array A of size n
//
  val A = arrszref_make_elt<int> (i2sz(n), 0)
//
// Initializing A with integers from 1 to n, inclusive
//
  val () = init(0) where
  {
    fun init (i: int): void =
      if i < n then (A[i] := i+1; init (i+1))
  } // end of [where] // end of [val]
//
  fun aux
    (i: int): void =
  (
    if i <= n
      then aux2 (i, i)
      else (
        print_intarray (A); print_newline ()
      ) (* end of [else] *)
  ) (* end of [aux] *)
//
  and aux2
    (i: int, j: int): void =
  (
    if j <= n then let
      val () = (
        rrotate (A, i-1, j-1); aux (i+1); lrotate (A, i-1, j-1)
      ) // end of [val]
    in
      aux2 (i, j+1)
    end // end of [if]
  ) (* end of [aux2] *)
//
in
  aux (1)
end // end of [permute]

where はキーワードで、なんらかの式 exp と宣言の列 decseq があるとき式 (exp where { decseq }) はlet式 (let decseq in exp end) と等価であることに注意してください。関数 aux の挙動を理解するために、 n が 4 で、配列 A の4つの要素が 1, 2, 3, 4 であるとき、 aux(1) を評価してみましょう。この評価によって aux(2) の評価が4回起きることは簡単に理解できるでしょう: 1度目では配列 A は (1, 2, 3, 4) を含み、 2度目では (2, 1, 3, 4)、 3度目では (3, 1, 2, 4)、 4度目では (4, 1, 2, 3) を含みます。再帰呼び出しによって、 aux(1) の評価が、すべての置換を整数列の辞書順で印字するのを理解するのは難しくないでしょう。

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

Prev	Home	Next
配列	Up	行列