I'm working with higher-ranked types in Haskell and based on Peyton Jones' Practical Type Inference for Arbitrary-Rank Types), I expect the following function to type-check since ((forall b. [b]) -> Bool) appears to be more polymorphic than ((forall a. a) -> Bool).
Here's my code:
fun :: ((forall b. [b]) -> Bool) -> ((forall a. a) -> Bool)
fun arg = arg
However, GHC rejects it with a type error.
I also tried
fun2 :: (forall a.a -> Bool) -> (forall b.[b] -> Bool)
fun2 arg = arg
which compiled successfully, and it is consistent with the fact that (forall a.a -> Bool) is more polymorphic than (forall b. [b] -> Bool). But I do not understand why fun function that I defined previously does not type check.
As Naïm Favier says in their comment: "Turn on DeepSubsumption
.", this will change the subsumption rules that GHC uses, and thus introduce the deep skolemization:
GHC will instead automatically rewrite expressions like
f x
of typety1 -> ty2
to become(\ (y :: ty1) -> f x y)
; this is called eta-expansion. See Section 4.6 of Practical type inference for arbitrary-rank types, where this process is called “deep skolemisation”.
which is indeed what the paper "Practical type inference for arbitrary-rank types" on page 21 is talking about:
Hence, perhaps we can solve the problem by enriching the definition of subsumption, so that the type systems of Figure 5 and 6 admit the same programs. That is the reason for the new subsumption judgement ⊢dsk, defined in Figure 7. This relation subsumes ⊢ol; it relates strictly more types.