Haskell n-ary tree traversal

Question

I'm pretty new to Haskell and I'm trying to work out how to traverse a n-ary tree. As output I'm looking to get a list of Leaf values (as the branches have no value), so for testtree this would be: 4,5

My definition so far is:

data Tree a = Leaf a | Branch [Tree a] deriving (Show)

travTree                    :: Tree a -> [a]
travTree (Leaf x)           = [x]
travTree (Branch (x:xs))    = travTree x : travTree xs

testtree = Branch [(Leaf "4"), (Leaf "5")]

But it gives the error:

Couldn't match expected type `Tree a'
  against inferred type `[Tree a]'
In the first argument of `travTree', namely `xs'
In the second argument of `(:)', namely `travTree xs'
In the expression: travTree x : travTree xs

I'm assuming this is due to xs being a list of trees and its expecting a singular tree. Is there a way to do this? I've been trying the map function, along the lines of:

travTree (Branch (x:xs))    = travTree x : map travTree xs

But it then complains of:

Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `travTree'

I've also tried changing the function signature to:

travTree                    :: Tree a -> [b]

Which gives the error:

Couldn't match expected type `a' against inferred type `[b]'
  `a' is a rigid type variable bound by
      the type signature for `travTree' at Main.hs:149:36
In the first argument of `(:)', namely `travTree x'
In the expression: travTree x : map travTree xs
In the definition of `travTree':
    travTree (Branch (x : xs)) = travTree x : map travTree xs

Any help would be greatly appreciated, so thanks in advance..!

Answer 1

You're on the right lines with map, but after traversing each subtree you want to concat the resulting lists together. There's also no point breaking off the first element of the list with the (x:xs) pattern when using map. I'd write this as:

travTree (Branch xs) = concatMap travTree xs

(But beware; I haven't tested that! However I often find my "infinite type a = [a]" problems are caused by a map where concatMap is needed.)

Answer 2

Traversing a tree means traversing all subtrees and flattening the resulting lists into one.

This translates to

travTree (Branch branches) = concat $ map travTree branches

Note that there are even more concise notations like branches >>= travTree or concatMap travTree branches for the right hand side of this definition, but I consider the above one to be the clearest.

Edit: Reintroducing the list-comprehension version for the sake of completeness:

travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ]