2014/04/20 の自分の記事を見て、 ちょっと違う気がしたので、訂正
data Tree = Leaf | Node Int Tree Tree deriving Show
-- 適当な木その1
t = Node 0 (Node 1 (Node 3 Leaf Leaf) Leaf)
(Node 2 Leaf (Node 4 Leaf Leaf))
-- 適当な木その2
s = Leaf
-- 木からたどる順リストを得る
bfs tree = map root q
where
root Leaf = Nothing
root (Node x _ _) = Just x
q = tree : walk q
walk (Leaf : _) = []
walk ((Node x l r) : rest) = l : r : walk rest
main = do
print $ bfs t
print $ bfs s[Just 0,Just 1,Just 2,Just 3,Nothing,Nothing,Just 4,Nothing,Nothing]
[Nothing]その前の記事と実際違うのは一行だけで、
walk (Leaf : _) = []と今のはしているが、前は
walk (Leaf : _) = [Leaf]としていた． walkは次にたどるものが欲しいのであって、自身は既に返す答えに含まれている (tree : walk q) ．
で、幅優先で嬉しいというのは、深さが無限になり得る場合が一つの場合として挙げられて、
infinityTree = make 0
where
make n = Node n (make m1) (make m2)
where
m1 = n * 2 + 1
m2 = n * 2 + 2
main = do
print $ take 20 $ bfs infinityTreeが動く.