GADTs

A constructor that fixes the type

In an ordinary algebraic data type every constructor returns the same type with the same parameter: data Expr a = Lit Int has constructors whose result is Expr a for every a. A GADT lets each constructor choose the parameter, so the type of the tree records what kind of value it produces:

data Expr a where IntLit :: Int -> Expr Int BoolLit :: Bool -> Expr Bool

IntLit builds an Expr Int and nothing else, and BoolLit an Expr Bool. Pattern matching on the constructor then refines the type inside the branch, which is what makes the evaluator below type check without a single cast.

A typed expression

{-# LANGUAGE GADTs #-} module Main (main) where data Expr a where IntLit :: Int -> Expr Int BoolLit :: Bool -> Expr Bool Add :: Expr Int -> Expr Int -> Expr Int If :: Expr Bool -> Expr a -> Expr a -> Expr a eval :: Expr a -> a eval (IntLit n) = n eval (BoolLit b) = b eval (Add left right) = eval left + eval right eval (If test yes no) = if eval test then eval yes else eval no main :: IO () main = do print (eval (Add (IntLit 2) (IntLit 3))) print (eval (If (BoolLit True) (IntLit 1) (IntLit 2)))

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

5
1

The evaluator

The signature eval :: Expr a -> a is the whole idea: the evaluator promises a value of the type the expression says it has. Four equations satisfy the promise without a Maybe and without an error branch, because the GADT makes these the only cases that exist:

The type checker accepts the four equations because it knows something in each branch that an ordinary data type does not say: which constructor built the value and therefore what its parameter is.

The tree that cannot be built

The other side of the same information is that a wrong tree does not compile. Adding a boolean literal to an integer is a type error at the construction, before any evaluation:

{-# LANGUAGE GADTs #-} module Main (main) where data Expr a where IntLit :: Int -> Expr Int BoolLit :: Bool -> Expr Bool Add :: Expr Int -> Expr Int -> Expr Int eval :: Expr a -> a eval (IntLit n) = n eval (BoolLit b) = b eval (Add left right) = eval left + eval right main :: IO () main = print (eval (Add (IntLit 1) (BoolLit True)))

ghc -Wall -fno-code bad.hs

bad.hs:16:37: error: [GHC-83865]
    • Couldn't match type ‘Bool’ with ‘Int’
      Expected: Expr Int
        Actual: Expr Bool
    • In the second argument of ‘Add’, namely ‘(BoolLit True)’
      In the first argument of ‘eval’, namely
        ‘(Add (IntLit 1) (BoolLit True))’
    • In the first argument of ‘print’, namely
        ‘(eval (Add (IntLit 1) (BoolLit True)))’
  |
16 | main = print (eval (Add (IntLit 1) (BoolLit True)))
   |                                    ^^^^^^^^^^^^

The error is at the second argument of Add, which promised an Expr Int and got an Expr Bool. With an ordinary data Expr a the same program would build the tree and fail at run time inside eval, or need a Maybe in the result; the GADT moved the failure to the compiler.

When a GADT is worth it

The next lesson stays in the type system and moves the case analysis to the type level: a type family that maps a type to another type, and a class whose methods depend on it.

Exercises

  1. Add a Mul :: Expr Int -> Expr Int -> Expr Int constructor and its equation.
  2. Add a comparison Less :: Expr Int -> Expr Int -> Expr Bool and evaluate it.
  3. Write a size :: Expr a -> Int that counts the constructors.
  4. Add a StringLit and explain how the evaluator changes.
  5. Explain why eval needs no error branch for a BoolLit.
  6. Try the wrong tree with a plain data Expr a and compare the error with the one above.

Questions

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

  1. What does a GADT constructor declare?

    Answer

    Its own result type, such as Expr Int

    The signature after :: fixes the result type, which is what an ordinary constructor cannot do.

  2. Why does eval (IntLit n) = n type check?

    Answer

    Matching IntLit refines the result type a to Int

    The GADT tells the checker that this branch is the Expr Int case.

  3. What happens to Add (IntLit 1) (BoolLit True)?

    Answer

    It is a compile error at the second argument of Add

    Add expects two Expr Int values, and BoolLit gives an Expr Bool.

  4. What does this program print? {-# LANGUAGE GADTs #-} module Main (main) where data Expr a where IntLit :: Int -> Expr Int eval :: Expr a -> a eval (IntLit n) = n main :: IO () main = print (eval (IntLit 7))

    Answer

    7

    The only constructor is an Int literal, and eval returns its number.

  5. Which extension enables the data ... where syntax?

    Answer

    GADTs

    The pragma is GADTs, as at the top of every program on this page.

  6. What does eval :: Expr a -> a promise?

    Answer

    A value of the type the expression says it has

    The result type is the parameter of the expression, which the constructors fix.

  7. What does this program print? {-# LANGUAGE GADTs #-} module Main (main) where data Box a where BoxInt :: Int -> Box Int unbox :: Box a -> a unbox (BoxInt n) = n main :: IO () main = print (unbox (BoxInt 3) + 1)

    Answer

    4

    unbox returns 3 and the expression adds 1.

  8. What is the cost of a GADT compared with a plain data type?

    Answer

    A pragma and error messages that are harder to read

    The representation is the same; the type checker does more and reports more.

  9. Why does an ordinary data Expr a = IntLit Int | BoolLit Bool fail here?

    Answer

    Every constructor returns Expr a, so the evaluator cannot know which branch gives what

    Without the refined result type, eval would need a cast or a Maybe.

  10. What does this program print? module Main (main) where data Expr a = IntLit Int | BoolLit Bool eval :: Expr Int -> Int eval (IntLit n) = n eval (BoolLit _) = 0 main :: IO () main = print (eval (IntLit 5))

    Answer

    5

    The plain type needs a branch for BoolLit, here returning 0, and the IntLit branch returns 5.

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