Sun Apr 20 00:30:08 JST 2014

data Tree = L | N Int Tree Tree deriving Show

-- てきとーに考えた木の生成
range :: Int -> Int -> Tree
range i m
  | i >= m = L
  | otherwise = N i (range (i*2 + 1) m) (range (i*2 + 2) m)

bfs :: Tree -> [Tree]
bfs tree = q
  where q = tree : walk q :: [Tree]
        walk :: [Tree] -> [Tree]
        walk (L : _) = [L]
        walk ((N value left right) : rest) = left : right : walk rest

main = do
  -- print a -- これからたどる木
  -- print ls -- たどる順 (ただし木)
  print $ map just ls -- 木の根が、実際に見るノードになる
  -- doSomething (fromJust $ isJust $ map just ls) たどる順 (たぶん無限リスト) について、doSomething する。大域脱出することになるから、たぶん末尾再帰とかかな
  where
  a = range 0 16
  ls = bfs a
  just L = Nothing
  just (N x _ _) = Just x