人気ブログランキング | 話題のタグを見る

Haskell 木で遊ぶ

次のプログラム例は、情報処理46巻5号(2005年5月)に掲載された、『Haskell プログラミング 木 (tree) で遊ぶ』 山下伸夫著からの引用だ。

trees.hs (末端のノードがn個の二分木を列挙するプログラム

data DumbTree = Empty | Fork DumbTree DumbTree

instance Show DumbTree where
    show Empty = "0"
    show (Fork l r) = "(" ++ show l ++ "^" ++ show r ++ ")"

trees :: Int -> [DumbTree]
trees 1 = [Empty]
trees n = concat [ joins ls rs | (ls, rs) <- [ lrs xs ys | (xs, ys) <- splits1 n ]]

splits1 :: Int -> [(Int,Int)]
splits1 1 = []
splits1 n = (1, n - 1) : [ (i+1,j) | (i,j) <- splits1 (n-1) ]

lrs :: Int -> Int -> ([DumbTree],[DumbTree])
lrs xs ys = (trees xs, trees ys)

joins :: [DumbTree] -> [DumbTree] -> [DumbTree]
joins ls rs = [ Fork l r | l <- ls, r <- rs ]

冒頭の data DumpTree はユーザ定義型の DumpTree の定義だ。

第2段落の instance Show DumpTree ... はDumpTree 型のデータを show 関数で表示できるようにしたもの。

第3段落の trees n 関数は、n 個の末端を持つ木構造を列挙して DumbTree 型のデータのリストを作る。

第4段落の splits1 n 関数は足した数が n になる整数の組み合わせをすべて列挙する。

第5段落の lrs xs ys は、xs の DumbTree のリストと ys の DumbTree のリストからデータを一つずつ取り出して合成した DumbTree の新しいリストを作る関数。

こう書いていってもわかったような分からないような気になるだけなので、取り敢えずプログラムを走らせてみる。

Main> :l trees.hs
Main> trees 4
[(0^(0^(0^0))),(0^((0^0)^0)),((0^0)^(0^0)),((0^(0^0))^0),(((0^0)^0)^0)]
Main> trees 1
[0]
Main> trees 2
[(0^0)]
Main> trees 3
[(0^(0^0)),((0^0)^0)]

確かに末端のノードが n 個の二分木が列挙されている。

さて、上の関数の中で一番分かりやすいのは何だろうか。それは joins だろう。これは二つのDumbTreeのリストの中から一つずつ取り出して合成し新しいDumbTreeのリストを作る。これの動作から確認してみよう。

Main> trees 1
[0]
Main> trees 3
[(0^(0^0)),((0^0)^0)]
Main> joins (trees 1) (trees 3)
[(0^(0^(0^0))),(0^((0^0)^0))]

たしかに、trees 1 のリストから取り出したDumbTreeのデータと、trees 2 のリストから取り出したDumbTreeのデータを合成したDumbTree のリストが作成されている。ここでもう一度プログラムを見てみると、joins の定義は

joins ls rs = [ Fork l r | l <- ls, r <-rs ]

となっている。右辺の式はリストの内包的定義だ。これは、集合の記法の { Fork(l, r) | l ∈ ls, r ∈ rs } と同じ意味を表している(形も似ている)。つまり、集合(リスト) ls の要素 l と 集合(リスト) rs の要素をとりそれらにForkを作用してできる要素をすべて集めた集合ということだ。この場合 l と r は木構造なので、これを Fork で結合させた新しい木の集合(リスト)が得られることになる。このとき、集合 ls と集合 rs のすべての要素について作業が行われるので、内包的定義を使うとループで記載するのとは次元の違う要素の列挙がコンパクトな命令でできることになる。

次に分かりやすそうなのが、lrs xs ys 関数だ。これは、整数 xs, ys を引数として取り、末端のノードの数が xs 個の木の集合(リスト)と ys 個の木の集合(リスト) の組(タプル)を返す。lrs の定義

lrs xs ys = (trees xs, trees ys)

には lrs の定義に、その上位の関数 trees n が使われているが、これは問題ないらしい。関数形のプログラムでは実行の順序は全く問題にならないからだ。関数の値は引数の値によって決まってしまうので、関数が実行された順序には依存しない。なにか変な感じがするが、プログラムが動いているからそれでいいのだろう。

Main> lrs 2 3
([(0^0)],[(0^(0^0)),((0^0)^0)])

次に、split1 n を見てみよう。split1 n は和が n になるふたつ一組の数(タプル)のリストを列挙するプログラムだ。まず、n = 1 の時はそのようタプルはないから [] になる。

split1 1 = []

次に n が2以上の場合だが、再帰的に定義する。split1 (n-1) であらわされるタプルの一方の値に1を足したものの集合(リスト)に、(1, n-1) を加えたものが求めるタプルの集合(リスト)になる。

splits1 n = (1, n - 1) : [ (i+1,j) | (i,j) <- splits1 (n-1) ]

ちょっとテストしてみる。

Main> splits1 2
[(1,1)]
Main> splits1 3
[(1,2),(2,1)]
Main> splits1 4
[(1,3),(2,2),(3,1)]

道具立ては揃ったので、いよいよ tree n 関数だ。まずノード一個だけで枝がない場合はDumpTree はEmptyだけだ。

trees 1 = [Empty]

次に n が2以上の場合だが、まず足してnになるような2数の組(タプル)の集合を splits1 n で求める。そうしてタプルの第1要素 xs の数の末端数をもつDumpTreeの集合(リスト)と第2要素の数の末端数のDumbTreeの集合(リスト)を組にした集合と集合のタプルの集合を作る。

[ lrs xs ys | (xs,ys) <- splits1 n]

は([末端数xsの木の集合], [末端数ysの木の集合])というタプルの集合になる。

したがって、

[ joins ls rs | (ls,rs) <- [ lrs xs ys | (xs, ys) <- splits1 n) ]]

は[末端数xsの木の集合]の要素と[末端数ysの木の集合]の要素から合成した木の集合の集合の集合になる。trees n = concat は上の集合が集合の集合なので内側の集合の枠をとり払ってフラットなリストにするための命令だ。

冒頭のHaskellの簡潔なプログラムを一つ一つ追いかけていくと大変な操作が要約されて表現されていたことが分かる。Haskell のプログラムで難しいのは、プログラムの書き方ではなくて、多くの操作を圧縮して表現するパズル的なアルゴリズムの難しさなのではないだろうか。

つまり、Haskell でプログラムすると、アルゴリズムを直接に記述することができるが、アルゴリズムそのものの難しさまではカバーしてくれないのだ。
by tnomura9 | 2009-08-10 23:46 | Haskell | Comments(0)
<< Haskell 探検のおわりに Haskell のファイルの読... >>