Mon Jun 16 12:50:15 JST 2014

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

が動く.