CODEWITHSUNDEEP
haskell
Rumca
Rumca

Reputation: 1829

Decrypting Haskell type error message in simple case

What represents [t0] -> a0 -> [a1] in this error message? I just realized I must be applying (:) to foldr. Why is compiler not complaining that (*2) expects something of kind * as argument?

Prelude> foldr (:) . (* 2) [] [1..10]

<interactive>:141:19:
    Couldn't match expected type `[t0] -> a0 -> [a1]'
                with actual type `[a2]'
    In the first argument of `* 2', namely `[]'
    In the second argument of `(.)', namely `(* 2) [] [1 .. 10]'
    In the expression: foldr (:) . (* 2) [] [1 .. 10]

Upvotes: 2

Views: 155

Answers (2)

kosmikus
kosmikus

Reputation: 19637

Explanation of the error message

We have

foldr (:) ::  [a] -> ([a] -> [a])
(.)       :: (c   -> d           ) -> (b -> c) -> (b -> d)

From this, we conclude that the second argument y in the composition

foldr (:) . y

must result in a list, i.e., be of type 

e -> [a]

In our case, y = (* 2) [] [1..10]. So we have:

(* 2) [] [1..10] :: e -> [a]  -- for some e and a

Thus:

(* 2) [] :: [f] -> e -> [a]  -- for some e, a and f where (Num f, Enum f)

(The constraints on f are because we use numeric literals and range notation in the list [1..10].) Now, consider that 2 and (*) are overloaded, and

(* 2) :: Num g => g -> g

From this we get that [] must have the same type as (* 2) [] (and that type must be an instance of Num):

[] :: [f] -> e -> [a]  -- for some e, a and f where
                       --   (Num f, Enum f, Num ([f] -> e -> [a]))

But this is not true, because [] has type [g] for some g. Now let's look at the error message again:

Couldn't match expected type `[t0] -> a0 -> [a1]'
            with actual type `[a2]'
In the first argument of `* 2', namely `[]'

So modulo renaming of type variables, this is exactly what the error message says.

Addendum

The error points to `[]', so it's perhaps enlightening to see what the typechecker thinks should go in this position. In GHC 7.8, we'll be able to use the TypeHoles extension for this, but for now, an easy way to do it is to abstract from [], i.e., replace it by a function argument:

Prelude> :t \ x -> foldr (:) . (* 2) x [1..10]
\ x -> foldr (:) . (* 2) x [1..10]
  :: (Enum t, Num ([t] -> a -> [a1]), Num t) =>
     ([t] -> a -> [a1]) -> a -> [a1] -> [a1]

From this, you can easily see that this term is actually still type-correct, it only requires x to be of the type

[t] -> a -> [a1]

with the additional class constraints (which are admittedly unlikely to hold).

Upvotes: 3

daniel gratzer
daniel gratzer

Reputation: 53891

So the type of foldr is

 foldr :: (a -> b -> b) -> b -> [a] -> b

So you're passing it (:) so it's type becomes

 foldr (:) :: [a] -> [a] -> [a]

However, you then try to compose it with (*2) [] [1..10]. This isn't even well typed so you're in trouble. I think your problem here is that function application is the highest precedence of all.

  foldr ((:) . (*2)) [] [1..10]

The explicit parens are necessary.

By the way, you can just use

 map (*2) [1..10]

Upvotes: 8

Related Questions