As my interest in functional languages has grown, I have become increasingly interested in using them to implement algorithms which I can already write with imperative languages.

For example, I was taught to implement (and I assume most other people as well)  a breadth first traversal of a tree using a queue and a loop.  An example using this method can be found at the wikipedia page for a breadth first search.  When I wanted to try implement a breadth first search in Haskell I quickly realized that algorithm wouldn’t port over very well.  I thought a bit and was able to come up with this algorithm:

-- My Implementation
breadth :: Tree a -> [a]
breadth nd =  map rootLabel $ nd : (breadth’ [nd])
    where             
      breadth’ [] = []
      breadth’ nds = let cs = foldr ((++).subForest) [] nds in
                     cs ++ breadth’ cs

The idea was that each call to breadth’ takes a list of nodes (which represents of level of the tree) and will concatenate the children of each of those nodes together and recursively call itself again with that list.  This works but its not pretty Haskell.  When choosing Haskell (from what I have learned) it is best if you can avoid explicit recursion and use built in combinators.  After I coded my breadth first traversal function I decided to look into the Haskell standard libraries to see how it is done there.  What I found was a function called levels which returns a list of lists, where each sub-list is a level of the tree.  I slightly modified this to have the same functionality as my breadth function which creates one list of all the nodes in the breadth first order.

This is the resulting code:

-- Haskell Standard Libraray Implementation
br :: Tree a -> [a]
br t = map rootLabel $
      concat $
      takeWhile (not . null) $                
      iterate (concatMap subForest) [t]

This is really slick implementation of what I did above.  The algorithm is the same but the way they went about writing it is so much prettier.