Rank-N types
forall and rank 1
Every polymorphic signature is a forall that the compiler inserts for you. These two lines are the same type:
id :: a -> a
id :: forall a. a -> a
The forall says the caller chooses a: id 3 chooses Int and id "x" chooses String. In both cases the quantifier is at the outside of the type, which is called rank 1, and the choice is made once per call. The explicit form becomes interesting when the forall moves inside the parentheses, because then the function chooses instead of the caller.
A signature that is too narrow
A function that applies its argument to an Int and to a Bool needs the argument to work for both. The rank-1 signature says the caller picks one type for the whole call, and the compiler rejects the body:
module Main (main) where
applyBoth :: (a -> a) -> (Int, Bool)
applyBoth f = (f 3, f True)
main :: IO ()
main = print (applyBoth id)
ghc -Wall -fno-code narrow.hs
narrow.hs:4:16: error: [GHC-25897]
• Couldn't match expected type ‘Int’ with actual type ‘a’
‘a’ is a rigid type variable bound by
the type signature for:
applyBoth :: forall a. (a -> a) -> (Int, Bool)
at narrow.hs:3:1-36
• In the expression: f 3
In the expression: (f 3, f True)
In an equation for ‘applyBoth’: applyBoth f = (f 3, f True)
• Relevant bindings include
f :: a -> a (bound at narrow.hs:4:11)
applyBoth :: (a -> a) -> (Int, Bool) (bound at narrow.hs:4:1)
|
4 | applyBoth f = (f 3, f True)
| ^
The word rigid is the key: inside the body the a is fixed by the caller and cannot become Int. The signature is honest about what the caller would have to provide, and no caller can provide a function of one fixed type that works for every type.
Rank 2 and a polymorphic argument
Moving the forall inside the argument type is what the body needs:
applyBoth :: (forall a. a -> a) -> (Int, Bool)
Read it as: the argument must be a function that works for every a, and the caller of applyBoth passes such a function once. Inside the body, f can be used at Int and at Bool, because its type says it is polymorphic and the quantifier is in scope for the body. The rank is the nesting depth of the quantifier: rank 1 at the outside, rank 2 inside one argument, rank 3 inside a function that takes a function that takes a polymorphic function.
The program that type checks
{-# LANGUAGE RankNTypes #-}
module Main (main) where
applyBoth :: (forall a. a -> a) -> (Int, Bool)
applyBoth f = (f 3, f True)
main :: IO ()
main = print (applyBoth id)
ghc -Wall -O1 -o rankn rankn.hs
./rankn
(3,True)
id is the only simple function of type forall a. a -> a and it satisfies the argument. The result is the pair of the two calls, one at Int and one at Bool, which the rank-1 signature could not express. A lambda such as \x -> x needs a type annotation in this position, because the compiler does not infer a rank-2 type for an argument on its own.
Where the rank matters
- runST :: (forall s. ST s a) -> a is rank 2, and the forall s is what keeps a mutable reference from escaping its computation. The lesson on arrays and the one on FFI both rest on that trick.
- A lens is a function that is polymorphic in the functor, so its type has a forall inside the argument; the lens package is a library of rank-2 functions.
- A continuation-passing fold such as foldr :: (a -> b -> b) -> b -> [a] -> b is rank 1, and that is why it is simpler than the monadic fold that generalises it.
The extension is RankNTypes, and GHC2021 enables it, so a modern module can write the signature without a pragma. The cost is inference: a rank-2 argument usually needs an explicit annotation at the call site, which is the trade the next lesson makes again with existential types.
Exercises
- Write applyThree :: (forall a. a -> String) -> [String] and call it with a function that shows its argument.
- Give applyBoth (\x -> x) the annotation it needs and compile it.
- Explain why the rank-1 version cannot be fixed by a type annotation on the call.
- Write a rank-2 function that takes a polymorphic mempty and returns two values.
- Read the type of runST and point at the forall.
- Explain what the rank of a type is in one sentence.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does moving
forallinside an argument type change?Answer
The function can use its argument at several types
A rank-2 argument is polymorphic for the body, which is why f 3 and f True both work.
-
Which extension enables the signatures of this lesson?
Answer
RankNTypesRankNTypes is the extension, and GHC2021 includes it.
-
What does the error word
rigidmean?Answer
The type variable is fixed by the caller and cannot be changed in the body
The body cannot choose a for the caller, so a is rigid inside it.
-
What does this program print?
{-# LANGUAGE RankNTypes #-} module Main (main) where applyBoth :: (forall a. a -> a) -> (Int, Bool) applyBoth f = (f 3, f True) main :: IO () main = print (applyBoth id)Answer
(3,True)
id returns its argument, so the pair is the Int 3 and the Bool True.
-
What is the rank of
id :: forall a. a -> a?Answer
Rank 1
The quantifier is at the outside of the type, which is rank 1.
-
What does
runST :: (forall s. ST s a) -> ause the rank for?Answer
To keep a mutable reference from escaping the computation
The forall s is chosen by runST, so the state token cannot leak out of the call.
-
What does this program print?
{-# LANGUAGE RankNTypes #-} module Main (main) where applyAll :: (forall a. a -> String) -> [String] applyAll f = [f (1 :: Int), f True] main :: IO () main = putStrLn (concat (applyAll (\_ -> "x")))Answer
xx
The function ignores its argument and returns one x per call, and concat joins the two.
-
Why does the rank-1 signature fail?
Answer
The caller chooses one a, so the body cannot use f at both Int and Bool
The quantifier at the outside means one type per call, and the body needs two.
-
What does this program print?
module Main (main) where apply :: (Int -> Int) -> Int apply f = f 4 + 1 main :: IO () main = print (apply (* 2))Answer
9
The function doubles 4 to 8 and the body adds 1, so the result is 9.
-
What does a rank-2 argument usually need at the call site?
Answer
An explicit type annotation for an argument that is a lambda
The compiler does not infer a polymorphic type for an unannotated lambda argument, so the annotation is written.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev