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)

Answer 2

levels :: (Tree a) -> [[a]]
levels (Nd x ts) = [[x]] ++ levelshelper ts

level2 = (map concat).levels

levelshelper :: [Tree a] -> [[a]]
levelshelper [] = []
levelshelper xs = (map (\(Nd x ts) -> x) xs) : (levelshelper (extractl xs))

--get the next level's Nd's 
extractl :: [Tree a] -> [Tree a]
extractl [] = []
extractl ((Nd x ts):xs) = ts ++ (extractl xs)

My approach turned out being a bit more ham-handed than I wanted. Correct me if I'm wrong, though, since strings are lists of characters, but you're using polymorphic types, is it really so straightforward to to print your results out like specified in the problem? This code produces lists of lists of strings. ***Props to Chris in his more elegant answer for reminding me about the use of concat!!

Answer 3

Here is another version which can be applied to Tree a instead of Tree [a].

levelorder :: Tree a -> [[a]]
levelorder (Nd x ts) = [x]:(ziplist (map levelorder ts))

ziplist :: [[[a]]] -> [[a]]
ziplist l = if null ls then [] else (concat heads):(ziplist tails)
    where
        ls = filter (not.null) l
        heads = map head ls
        tails = map tail ls

If you want to concatenate the strings at the end you may use:

levelorder2 :: Tree [a] -> [[a]]
levelorder2 = (map concat).levelorder

Answer 4

I'm guessing this is homework. On the assumption that it is, then here's some ideas for how to think about the problem that might lead you to an answer:

In preorder, first the current item is "reported", then recurse for all this node's tails. In postorder these two steps are done in reverse. In both cases, the recursion is "local", in the sense that it only need deal with one node at a time. Is this true for levelorder? Or to ask it another way, when levelorder recurses, do the results of the recursions interact or no? If so, then, what is the "unit" of recursion, if not a single Tree?

Understanding the nature of the recursion (or iteration..?) of levelorder will lead you to a solution that very simple and elegant. My version is only three lines long!

By the way, it might be nice to have these utility functions to make the code even clearer in some places:

element :: Tree a -> a
element (Nd x _) = x
subtrees :: Tree a -> [Tree a]
subtrees (Nd _ s) = s

Or, if you are familiar with record syntax in Haskell, you can achieve exactly this by changing your original Tree definition to:

data Tree a = Nd { element :: a, subtrees :: [Tree a] }
    deriving Show

---

A full solution:

The key is realizing that levelorder requires recursion on a list of Tree. At each step the elements from each Tree is extracted, and the next step is upon the concatenation of the subtrees:

levelorder :: Tree a -> [a]
levelorder t = step [t]
    where step [] = []
          step ts = map element ts ++ step (concatMap subtrees ts)

This produces the elements in a single, flattened list, much like preorder and postorder do, and is the usual definition of a breadth-first traversal.

If instead you really want the elements grouped by level, a single change of the ++ operator to : will yield that version:

bylevel :: Tree a -> [[a]]
bylevel t = step [t]
    where step [] = []
          step ts = map element ts : step (concatMap subtrees ts)

Note: I have given type signatures for all top-level functions. This is a really good habit to get into, and will save you considerable time debugging.