Use foldl to traverse a Tree in Haskell

Question

I've got the following code:

data Tree a = ATree a [Tree a] 
            deriving Show

treeFold :: (b -> a -> b) -> b -> Tree a -> b
treeFold f acc (ATree a [])      = f acc a 
treeFold f acc (ATree a m)       = foldl (treeFold f acc) (f acc a) m

It's supposed to go over each element of Tree and apply a function to the value. But it gives me this error:

Couldn't match type `Tree a' with `Tree a -> b'
    Expected type: (Tree a -> b) -> a -> Tree a -> b
      Actual type: b -> a -> b
    In the first argument of `treeFold', namely `f'
    In the first argument of `foldl', namely `(treeFold f acc)'
    In the expression: foldl (treeFold f acc) (f acc a) m

Answer 1

The first input to foldl you have has type Tree a -> b but it should actually have type b -> Tree a -> b. Just get rid of the acc in the first argument.

treeFold f acc (ATree a m) = foldl (treeFold f) (f acc a) m

Answer 2

First off, please don't use foldl. It's almost always bad and it's strict cousin foldl' is a much better behaved and properly tail-recursive function.

In any case, foldl expects to supply it's function with the accumulator which you're already doing by applying treeFold to acc, instead just use foldl' (treeFold f).