Breadth First Search

gistfile1.hs

data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)

breadthFirst :: (a -> b) -> Tree a -> [b]
breadthFirst f Empty = []
breadthFirst f t     = breadthFirst' f ([], [t])

breadthFirst' :: (a -> b) -> ([b], [Tree a]) -> [b]
breadthFirst' f (bs, []) = bs
breadthFirst' f (bs, as) = bs ++ breadthFirst' f  (bsForAs, nextAs)
  where (bsForAs, nextAs) = breadthFirst'' f as

breadthFirst'' :: (a -> b) -> [Tree a] -> ([b], [Tree a])
breadthFirst'' f []                           = ([], [])
breadthFirst'' f (Empty : xs)                 = (peers, children)
  where (peers, children) = breadthFirst'' f xs
breadthFirst'' f ((Branch x lt rt) : xs)      = ((f x) : peers, (lt : rt : children))
  where (peers, children) = breadthFirst'' f xs

sampleTree = Branch 'a' (Branch 'b' (Branch 'd' Empty Empty)
                               (Branch 'e' Empty Empty))
                   (Branch 'c' Empty
                               (Branch 'f' (Branch 'g' Empty Empty)
                                           Empty))

*Main> breadthFirst succ sampleTree
"bcdefgh"