Haskell n-ary tree traversal

Question

Hi, 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

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 ]

Answer 2

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 3

When I was new to Haskell I ran into the same problem a lot. I finally figured out how to solve the problem by slowing down and looking at the types. (Back when I wrote a lot of Scheme, I instead slowed down and look at very simple input/output pairs. I do that sometimes in Haskell, but not until I've looked at the types.)

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

Your type looks right: Tree a -> [a] sounds like "all the leaves" to me.

travTree (Leaf x) = [x]

This case properly converts a Tree a to a [a].

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

OK, the input is definitely a Tree a. If the output is to be [a], and the first operator is (:) :: a -> [a] -> [a], then we need travTree x :: a and travTree xs :: [a]. Does this work?

Well, it fails for two reasons: actually, travTree x :: [a], and you can't cons a list onto another list (you need (++) :: [a] -> [a] -> [a] for that). And you can't pass [Tree a] to travTree :: Tree a -> [a]--you're giving it a list of trees when it expects a single tree.

You can address the second problem by using map: map travTree xs. This has the type [Tree a] -> [[a]]. Fortunately, this now fits the travTree x :, so that

(travTree x : map travTree xs) :: [[a]]

Now you just have the problem that you have [[a]] instead of [a]. concat solves this problem by flattening once, so

travTree (Branch (x:xs)) = concat (travTree x : map travTree xs) :: [a]

which matches the expected Tree a -> [a].

The other answers are right in saying that the destructuring is pointless here, but I hope that seeing the types spelled out helps you understand how to mimic the type inference in your head. That way you can work out what's going wrong for other, similar problems.