ATSプログラミング入門:
Prev	Chapter 15. 線形データ型としてのデータ観型 (dataviewtype)	Next

例: 線形リストのマージソート

配列の要素をソートするためにマージソートをすると、要素を移動させるために配列のサイズに比例した追加のメモリが必要になります。これはマージソートの重大な欠点と考えられます。けれども、線形リストに対するマージソートにはこのような要求はありません。 C言語の相当する実装に時間効率と空間効率の両面で匹敵できるような、線形リストのマージソートを次に示します。この実装にて捕捉された不変条件とその捕捉の容易さは、現実のプログラミングにおいて ATS が高い正確さを強制できるプログラミング言語であることを実証する大きな証拠です。

はじめに、ソートするリストの要素を比較する関数テンプレートの型定義とインターフェイスを導入しましょう:

//
typedef cmp (a:t@ype) = (&a, &a) -> int
//
fun{a:t@ype} compare (x: &a, y: &a, cmp: cmp (a)): int
//

マージソートのインターフェイスは次のように与えられます:

fun{
a:t@ype
} mergeSort{n:nat}
  (xs: list_vt (a, n), cmp: cmp a): list_vt (a, n)
// end of [mergeSort]

mergeSort の1番目の引数は (ソートする) 線形リストで、2番目の引数は線形リストの要素を比較するための関数です。明確に、mergeSort のインターフェイスは mergeSort が1番目の引数を消費してから、1番目の引数と同じ長さの線形リストを返すことを示しています。明確になったように、返される線形リストは消費されたリストのノードでコンストラクトされたことになります。特に、次に与えられた mergeSort の実装はどのようなメモリの確保/解放も必要としません。

2つのソート済みリストを1つにマージする関数テンプレートは次のように与えられます:

fun{
a:t@ype
} merge{m,n:nat} .<m+n>.
(
  xs: list_vt (a, m), ys: list_vt (a, n)
, res: &List_vt(a)? >> list_vt (a, m+n)
, cmp: cmp a
) : void =
  case+ xs of
  | @list_vt_cons (x, xs1) => (
    case+ ys of
    | @list_vt_cons (y, ys1) => let
        val sgn = compare<a> (x, y, cmp)
      in
        if sgn <= 0 then let // stable sorting
          val () = res := xs
          val xs1_ = xs1
          prval () = fold@ (ys)
          val () = merge<a> (xs1_, ys, xs1, cmp)
        in
          fold@ (res)
        end else let
          val () = res := ys
          val ys1_ = ys1
          prval () = fold@ (xs)
          val () = merge<a> (xs, ys1_, ys1, cmp)
        in
          fold@ (res)
        end // end of [if]
      end (* end of [list_vt_cons] *)
    | ~list_vt_nil () => (fold@ (xs); res := xs)
    ) // end of [list_vt_cons]
  | ~list_vt_nil () => (res := ys)
// end of [merge]

以前の紹介した関数実装と異なり、merge のこの実装は末尾再帰です。そのため ATS コンパイラはC言語のループに変換します。つまり、スタックオーバフローの可能性のために (例: 百万個の要素を含むような) とても長いリストを扱えないような心配はこの merge にはありません。

次の関数テンプレートは与えられた線形リストを2つに分割します:

fun{
a:t@ype
} split{n,k:nat | k <= n} .<n-k>.
(
  xs: &list_vt (a, n) >> list_vt (a, n-k), nk: int (n-k)
) : list_vt (a, k) =
  if nk > 0 then let
    val+@list_vt_cons(_, xs1) = xs
    val res = split<a> (xs1, nk-1); prval () = fold@(xs)
  in
    res
  end else let
    val res = xs; val () = xs := list_vt_nil () in res
  end // end of [if]
// end of [split]

split の実装もまた末尾再帰であることに注意してください。

次の関数テンプレート msort は線形リストとその長さ、比較関数を取り、そして与えられた線形リストをソートしたものを返します:

fun{
a:t@ype
} msort{n:nat} .<n>.
(
  xs: list_vt (a, n), n: int n, cmp: cmp(a)
) : list_vt (a, n) =
  if n >= 2 then let
    val n2 = half(n)
    val n3 = n - n2
    var xs = xs // lvalue for [xs]
    val ys = split<a> (xs(*cbr*), n3)
    val xs = msort<a> (xs, n3, cmp)
    val ys = msort<a> (ys, n2, cmp)
    var res: List_vt (a) // uninitialized
    val () = merge<a> (xs, ys, res(*cbr*), cmp)
  in
    res
  end else xs
// end of [msort]

msort を再帰呼び出しする際、ソートされるリストの長さをそのリストを辿って直接算出する必要がないように、msort の2番目の引数が渡されます。

最後に、mergeSort は msort 呼び出しを使って実装できます:

implement{a}
mergeSort (xs, cmp) = msort<a> (xs, length (xs), cmp)

split と merge の実装を調べてみると、mergeSort が安定ソートになっていることがすぐにわかります。つまり、ソートしている間に、等しい要素群の順序は保存されています。

この章で紹介したコード全体と追加のテストコードはオンラインから入手できます。

Prev	Home	Next
線形リスト	Up	例: 線形リストの挿入ソート