低脳だから学ばなければならないはずだけど、低脳だと気づきたくないから目を背けてしまう。最近プログラミングの勉強を疎かにしている。「よくないな久しぶりにやろうか」ということで、今日はこれ「Learn You a Haskell for Great Good!」を少し読み進めた。
binary search tree、もしくは赤黒木?(上の画像は白黒木のwikipediaから拝借した) の実装のところで、再帰を使って木の型を定義するのは、シンプルだが不思議な感覚がして感銘を受けた。そういえば、私は木というものが昔から好きだった。忘れると思ったから私が今日読んだ当該部分をコピペする。
--Treeという型をつくる。 data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) --ノードの末端は空(NIL)ということ。 singleton :: a -> Tree a singleton x = Node x EmptyTree EmptyTree --Treeの中に要素を挿入する。要素は順序が比較できる型を持っていなければならない。 treeInsert :: (Ord a) => a -> Tree a -> Tree a treeInsert x EmptyTree = singleton x treeInsert x (Node a left right) | x == a = Node x left right | x < a = Node a (treeInsert x left) right | x > a = Node a left (treeInsert x right) --Treeにある特定の要素が入っているか確認する。 treeElem :: (Ord a) => a -> Tree a -> Bool treeElem x EmptyTree = False treeElem x (Node a left right) | x == a = True | x < a = treeElem x left | x > a = treeElem x right
そして、端末からghciの中に入って、上の関数が書かれたファイルをロードする。
ghci> :l ファイル名
それから、たとえば次のように入力してみる。
ghci> let nums = [8,6,4,1,7,3,5] ghci> let numsTree = foldr treeInsert EmptyTree nums ghci> numTree Node 5 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 7 (Node 6 EmptyTree EmptyTree) (Node 8 EmptyTree EmptyTree)) ghci> 8 `treeElem` numsTree True ghci> 100 `treeElem` numsTree False ghci> 1 `treeElem` numsTree True ghci> 10 `treeElem` numsTree False
上のfoldrで折り畳んでnumsに入っていた数字をTreeの中に入れるのはいいなと思った。Skitchを使って指で適当につくった雑なものだけど、numsTreeの図を書いてみた。
foldrでright(右)から畳み込むやり方をやったので、ついでだから、foldlでleft(左)からも同じことをやってみる。
ghci> let numsTree00 = foldl (flip treeInsert) EmptyTree nums ghci> numsTree00 Node 8 (Node 6 (Node 4 (Node 1 EmptyTree (Node 3 EmptyTree EmptyTree)) (Node 5 EmptyTree EmptyTree)) (Node 7 EmptyTree EmptyTree)) EmptyTree ghci> map ((flip treeElem) numsTree00) [1..10] [True,False,True,True,True,True,True,True,False,False]
numsTree00の図を書いてみたが、右から入れた場合と木の形が違う。要素を入れる順序によってつくられる木の形が変わるんだね。
