二分木探索

Haskell の魅力は、木構造のデータのすべてを簡単に再帰的に探索できることだ。

しかし、木構造を扱うプログラムを Haskell 初心者が作るのは難しい。そこで、節や葉に全くデータを持たない二分木のデータを定義して、その葉の数を数えるプログラムを作ってみた。

木構造のプログラムを作るためには、二つのことをしなければならない。最初の一つは、木構造を表すデータを定義することだ。次にすることは、それらのデータを操作する関数を定義することだ。プログラムの例は次のように簡単なものになる。

data Btree = Leaf | Node Btree Btree
  deriving (Show)

countLeaves Leaf = 1
countLeaves (Node left right) = countLeaves left + countLeaves right

上の2行が二分木のデータ型 Btree を定義した部分で、下の2行が二分木の葉の数を数える関数 countLeaves だ。

節や葉にデータのない最も単純な木構造のデータ Btree 型は、葉を表すコンストラクタ Leaf と節を表すNode コンストラクタからなる。Node コンストラクタはパラメータに左の枝につながるBtree型のデータと右の枝につながるBtree型のデータをとる。

countLeaves は引数として与えられた Btree 型のデータの葉(Leaf)の数を数える関数だ。countLeaves の引数のデータが Leaf 型の時は、カウントは1だ。countLeaves の引数のデータが Node 型の時は、節(Node) の左の分枝につながる二分木の葉の数と右の分枝につながる二分木の葉の数の和になる。

実行例は次のようになる。(GHCi で実行した。)

*Main> let a = Node Leaf (Node Leaf Leaf)
*Main> countLeaves a
3

二分木の構造を再帰的にたどってすべての葉の数を数える関数をどうやって作るのだろうと思うが、実際には、代表的な葉や節に注目して、その葉や節における葉の数を数えるにはどうすればよいかと考えたことをそのままプログラムにすればよいだけだった。

繰り返しのある構造については、その中の一点だけに注目して漸化式(再帰的な定義式)を記述するという再帰的定義の仕方は、慣れてくると、プログラムのアルゴリズムを考える手間を非常に楽にしてくれる。

Haskell というと、再帰関数が多用されるのが分かりにくいと敬遠されるが、再帰的定義のパターンに慣れるとこれほど強力なものはない。Haskell の記述の簡潔さは主に再帰関数によるのではないかと思える。Haskell を習得し楽しむためのコツは、事あるごとに再帰関数を定義して、その考え方に慣れることだろう。


今日のHaskell
data MyData a = MyData a
  deriving (Show)

data で自分のデータ型を宣言するとき、deriving (Show) で自分で定義したデータ型を Show クラスのインスタンスにしておくと、Haskell が自動的に show 関数で文字列として表示可能にしてくれる。

実行例
*Main> let x = Mydata 3
*Main> show x
"Mydata 3"
*Main> print x
Mydata 3
[PR]
by tnomura9 | 2010-11-17 22:00 | Haskell | Comments(0)
<< ハノイの塔 Ruby版 askForWords >>