Haskell あれこれ 再帰の種類 (木構造型)

3.木構造型

普通の用途でプログラムするときに、木構造のデータを使うような機会はあまりない。人工知能や、プログラム言語のパーサなどで利用されるデータ型だ。したがって、木構造が何かという説明はここではしない。Scheme などでは木構造はリストで表現するが、Haskell の場合はユーザデータ型の定義が必要だ。

単純な二分木構造で、ノードに値を持つ木構造は、Haskell では次のように定義する。

data Tree = Leaf Int | Node Tree Int Tree
  deriving Show

うえの定義の Tree はタイプコンストラクタで関数の型宣言の時に使われる。Leaf と Node はデータコンストラクタで引数を取る関数のようにふるまう。例えば、Leaf 1 とするとノードの値が1の葉のデータを生成し、Node (Leaf 1) 2 (Leaf 3) とすると、ノードの値が2で左の枝に値1の葉がつながり、右の枝に値3の枝がつながるノードを生成する。

データの宣言で等号の左側にも Tree 型が使われているのに注意してほしい。Haskell ではデータもまた、再帰的に定義できる。Node型は、その中にTree型の左の部分木、ノードの値、Tree型の右の部分木を収めている。

また、deriving Show として、Tree データ型を Show クラスのインスタンスに登録しておくと、Hugs のコンソールでデータを表示できるようになる。このようにしてできる木構造を次に示す。

木構造型データの例
Main> (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5)))
Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5))

この木構造を処理するプログラムも再帰的プログラムになることが多い。左の枝を処理したあと、右の枝を処理する、その枝についてもそのノードについて同じ処理を左と右の枝に加える... というような同じ操作を次々に下位レベルのノードについて加えていくからだ。

数値型やリスト型の再帰関数については3つの要件があった。すなわち、1)終了条件(base case)があること、2)関数が再帰的に定義されていること(recursive case)、3)左側の引数の値が右に比べ減少(reduce)していることだ。このうちリスト構造と前二者の場合の違いは、リストのデータが枝分かれしているということだ、引数の減少は右と左の枝の両方にわかれて行われる。このため、再帰的定義の関数名は、等号の左側で2回現れることになる。

文章では分かりにくいので、木構造型を再帰的に処理する関数の例として、ノードの値をすべて集めてリストにする関数 flatten を作ってみる。

flatten :: Tree -> [Int]
flatten (Leaf n) = [n]
flatten (Node l n r) = flatten l ++ [n] ++ flatten r

実行例
Main> flatten (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5)))
[1,2,3,4,5]

上のプログラムで、2行目が終了条件だ。葉のノードは枝をもたないのでそれ以上は枝をたどれない。3行目が flatten 関数の再帰的定義で、ノードから左の部分木とノードの値と右のの部分木をとりだし、左の部分木にflatten を適用した、flatten l の戻り値のリストとノードの値のリストと、右の部分木の flatten r の戻り値のリストを連結している、引数の減少については、現在のノードを処理して残りの左右の部分木に flatten を適用するので、左側では木構造データからノードが一つ取り去られている勘定になる。

例によって再帰関数の動作を展開によって追いかけてみよう。ただし、木構造の表示は Haskell 流だと煩雑なので、Scheme 流のリストで表現する。

flatten ((1) 2 ((3) 4 (5)))
= flatten (1) ++ [2] ++ flatten ((3) 4 (5))
= [1] ++ [2] ++ (flatten (3) ++ [4] ++ flatten (5))
= [1] ++ [2] ++ ([3] ++ [4] ++ [5])
= [1,2,3,4,5]

このように再帰関数の動作は数式の展開と同一視してイメージしておくとその動作がよく理解できる。

このように、木構造の再帰関数は、等号の左側に関数名が2回現れるので混乱するが、再帰関数の終了条件、再帰的定義、引数の減少の3点をおさえていれば動作の理解がしやすい。
[PR]
by tnomura9 | 2009-08-21 11:24 | Haskell | Comments(0)
<< Haskel あれこれ 型 Haskell あれこれ 再帰... >>