top page > computer > haskell > web_lecture > for_programmer > binary_tree.html
更新日:
文責: 重城良国

二分樹を下にたどる

binaryTree.hs

はじめに

制御の流れが1本道の再帰「くりかえし」は生の再帰を使わなくてもリストによる「列挙-蓄積」の枠組みで書ける。生の再帰の力を知るために制御の流れが樹構造になるような再帰関数を学ぶ。

仕様

二分樹のあるノードから別のノードにたどりつけるかどうかを判定する関数を作成する。樹の各ノードは2つの枝を出すか、またはひとつも枝を出さないかのどちらかだ。下向きにしか進めないものとする。

[樹のサンプルの画像]

図に書いた例ではbからfには行けるがcからfには行けない。樹をうえにはたどれないのでcからaにもどれないからだ。

樹の表現

樹のノードは1文字で表現する。樹は各ノードから出る枝の集合とする。同じノードから出る枝はまとめて書く。上の例のaからbとcに枝が出ていることを('a', ('b', 'c'))のように表現する。

[('a', ('b', 'c')), ('b', ('d', 'e')), ('e', ('f', 'g'))]

型は[(Char, (Char, Char))]だ。これに別名をつける。型の別名には以下の構文を使う。

type [型の別名] = [型]

樹を表現する型の別名を型Treeとする。

type Tree = [(Char, (Char, Char))]

サンプルの樹も定義しておく。

sampleTree :: Tree
sampleTree = [('a', ('b', 'c')), ('b', ('d', 'e')), ('e', ('f', 'g'))]

次を見つける

樹を下にたどっていくために、あるノードから出る枝の先にあるノードを求める。例示した樹では引数'b'に対して'd'と'e'を返してほしい。Tree型の値を辞書として考える。辞書から鍵に対応する値をとりだせれば良い。タプルのリストを辞書と考えたときに値を引き出す関数lookupがある。

% ghci binaryTree.hs
*Main> lookup 'b' sampleTree
Just ('d', 'e')
*Main> lookup 'e' sampleTree
Just ('f', 'g')
*Main> lookup 'd' sampleTree
Nothing

ノードbからはdとeに枝がのび、ノードeからはfとgに枝がのびている。ノードdの下には枝がないのでNothingとなる。

作成する関数の型

樹を指定しあるノードからもうひとつのノードへと行けるかどうかを求める関数を作りたい。

reachable [樹] [始点] [終点] => [真偽値]

型は以下のようになる。

reachable :: Tree -> Char -> Char -> Bool

基底部

基底部とは再帰しない部分だ。再帰的に定義する必要のない部分である。今回の例での基底部は以下の2つだ。

それぞれの基底部を書いてみよう。始点と終点が同じときをガードを使って書く。

reachable _ s e | s == e = True

始点からの枝が存在しない場合をcase式のなかに書く。

reachable t s e = case lookup s t of
Nothing -> False

再帰部

考えかた

点Xからの直接の枝が点Y, Zにのびているとき、点Yまたは点Zから点Wまでの経路があれば、点Xから点Wまでの経路は存在する。

コード

case文のなかに以下を書き足せば良い。

Just (l, r) -> reachable t l e || reachable t r e

試してみる

% ghci binaryTree.hs
*Main> reachable sampleTree 'b' 'g'
True
*Main> reachable sampleTree 'c' 'f'
False

まとめ

処理の流れが樹構造となる再帰関数の例を学んだ。「生の再帰」が威力を発揮する。

「ライプニッツの公式」へもどる 「リストのパターンマッチ」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics