Haskell foldr results in type error while foldl doesn't

Question

I'm working through "Haskell Programming From First Principles". In the chapter on Folding Lists, exercise 5f,

when I evaluate

foldr const 'a' [1..5]

I get

No instance for (Num Char) arising from the literal ‘1’

However, with

foldl const 'a' [1..5]

I get 'a'.

I get that the folds are lazy, foldr doesn't traverse the spine and foldl does. But even looking at the definitions of foldr and foldl,

foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

I can't figure out why it would have this type error. I'm guessing that the compiler is inferring type of x (Num) based on the type of z (Char), but I can't see where it draws the connection, since const or f doesn't require its two arguments to be the same type.

Any thoughts?

Answer 1

ok look at the type of foldr :: (a -> b -> b) -> b -> [a] -> b

Starting from the right you obviously must have a be some instance of Num and Enum (because you use [1..5])

Next you pass in 'a' so you have b ~ Char

Finally you have const for the function - and const is const :: a -> b -> a - note how you now must have a ~ b because you unify

a -> b -> b
a -> b -> a
        ^^^^^

but this of course would mean that 'a' must be a value of an instance of Num which Char is not ... there is your error (it's complaining about the 1 because starting left instead it's the point where the the problem becomes obvious)

---

foldl on the other side has foldl :: (b -> a -> b) -> b -> [a] -> b

so now you have again a some instance of Num, b must again be Char but now const just fits in (just switch b and a in the type of const)

Answer 2

foldl and foldr invoke f with a different order of arguments. That is foldr calls const x 'a', but foldl calls const 'a' x. The result of the latter is 'a', which is fine, but the result of the latter is x, which is wrong because x is an Int and the result is supposed to have the same type as the accumulator (Char).

Answer 3

This is a typing problem. The type of foldl is

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b    

and foldr type is:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

When you apply foldr to const you get:

foldr const :: Foldable t => b -> t b -> b

Next, you supply 'a' argument, you get

(foldr const 'a') :: Foldable t => t Char -> Char

So, when you pass [1..5] as an argument it will try to unify t Char with (Enum a, Num a) => [a]. Type Char is an instance of Enum class but not Num and it is the reason why you get this error message.

Answer 4

As others have said, the order of arguments in a foldl and foldr are different. Use flip const instead:

> foldr (flip const) 'a' [1..5]
'a'