「Haskell プログラミング - 木（tree）で遊ぶ」に「ごくやさしい問題をやってみよう」と「課題」が書かれていた。著者を見たら「ふつうのHaskellプログラミング」の監修をされている方だった。おぉ～と思いながら、早速課題に目を通す。
末端のノードが n 個の二分木を列挙せよ． (同上より)
…ん？ (@_@;)
問題の意味がわからず。。。
次頁に 10 行 でコードが書かれていたので、解説を読みつつ目を通していく。
… … … (+_+) … … …
パタッ(o_ _)ｏ~†
(最初読んだとき、何をどうやって再帰的に考えればいいのかわからなかった。そのため splits1 関数の意図が見えず。)
方法を考える
結局わからなかったので、自分が理解できる方法で実装することに。上記の解説を読んだおかげで、課題の意味は理解することができた。^^;
「末端が 1 ~ 3 個のノードをそれぞれ列挙」したものを描いてみると、
「末端のノード」を言いかえれば、木における「葉」のこと。末端のノードが 1 個というのは「葉」が一枚あるだけの木のこと。このとき当然ながら他の形はない。末端のノードが 2 個は、葉が左右に 2 枚ある木。これが枝のある木としては一番小さい形。2 個のときもこの形のものしかない。末端のノードが 3 個は、2 個のときの木の葉に、それぞれ「最小の木」がぶらさがる形。合計 2 つ。末端のノードが 4 個の絵は、「木（tree）で遊ぶ」に描かれている。(以下、末端のノードが 1 個の木を n = 1 の木と呼ぶ。)
再帰的な定義を考えるときは「現在の形が、一つ前の形からどのようにして形成されるか？」を考えること。そこで n = 2 の木を見ると、n = 1 の木の葉から枝が 2 本ニョキニョキ枝が生え、尖端に葉がついたと見ることができる。 n = 3 の木を見ると、n = 2 の木の葉からそれぞれ n = 2 の木が生えたと考えることができる。同様に、n = 4 の場合も見ておくと、n = 3 の木のそれぞれ葉から１つだけ n = 2 の木が生えているのがわかる。
これで「木」に対して再帰的な見方ができるようになった。問題は、どのようにして全ての場合を漏れなく列挙するかということ。うーん… (+_+)
葉から木を生やす関数
ここで最初に必要となる関数が思い浮かんだ。上記のように特定の「葉」からニョキニョキと木が生えてくると見るのであれば、「特定の葉」を指定したら、そこから木が生える関数が欲しい。
その前にまずは、木の型を A Gentle Introduction to Haskell: Standard Classes に倣い以下のように定義。
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show, Eq)
Tree 型ではなく Tree a 型としたのは、各々の葉を識別するラベルを付けるため。これにより、指定したラベルの付いている葉からニョキニョキと木を伸ばすことができるようにする。
関数の定義に移る。まずは、関数の名前と型から。関数名を extend とし、第1引数に葉を伸ばす木を与え、第2引数で対象の葉のラベルを指定すると、大きくなった木が返されるとした。
extend :: Num a => Tree a -> a -> Tree a
extend (Leaf x) n
| x == n = Branch (Leaf $ n*10) (Leaf $ n*10+1)
| otherwise = Leaf x
extend (Branch l r) n = Branch (extend l n) (extend r n)
葉に適用された場合、上記のシンプルな方法でラベルの値を設定し木を返す。木に葉がある場合は、それぞれの葉に extend 関数を適用。これにより、葉に到達するまで再帰的に関数が適用され、与えられた引数に一致する値の葉を見つけたら、その葉から枝を伸ばすということが表現できた。
extend 関数を試してみる。
main = do print $ extend (Leaf 1) 1 print $ extend (Branch (Leaf 1) (Leaf 2)) 1 print $ extend (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3)) 3
結果、
Branch (Leaf 10) (Leaf 11) Branch (Branch (Leaf 10) (Leaf 11)) (Leaf 2) Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 30) (Leaf 31))
それぞれの葉から木を生やす
(※ 後でこれだけでは問題があることに気がついた。)
さて、どうやって定義をすればいいだろう。何かちょっとややこしくなりそうな雰囲気が… (+_+) とりあえず順を追って定義していく。
関数名は trees とし、末端のノード数 n を与えると、木のリストが返される。
trees :: Int -> [Tree Integer]
「葉」に数値のラベルを付けることにしたので、返されるのは Tree Integer のリスト。
葉のラベルのリスト
最初に trees から独立した関数で、木を与えると、葉のラベルのリストを返す関数を定義する。名前は leaflabels 。これは単純に、葉に適用されたらその葉が持つラベルを返し、葉を持つ木であれば左右の葉に再帰的に leaflabels を適用。
leaflabels :: Tree a -> [a] leaflabels (Leaf x) = [x] leaflabels (Branch l r) = (leaflabels l) ++ (leaflabels r)
n = 1 のとき
trees 関数の定義に戻る。最初は n = 1 のとき。これは絵を見て、明らかなように、
trees 1 = [Leaf 1]
trees 1 はラベルが `1’ の葉を返すことにした。木が大きくなるとき、この値を元にして葉の値が作られていく。
n = 2 のとき
次に、いきなり一般化して考えることができなかったので、 n = 2 のときを定義してみる。 n = 2 では、以下のような値が返ってきてほしい。
[Branch (Leaf 0) (Leaf 1)]
とりあえず、いきなりキチンとした関数を定義することは考えず、最初は n = 2 で「目的の値が返ればよい」という程度で考える。
まず、先ほど定義した leaflabels を使って、Leaf 1 のラベルのリストを取得する。
leaflabels $ Leaf 1
n = 2 のときは、返されるのは要素が一つ、 [1] 。これを元に n = 1 の木を大きくする。
map (extend (Leaf 1)) $ leaflabels $ Leaf 1
もちろん、これは単に目的の値が返ってくるだけに過ぎない。n > 2 だと、上記の定義では目的の値を取得できない。ただし、少し定義の方向が見えてきた感じが…。
n = 4 のとき
次に、再帰的な定義ができるか考えてみる。 n = 2 で生成される木のリストは、trees 1 が元になる。 trees 1 は木のリストで、その各々の要素を使って trees 2 が作られる。しかし、trees 1 で得られる木のリストは要素が一つだけであり、木自身も葉が一枚なので、再帰的な定義を考える上で少しイメージがつかみにくい。
そこで、n = 4 の場合で考えてみる。n = 4 のときは、trees 3 で得られる木のリストを元に作られる。上の絵の赤い線で囲った葉の部分に、それぞれニョキニョキと枝をつけた木のリストが得られればよい。
最初に trees 関数全体の形が、次のように想像できる。
map 関数X $ trees 3
「trees 3 で得られた木のリストを元にして、各々の木に「何かする」 関数X を適用する」と考える。
「関数X」の中身が何かわからないけれど、とりあえず格好だけ整える。関数X をとりえあえず trees’ と命名。
trees 4 = map trees' $ trees 3
where
trees' t =
trees’ の t は trees 3 によってできる木の要素の一つを表わす。 その一つの木に対して、更に各々の葉から枝を伸ばした木を生成する。そのため、ここでもまた map を使う。
trees 4 = concatMap trees' $ trees 3
where
trees' t = map (extend t) $ leaflabels t
trees はリストを返す。結果、 map がネストしたので、全体で返される値がリストのリストになってしまった。リストのネストをなくすため、最初の map を concatMap に変更。 (cf. Haskell で map のネスト)
次に n の場合に一般化する。これは簡単で、4 と3 を置き換えるだけ。
trees n = concatMap trees' $ trees (n-1)
where
trees' t = map (extend t) $ leaflabels t
結果の表示
これできたぁ～ ^^ と思い、表示のための showTree 関数を書き、
showTree :: Tree a -> String
showTree (Leaf x) = "o"
showTree (Branch l r) = "(" ++ showTree l ++ "^" ++ showTree r ++ ")"
n = 4 の場合を出力させた。
["(((o^o)^o)^o)","((o^(o^o))^o)","((o^o)^(o^o))","((o^o)^(o^o))","(o^((o^o)^o))","(o^(o^(o^o)))"]
あれ？ (@_@;) 同じ形の木が余分にできてる。
考えてみれば当り前で、n = 4 を作成する元になる木のパターンは右図のように二つあり、異なる木からでも、赤い丸で囲った葉から枝を伸ばすと同じ形になる。上記の出力を見ても、右図の下の木が二つ表われている。
うへぇ～、どうしよう (+_+)。
重複を取り除く
同じものができてはいけないというなら、重複を取り除ければいい。Python の組み込み関数である set() のように、リストから重複のある要素を取り除いて set 型のオブジェクトを返してくれるような関数があるといいのだけれど…。
print set([1,2,3,3,4,4,5]) # set([1, 2, 3, 4, 5])
リスト操作なので、Data.List をながめていたら、Special lists に、"Set" operations があった。その中で、
nub :: Eq a => [a] -> [a]
The nub function removes duplicate elements from a list.
Yahoo!辞書 – nub によると、
要旨, 要点, 骨子, 核心, 中心((of ...))
import Data.List し、nub を試してみる。
print $ nub [1,2,3,3,4,4,5] -- [1,2,3,4,5]
おぉ～、これでリストから重複した木を取り除くことができる。 ^^
後付けな感が否めないけれど、先ほどのコードに nub を加えた。
trees n = nub $ concatMap trees' $ trees (n-1)
where
trees' t = map (extend t) $ leaflabels t
表示の変更
ついでに「練習問題1」もやってみる。出力を左の葉であれば `L’、右の葉であれば `R’ と表示する。showTree を元にして、まずは左右の葉で異なる関数を呼出すように変更。
showTree2 :: Tree a -> String
showTree2 (Leaf x) = "o"
showTree2 (Branch l r) = "(" ++ showTreeL l ++ "^" ++ showTreeR r ++ ")"
上記の関数から呼出される関数をそれぞれ定義。
showTreeL :: Tree a -> String showTreeL (Leaf _) = "L" showTreeL t = showTree2 t showTreeR :: Tree a -> String showTreeR (Leaf _) = "R" showTreeR t = showTree2 t
何か似たような処理をしているのでまとめる。
showTree3 :: Tree a -> String
showTree3 t = case t of
Leaf x -> "o"
(Branch l r) -> "(" ++ showTreeL l ++ "^" ++ showTreeR r ++ ")"
where
showTreeL (Leaf _) = "L"
showTreeL t = showTree3 t
showTreeR (Leaf _) = "R"
showTreeR t = showTree3 t
あれ？ まとめた意味がなかった… ^^;
全体
import Data.List
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show, Eq)
-- ノードが n の二分木のリスト
trees :: Int -> [Tree Integer]
trees 1 = [Leaf 1]
trees n = nub $ concatMap trees' $ trees (n-1)
where
trees' t = map (extend t) $ leaflabels t
-- Tree における Leaf に設定された値のリスト
leaflabels :: Tree a -> [a]
leaflabels (Leaf x) = [x]
leaflabels (Branch l r) = (leaflabels l) ++ (leaflabels r)
-- 与えられた引数 a に一致する Leaf を拡張
extend :: Num a => Tree a -> a -> Tree a
extend (Leaf x) n
| x == n = Branch (Leaf $ n*10) (Leaf $ n*10+1)
| otherwise = Leaf x
extend (Branch l r) n = Branch (extend l n) (extend r n)
showTree :: Tree a -> String
showTree (Leaf x) = "o"
showTree (Branch l r) = "(" ++ showTree l ++ "^" ++ showTree r ++ ")"
showTree3 :: Tree a -> String
showTree3 t = case t of
Leaf x -> "o"
(Branch l r) -> "(" ++ showTreeL l ++ "^" ++ showTreeR r ++ ")"
where
showTreeL (Leaf _) = "L"
showTreeL t = showTree3 t
showTreeR (Leaf _) = "R"
showTreeR t = showTree3 t
main = do
print $ map showTree $ trees 4
print $ map showTree3 $ trees 4
2コメント:
nub使わないやり方のほうがいいと思います。再帰を左右に分けて…
やっぱり、そうですか ... ^^;
木を大きくしていくというと根本からニョキニョキ伸ばしていくものだと思っていたので、葉の方から根本に向って作り、最後にくっつけるという発想ができませんでした。
コメントを投稿