haskell polymorphic function evaluation error

Question

The following code doesn't compile:

foo :: Num a => (a -> a) -> Either Integer Double -> Either Integer Double
foo f x = case x of
  Left i -> Left $ f i
  Right d -> Right $ f 

and give the following error:

Couldn't match type `Integer' with `Double'
Expected type: Either Integer Double
Actual type: Either Integer a
In the expression: Right $ f d
In a case alternative: Right d -> Right $ f d

This is a follow up question to this question, the problem is solved by using RankNTypes:

(forall a. Num a => a -> a)

But the answer didn't say anything. I want to know:

• what's the root cause of this error? The eventual result would only be one of the case branch, f wouldn't be typed to two types at the same time, the type of f should be checked as long as f :: Num a => (a -> a), either Integer -> Integer or Double -> Double should work, could someone elaborate why this causes an error?

• Is there any other way to fix the error? Why RankNTypes would fix the error? This strike me like the Monomorphism Restriction error I got the other day, but the enable it doesn't help me fix this, and the explicit type annotation doesn't work either.

Answer 1

The root cause is, that with your original definition, a is too general. Consider:

foo :: Num a => (a -> a) -> Either Integer Double -> Either Integer Double
foo f x = case x of
  Left i -> Left $ f i

At this point, the type checker comes in trouble, because the type of Left $ f i must be Either Integer Double, hence the expression f i must be Integer. But you said that the caller may pass any function mapping a numeric type to itself. For example, your type signature permits to pass a Double -> Double function. Clearly, such a function may never result in Integer, hence the application of f is not well typed here.

OTOH, if you use the solution with higher ranked types, you won't be able to pass any function that works on specific types - only functions that work on all numeric types. For example, you could pass negate, but not ((1::Integer)+). This absolutly makes sense, as you also apply the same function to a Double value in the other case alternative.

So, to answer your second question, the higher ranked type solution is the correct one, given your code. You obviously can only want to pass functions like negate if you want to apply it to an Integer and a Double.

Bottom line: With

f :: (a -> a) -> b

you could pass functions like id, tail, reverse, ((1::Int)+). With

f :: (forall a. a -> a) -> b

you could only pass functions with that exact type signature forall a. a->a (modulo type variable renaming) such as id, but none of the others mentioned above.

Answer 2

Fundamentally this is a scoping issue. Let us compare the following type drafts:

foo1 :: Num a => (a -> a) -> ...

foo2 :: (forall a. Num a => a -> a) -> ...

In the first declaration the compiler wants to have one type a that is an instance of Num and a function of type a -> a for that particular type. Specifically a function that only works with Integer would fit here. Of course such a function does not fit for your task, so the compiler rightfully rejects your implementation for your given type signature. On the other hand the second type signature says that you want a function of type a -> a that works for all instances of Num. This type is significantly limited compared to the former.

As a workaround you could require the function to be given twice:

foo :: (a -> a) -> (b -> b) -> Either a b -> Either a b
foo f g = either (Left . f) (Right . g)

Answer 3

It’s a question of scope, really.

In the original, you have a fresh type variable for each instantiation of foo.

foo :: forall a. Num a => (a -> a) -> Either Integer Double -> Either Integer Double

a must be the same for the entire body of each instantiation of foo, and only one Num instance is involved. Whereas in the rank-2 polymorphic version, you have a fresh type variable for each instantiation of the f parameter.

foo :: (forall a. Num a => a -> a) -> Either Integer Double -> Either Integer Double

And you are talking about as many Num instances as there are instantiations.