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

例: ブラウンツリーの判定

ブラウンツリー (Braun Trees) は、次のような再帰的な定義によって導かれる特殊な二分木です:

自然数 n が与えられた時、サイズ n のブラウンツリーは唯一1つだけ存在します。 ブラウンツリーが平衡であることは自明でしょう。

次のような二分木を表わす多相データ型を宣言します: 

datatype tree (a:t@ype) =
  | tree_nil of ((*void*))
  | tree_cons of (a, tree(a)(*left*), tree(a)(*right*))
// end of [tree] // end of [datatype]

次に宣言する関数 brauntest0 は、与えられた二分木がブラウンツリーかどうか判定します: 

fun{
a:t@ype
} size (t: tree a): int = case+ t of
  | tree_nil () => 0
  | tree_cons (_, tl, tr) => 1 + size(tl) + size(tr)
// end of [size]

fun{
a:t@ype
} brauntest0
  (t: tree a): bool =
(
case+ t of
| tree_nil () => true
| tree_cons (_, tl, tr) => let
    val cond1 = brauntest0(tl) andalso brauntest0(tr)
  in
    if cond1 then let
      val df = size(tl) - size(tr) in (df = 0) orelse (df = 1)
    end else false
  end // end of [tree_cons]
) (* end of [brauntest0] *)

brauntest0 の実装はブラウンツリーの定義に厳密に従っています。 サイズ n の二分木を判定すると、関数 size の時間的計算量は O(n) であり、 関数 brauntest0 の時間的計算量は O(n(log(n))) です。

次のプログラムで定義している brauntest1 関数もまた与えられた二分木がブラウンツリーか判定しています: 

fun{
a:t@ype
} brauntest1
  (t: tree a): bool = let
  exception Negative of ()
  fun aux (t: tree a): int =
  (
    case+ t of
    | tree_nil () => 0
    | tree_cons (_, tl, tr) => let
        val szl = aux (tl) and szr = aux (tr)
        val df = szl - szr
      in
        if df = 0 orelse df = 1 then 1+szl+szr else $raise Negative()
      end // end of [tree_cons]
  ) (* end of [aux] *)
in
  try let
    val _ = aux (t)
  in
    true // [t] is a Braun tree
  end with
    ~Negative() => false // [t] is not a Braun tree
  // end of [try]
end // end of [brauntest1]

子ツリーの内1つでもブラウンツリーでなければ、その二分木はブラウンツリーでないことは明確です。 補助関数 aux は、ツリーがブラウンツリーである場合には二分木のサイズを返し、そうでない場合には例外を発生させるために定義されています。 brauntest1 の中身にある try 式の評価が開始すると、まずはじめに二分木に対して aux を呼び出します。 もしこの呼び出しの評価が返れば t はブラウンツリーであるので、try 式の値としてブール値 true が返ります。 そうでなければ、Negative() 例外が発生して捕捉され、try 式の値としてブール値 false が返ります。 brauntest1 と aux の時間的計算量はどちらも O(n) です。

brauntest1 の実装における例外機構の使い方は妥当なものです。 なぜなら例外が発生するポイントから例外が捕捉されるポイントまでの範囲に多くの関数呼び出しがあるからです。 もしこの範囲が短かい場合 (例えばたった1つの関数しか呼び出さないなど)、おそらくプログラマは例外機構を使うべきか吟味すべきでしょう。 例えば、次の例における例外の使い方は興味深いものですが、実際には役に立ちません： 

fun{
a:t@ype
} list0_length
  (xs: list0 (a)): int =
  try 1 + list0_length (xs.tail()) with ~ListSubscriptExn() => 0
// end of [list0_length]

そのため、このような例外の使い方は避けるべきでしょう。

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

PrevHomeNext
効果 (effect) を持つプログラミングの機能Up参照