Level-order in Haskell

Question

I have a structure for a tree and I want to print the tree by levels.

data Tree a = Nd a [Tree a] deriving Show
type Nd = String
tree = Nd "a" [Nd "b" [Nd "c" [],
                       Nd "g" [Nd "h" [],
                               Nd "i" [],
                               Nd "j" [],
                               Nd "k" []]],
               Nd "d" [Nd "f" []],
               Nd "e" [Nd "l" [Nd "n" [Nd "o" []]],
                       Nd "m" []]]
preorder (Nd x ts) = x : concatMap preorder ts
postorder (Nd x ts) = (concatMap postorder ts) ++ [x]

But how to do it by levels? "levels tree" should print ["a", "bde", "cgflm", "hijkn", "o"]. I think that "iterate" would be suitable function for the purpose, but I cannot come up with a solution how to use it. Would you help me, please?

Answer 1

You just need to compute the levels for all of the subtrees and zip them all together after the root:

levels :: Tree [a] -> [[a]]
levels (Nd a bs) = a : foldr (zipWith' (++)) [] (map levels bs)

Sadly, zipWith doesn't do the right thing, so we can instead use:

zipWith' f xs [] = xs
zipWith' f [] xs = xs
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Update: there is some concern (which I agree with) that what you originally asked is a little weird as it's not a generic breadth-first tree to list convertor. What you probably really want is to concat the result of:

levels' (Nd a bs) = [a] : foldr (zipWith' (++)) [] (map levels' bs)