How does the GHC interpret `foldl + 0 [1,2,3]` (without parentheses around +)?
One thing that got me stuck early in learning Haskell was the difference between foldl +
and foldl (+)
.
Prelude> :t foldl + 0 [1,2,3]
:: (Num t1, Num ((b -> a -> b) -> b -> t a -> b),
Num ([t1] -> (b -> a -> b) -> b -> t a -> b), Foldable t) =>
(b -> a -> b) -> b -> t a -> b
against
Prelude> :t foldl (+) 0 [1,2,3]
foldl (+) 0 [1,2,3] :: Num b => b
How does Haskell / GHC infer the type foldl + 0 [1,2,3]
? How can I figure out why it is spreading to this giant type?
source to share
Because it +
is an infix operator and there are no parentheses that override things,
foldl + 0 [1,2,3]
analyzes how
(foldl) + (0 [1,2,3])
The simplest starting point is the type foldl
, which is well known (and if you don't know it, you can just ask GHCI with :t foldl
).
foldl :: Foldable f => (a -> b -> a) -> a -> f b -> a
Next, the other side of the addition. Since it 0
is applied as a function with [1,2,3]
as an argument, there must be a Num instance for the function type that takes a list of some numeric type as input and produces as output ... well, I'll get to that.
0 [1,2,3] :: (Num t, Num ([t] -> s)) => s
Since it is applied to these two expressions +
, they must be of the same type. Therefore, we must combine
foldl :: Foldable f => (a -> b -> a) -> a -> f b -> a
from
0 [1,2,3] :: (Num t, Num ([t] -> s)) => s
The most common way to do this is to s
be the same type as foldl
(combining their constraints), giving us
0 [1,2,3] :: (Foldable f,
Num t,
Num ([t] -> (a -> b -> a) -> a -> f b -> a))
=> (a -> b -> a) -> a -> f b -> a
And remember, of course, foldl
must be of exactly the same type:
foldl :: (Foldable f,
Num t,
Num ([t] -> (a -> b -> a) -> a -> f b -> a))
=> (a -> b -> a) -> a -> f b -> a
And since +
from class Num, the class they share must also be Num.
foldl + 0 [1,2,3] :: (Foldable f,
Num t,
Num ([t] -> (a -> b -> a) -> a -> f b -> a),
Num ((a -> b -> a) -> a -> f b -> a))
=> (a -> b -> a) -> a -> f b -> a
Which, as you can see, is modulo some type renaming, exactly what GHC told you.
But of course this is a pretty stupid guy. Perhaps someone will write all these outrageous Num instances, which is why GHC dutifully describes this as a valid type. But nobody actually wrote these instances, so you will have a lot of problems using this expression. Indeed, what you need to do is correct your parentheses.
source to share
Haskell brackets are used for more than just evaluating expression precedence. These two statements are actually completely different.
The + sign is an operator, so it should work like a + b = c
. That is, one argument to the function is to the left and the other to the right. You say that an operator is used in infix notation when it does.
You can hide any operator before a normal function that is in prefix notation by having parentheses. (+) a b = c
...
Because of this, your two expressions were completely different. Naturally, they have different types of signatures.
source to share