CODEWITHSUNDEEP
haskelltree
Petter Bjao
Petter Bjao

Reputation: 325

Use foldl to traverse a Tree in Haskell

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

Upvotes: 2

Views: 302

Answers (2)

daniel gratzer
daniel gratzer

Reputation: 53911

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).

Upvotes: 3

Emil
Emil

Reputation: 2167

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

Upvotes: 4

Related Questions