RankNTypes and scope of `forall'

875 views Asked by At

What is the difference between these?

{-# LANGUAGE RankNTypes #-}

f :: forall a. a -> Int
f _ = 1

g :: (forall a. a) -> Int
g _ = 1

In particular, why do I get an error with g ()?

ghci> f ()
1
ghci> g ()
<interactive>:133:3:
    Couldn't match expected type `a' with actual type `()'
      `a' is a rigid type variable bound by
          a type expected by the context: a at <interactive>:133:1
    In the first argument of `g', namely `()'
    In the expression: g ()
    In an equation for `it': it = g ()

ghci> f undefined
1
ghci> g undefined
1
2

There are 2 answers

3
leftaroundabout On BEST ANSWER

f is just an ordinary polymorphic Haskell98 function, except the forall is written out explicitly. So all the type variables in the signature are parameters the caller gets to choose (without any constraints); in your case it's resolved a ~ ().

g OTOH has a rank-2 type. It requires that its argument has the polymorphic type forall a . a. () does not have such a type, it is monomorphic. But undefined has this type (in fact, only undefined, and error etc.), if we add the explicit forall again.

Perhaps it becomes clearer with a less trivial Rank2 function:

h :: (forall a . (Show a, Num a) => a) -> String
h a = show a1 ++ " :: Double\n"
     ++ show a2 ++ " :: Int"
 where a1 :: Double; a2 :: Int
       a1 = a; a2 = a

GHCi> putStrLn $ h 4
4.0 :: Double
4 :: Int

but I can't do

GHCi> putStrLn $ h (4 :: Integer)

<‌interactive>:4:15:
    Could not deduce (a ~ Integer)
    from the context (Show a, Num a)
      bound by a type expected by the context: (Show a, Num a) => a
      at <‌interactive>:4:12-27
      `a' is a rigid type variable bound by
          a type expected by the context: (Show a, Num a) => a
          at <‌interactive>:4:12
    In the first argument of `h', namely `(4 :: Integer)'
    In the second argument of `($)', namely `h (4 :: Integer)'
    In the expression: putStrLn $ h (4 :: Integer)

2
Aadit M Shah On

Think of forall as an anonymous type function. All data types in Haskell which have type variables in their type signature implicitly have a forall. For example consider:

f :: a -> Int
f _ = 1

The above function f takes an argument of any type and returns an Int. Where does the a come from? It comes from the forall quantifier. Hence it's equivalent to:

f :: (forall a . a -> Int)
f _ = 1

The forall quatifier can be used for any data type, not just functions. For example consider the types of the following values:

() :: ()
10 :: Int
pi :: Floating a => a

Here () and 10 are monomorphic (i.e. they can only be of one concrete type). On the other hand pi is polymorphic with a typeclass constraint (i.e. it can be of any type as long as that type is a instance of Floating). The type of pi written out explicitly is:

pi :: (forall a . Floating a => a)

Again the forall quantifier acts like a type function. It provides you the type variable a. Now consider the type of function g:

g :: (forall a . a) -> Int
g _ = 1

Here g expects an argument of type forall a . a and returns an Int. This is the reason g () doesn't work: () is of type (), not of type forall a . a. In fact the only value of type forall a . a is undefined:

undefined :: a

Written out explicitly with forall:

undefined :: (forall a . a)

If you noticed I've always put parentheses around the forall quantifications. The reason I did this is to show you that when you use a forall quantification on a function the quantification extends all the way to the right. This is just like a lambda: if you don't put parentheses around the lambda Haskell will extend the lambda function all the way to the right. Hence the type of f is (forall a . a -> Int) and not (forall a . a) -> Int.

Remember in the first case Haskell expects the type of the argument to be a (i.e. anything). However in the second case Haskell expects the type of the argument to be (forall a . a) (i.e. undefined). Of course if you try to evaluate undefined then your program will immediately halt with an error. Fortunately you're not trying to evaluate it.