酔いながらエントリを書いてみる

Haskell 戯言

...タイトル書くだけですでに3回ミスタイプ。
死ねばいいのに。俺。
久々に後輩と飲んだのでちょいとハイ。
で、こんなんmixiに書けよと言う話なので、ちょいと技術的な話を書いてみる。


具体的にはHaskellのData.Treeが気にくわない。
というか、ghcか。

まず、Data.Treeについて。

type Forest a = [Tree a]
data Tree a = Node {rootLabel :: a, subForest :: Forest a}
drawForest :: Forest String -> String
drawTree :: Tree String -> String
flatten :: Tree a -> [a]
levels :: Tree a -> [[a]]
unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a
unfoldForestM ::
  (Monad m) => (b -> m (a, [b])) -> [b] -> m (Forest a)
unfoldForestM_BF ::
  (Monad m) => (b -> m (a, [b])) -> [b] -> m (Forest a)
unfoldTree :: (b -> (a, [b])) -> b -> Tree a
unfoldTreeM :: (Monad m) => (b -> m (a, [b])) -> b -> m (Tree a)
unfoldTreeM_BF :: (Monad m) => (b -> m (a, [b])) -> b -> m (Tree a)

こんな感じの関数群が用意されているらしい。
定義はすんごい素直。
Treeの複数形がForestで、TreeはLabelとそのサブTreeを持っているという、まぁ、多分実装しろ、とか言われたら俺もこう書くだろうな、的な実装。
Frorest系は全部mapと*Tree系で実装できそうだが、とりあえず気にしない。
まぁ、そこはいい。


で、


なんでdrawTreeがTree String -> Stringなのかな？というところ。
そこは(Show a) => Tree a -> Stringだろ。
drawTreeで表示される木がなかなか奇麗なのがナオ悔しいところ。


あと、mapぐらい用意してくれ。

mapTree :: (a -> b) -> Tree a -> Tree b

ぐらい用意してくれ。
それさえあれば

showTree :: (Show a) => Tree a -> String
showTree = drawTree . mapTree show

で、drawTreeを一般化した(Show a) => Tree a -> Stringができるのに。


というわけで実装してみた

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f (Node label forest)	= Node (f label) $ map (mapTree f) forest

こんな感じか？


あと、unfoldがあってfoldがないのかいかがなものか、とfoldも実装。これであってるよね？

foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f (Node label forest)	= f label $ map (foldTree f) forest

こうか？
多分これで、foldTree Nodeがid :: Tree a -> Tree aと恒等なはず。
Listのfoldも"foldr (:) []"が"id :: [a] -> [a]"な感じなんで、多分そう大きな間違いは無いはず。



...酔ってるんで色々間違いあるかと。
うーっぷす。