Reputation: 429
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?
Upvotes: 1
Views: 500
Reputation: 52290
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)
Upvotes: 2
Reputation: 8966
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'
Upvotes: 1
Reputation: 3218
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.
Upvotes: 1
Reputation: 370415
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
).
Upvotes: 1