Folding list of trees - hasekell

Question

I am working on this problem and got stumped hard. The problem is posted on the picture below:

https://i.stack.imgur.com/SeXpF.png

Before it is marked as duplicate, someone has already answered this question but they changed the function definition to make their answer work. I've posted their solution here:

Find Sum of leaves

I'm looking for an answer that would actually work with the function definition described in the question itself.

foldListTree :: (a -> a -> a) -> a -> ListTree a -> a

I've attempted to do the solution as follows:

data ListTree a = ListLEAF [a] | ListNODE [(ListTree a)]
                  deriving (Show, Read, Eq)

foldListTree :: (a -> a -> a) -> a -> ListTree a -> a
foldListTree f base (ListLEAF a) = foldr f base a
foldListTree f base (ListNODE iL) = foldListTree f base (map f iL)

However I get an error:

Couldn't match expected type `ListTree a' with actual type `[a -> a]'

Any help would be appreciated, thanks!

Answer 1

Let's look at this line:

foldListTree f base (ListNODE iL) = foldListTree f base (map f iL)

You have the following values available:

• foldListTree :: (a -> a -> a) -> a -> ListTree a -> a
• f :: a -> (a -> a)
• base :: a
• iL :: [ListTree a]

and you need to inhabit a.

Let's trace the type of your expression:

• map :: forall c d. (c -> d) -> ([c] -> [d])
• map f :: [a] -> [a -> a], where c is instantiated to a and d is instantiated to a -> a.

For the expression map f iL to be well-typed, iL should have type [a], but it has type [ListTree a]. That's one type error, but not the one that the typechecker is reporting.

In the code foldListTree f base (map f iL), the third parameter should have type ListTree a. However, map f iL has type [a -> a].

What you actually want is:

foldListTree f base (ListNODE iL) = foldl' (foldListTree f) base iL

This is the derivation:

• foldListTree :: (a -> a -> a) -> a -> ListTree a -> a
• foldListTree f :: a -> ListTree a -> a
• foldl' (foldListTree f) :: a -> [ListTree a] -> a
• foldl' (foldListTree f) base :: [ListTree a] -> a
• foldl' (foldListTree f) base iL :: a

Note that the question asks for the leaves to be visited from left to right. (If f is not commutative, the order that you visit the leaves matters.) In your base case, you've used foldr, but you should actually use foldl or foldl'. I use foldl' here because it avoids thunk buildup.

To use foldl', you must import it:

import Data.List (foldl')

Update April 10, 2020: Update answer to use foldl' instead of foldr.