Type checking with RankNTypes in Haskell

Question

I am trying to understand RankNTypes in Haskell and found this example:

 check :: Eq b => (forall a. [a] -> b) -> [c] -> [d] -> Bool check f l1 l2 = f l1 == f l2 

(If my understanding is correct, this is equivalent to check :: forall bc d. Eq b => (forall a. [a] -> b) -> [c] -> [d] -> Bool .)

Ok, so far so good. Now, if explicit forall a removed, the GHC generates the following errors:

 Could not deduce (c ~ a) from the context (Eq b) […] Could not deduce (d ~ a) from the context (Eq b) […] 

When deleting a nested forall type signature becomes

 check :: forall abc d. Eq b => ([a] -> b) -> [c] -> [d] -> Bool 

It is easy to see why this does not check type checking, since l1 and l2 must be of type [a] so that we can pass them to f , but why it is not, when f specified, enter (forall a. [a] ->b) ? Is the fact that a is connected only inside the parens complete answer? That is, type checking will take

 [c] -> b ~ (forall a. [a] -> b) [d] -> b ~ (forall a. [a] -> b) 

(edit: fixed thanks, Boyd!)

since a function like (forall a. a -> b) can accept any list?

Answer 1

When f = \xs -> ... written with explicit quantization Rank2 forall a. [a] -> b forall a. [a] -> b , you can view this as a new function

 f = Λa -> \xs -> ... 

where Λ is a special lambda that takes a type argument to determine which concrete type a it will use in the function body. This type argument is applied every time a function is called, just like regular lambda bindings are applied to every call. So the GHC processes forall internally.

In the explicit version, forall 'd f can be applied to different type arguments every time it is called so a can be resolved each time for another type, once for c and once for d .

In the version without internal forall this type application for a occurs only once when check is called. Therefore, every time f is called, it must use the same a . Of course, this fails because f is called on lists of different types.

Answer 2

It is easy to understand why this does not check type checking, since l1 and l2 must be of type [a] so that we can pass them to f, but why this is not so if you specify the type f as (forall a. [A] → b )?

Since the type (forall a. [a] -> B) can be unified using [C] -> B and (separately) [D] -> B However, type [A] -> B cannot be unified using [C] -> B or [D] -> B

Is the fact that a is only connected inside the parens complete answer?

Basically. You must select a specific type for each type variable if you are “inside” the entire area, but outside you can use forall several times and select each individual type every time you do.

those. type check will accept

 [c] ~ (forall a. a -> b) [d] ~ (forall a. a -> b) 

since a function like (forall a. a → b) can accept any list?

Meticulous. You seem to have lost some "[]" characters. In addition, you are not entirely sure that the merge is correct. The type controller will accept both:

 [C] -> B ~ (forall a. [a] -> B) [D] -> B ~ (forall a. [a] -> B) 

He also will not accept:

 [C] -> B ~ [A] -> B [D] -> B ~ [A] -> B 

Answer 3

You can rewrite universal quantification in a contravariant field with existential quantification in covariant fields (not legal in Haskell, but in principle).

 check' :: exists c' d'. forall bc d. Eq b => ([c'] -> b) -> ([d'] -> b) -> [c] -> [d] -> Bool 

Obviously this works: for c ~ C , d ~ D select c' ~ C and d' ~ D , then the function is just

 check'' :: forall b . Eq b => ([C] -> b) -> ([D] -> b) -> [C] -> [D] -> Bool 

Not sure if this answers your question, but this is one way to take a look at the rank 2 types.