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

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

  1. Write applyThree :: (forall a. a -> String) -> [String] and call it with a function that shows its argument.
  2. Give applyBoth (\x -> x) the annotation it needs and compile it.
  3. Explain why the rank-1 version cannot be fixed by a type annotation on the call.
  4. Write a rank-2 function that takes a polymorphic mempty and returns two values.
  5. Read the type of runST and point at the forall.
  6. 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.

  1. What does moving forall inside 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.

  2. Which extension enables the signatures of this lesson?

    Answer

    RankNTypes

    RankNTypes is the extension, and GHC2021 includes it.

  3. What does the error word rigid mean?

    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.

  4. 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.

  5. 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.

  6. What does runST :: (forall s. ST s a) -> a use 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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