Existential types

Why a forall in a constructor

A list holds values of one type: [Int], [String], [a] for a caller that picks a. A list of an Int, a String and a Bool has no such type. An existential type puts the forall inside the constructor, so every value carries its own type and the list holds one type again:

data Box = forall a. Show a => Box a

The constructor Box takes a value of any type that has a Show instance and returns a Box with no type parameter. The price is that the only operations available on the value inside are the ones the constraint guarantees: here show, and nothing else. That is the whole trade of the lesson.

A list of differently typed values

{-# LANGUAGE ExistentialQuantification #-} module Main (main) where data Box = forall a. Show a => Box a boxes :: [Box] boxes = [Box (3 :: Int), Box "text", Box True] main :: IO () main = mapM_ (\(Box value) -> print value) boxes

ghc -Wall -O1 -o exist exist.hs
./exist

3
"text"
True

The pattern \(Box value) -> print value brings the value out with its type hidden and its Show instance available, which is exactly enough for print. The output shows the three types in the way print shows them: a number without quotes, a string with quotes, a boolean. A [Show]-style list could not exist, because Show is a class and not a type.

The value that tries to escape

Without the constraint there is nothing to do with the value, and a function that tries to return it does not compile. The type it would have to promise is the type of the caller, and the constructor does not know it:

{-# LANGUAGE ExistentialQuantification #-} module Main (main) where data Box = forall a. Box a unbox :: Box -> a unbox (Box value) = value main :: IO () main = print (unbox (Box (3 :: Int)))

ghc -Wall -fno-code escape.hs

escape.hs:8:21: error: [GHC-25897]
    • Couldn't match expected type ‘a’ with actual type ‘a1’
      ‘a1’ is a rigid type variable bound by
        a pattern with constructor: Box :: forall a. a -> Box,
        in an equation for ‘unbox’
        at escape.hs:8:8-16
      ‘a’ is a rigid type variable bound by
        the type signature for:
          unbox :: forall a. Box -> a
        at escape.hs:7:1-17
    • In the expression: value
  |
8 | unbox (Box value) = value
  |                     ^^^^^

Two rigid variables that are not the same: the a of the signature is chosen by the caller, and the a1 of the constructor by the value that was boxed. Returning one as the other would be a lie the type system refuses. The second error of the same build is the consequence: print has no Show instance for an unknown type, which is the constraint the first version added.

When an existential is the answer

The alternative without the extension is a sum type with one constructor per case, which is clearer while the set is small and closed. The existential is the tool when the set is open: a library cannot add a constructor to your sum type, and it can add a value to your list of boxes.

Exercises

  1. Add a numeric operation to the box with a Num constraint and a sum of all the boxes.
  2. Write data Any = forall a. Any a and explain what you can and cannot do with it.
  3. Make the box hold a function a -> String next to the value instead of a constraint.
  4. Compare the box with a sum type of three constructors for the same three values.
  5. Explain why Show is the only operation available in the first program.
  6. Write a list of shapes with an existential and with a GADT and compare the two types.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does data Box = forall a. Show a => Box a put in the constructor?

    Answer

    A hidden type with a Show instance

    The forall inside the constructor hides the type and keeps the constraint, which is what an existential is.

  2. What can you do with the value inside a Box?

    Answer

    Only what the constraint allows, here show

    The type is hidden, so only the operations of the constraint are available.

  3. Why does unbox :: Box -> a fail?

    Answer

    The type of the boxed value is not the caller type a

    The two foralls are different rigid variables, and the body cannot return one as the other.

  4. What does this program print? {-# LANGUAGE ExistentialQuantification #-} module Main (main) where data Box = forall a. Show a => Box a main :: IO () main = mapM_ (\(Box v) -> putStrLn (show v)) [Box (1 :: Int), Box True]

    Answer

    1 and True on two lines

    Each box is shown by its own instance and putStrLn prints the string.

  5. Which extension enables the syntax of this lesson?

    Answer

    ExistentialQuantification

    The pragma is ExistentialQuantification; a GADT can express the same with data ... where.

  6. What is the alternative to an existential for a small closed set?

    Answer

    A sum type with one constructor per case

    A sum type is clearer while the cases are known; the existential is for an open set.

  7. What does this program print? {-# LANGUAGE ExistentialQuantification #-} module Main (main) where data Box = forall a. Show a => Box a main :: IO () main = print (length [Box (1 :: Int), Box True])

    Answer

    2

    The list has two boxes and length does not need the hidden types.

  8. What does a GADT give that an existential does not?

    Answer

    A refined result type, so the consumer knows which case it has

    A GADT constructor fixes the type parameter, which is the information an existential hides.

  9. What does this program print? module Main (main) where data Shape = Circle Double | Square Double area :: Shape -> Double area (Circle r) = 3 * r * r area (Square s) = s * s main :: IO () main = print (area (Square 3))

    Answer

    9.0

    The square of 3 is 9 and print shows the Double with its decimal.

  10. Why can a list not hold [3, "text", True] directly?

    Answer

    Every element of a list has the same type

    A list is homogeneous, and the existential box makes the element type one again.

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