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:
- IntLit n refines a to Int, so the branch returns n.
- BoolLit b refines it to Bool, so the branch returns b.
- Add takes two Expr Int values, so eval left and eval right are Int and + applies.
- If has an Expr Bool test and two branches of the same a, so if applies and both branches have the result type.
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
- An interpreter whose terms have different types is the classic case, and this lesson is the small version of it.
- A typed protocol or a state machine where the constructor records the phase is another, and GADTs keep the transitions honest.
- A tagless encoding of a language, where the constructors are functions and the type is the interpretation, needs rank-N types, which is the lesson after the next one.
- A plain data type with a tag is simpler when every constructor returns the same type; the GADT buys type refinement and costs a pragma and some error messages that are harder to read.
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
- Add a Mul :: Expr Int -> Expr Int -> Expr Int constructor and its equation.
- Add a comparison Less :: Expr Int -> Expr Int -> Expr Bool and evaluate it.
- Write a size :: Expr a -> Int that counts the constructors.
- Add a StringLit and explain how the evaluator changes.
- Explain why eval needs no error branch for a BoolLit.
- 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.
-
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.
-
Why does
eval (IntLit n) = ntype check?Answer
Matching IntLit refines the result type a to Int
The GADT tells the checker that this branch is the Expr Int case.
-
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.
-
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.
-
Which extension enables the
data ... wheresyntax?Answer
GADTsThe pragma is GADTs, as at the top of every program on this page.
-
What does
eval :: Expr a -> apromise?Answer
A value of the type the expression says it has
The result type is the parameter of the expression, which the constructors fix.
-
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.
-
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.
-
Why does an ordinary
data Expr a = IntLit Int | BoolLit Boolfail 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.
-
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