GADTs in Haskell: Typed Expression Trees Made Simple

Problem: Runtime Errors in Expression Evaluators

When building a small interpreter, a common pattern is to define an algebraic data type (ADT) for expressions:

data Expr = IntLit Int | Add Expr Expr | Mul Expr Expr

Pattern matching on Expr is straightforward, but the type system offers no guarantee that the operands to Add and Mul are integers. If you later extend the language with booleans or strings, accidental mismatches can slip through until runtime, causing crashes or subtle bugs.

Thesis: Generalized Algebraic Data Types (GADTs) let you encode type‑refinement per constructor, turning impossible cases into compile‑time errors.

GADTs 101

A GADT is declared just like a normal data type, but each constructor can specify a different result type. In Haskell, the syntax uses a vertical bar and a type signature after the constructor name:

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

The type variable a is the “result type” of the expression. Each constructor states what that result type will be. The compiler now knows that Add always yields an Expr Int, so you can never accidentally add a boolean.

Concrete Example: A Typed Arithmetic Language

1. Define the GADT. The following snippet shows a minimal typed expression language with integers and booleans.
2. Write an evaluator. The evaluator’s type signature mirrors the GADT: it returns a value of the same type the expression promises.
3. Compile. GHC rejects any expression that violates the type constraints, e.g., adding a boolean to an integer.

{-# LANGUAGE GADTs #-}
module TypedExpr where

-- 1. GADT definition

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

-- 2. Evaluator

eval :: Expr a -> a
eval (IntLit n)   = n
eval (BoolLit b) = b
eval (Add e1 e2)  = eval e1 + eval e2
eval (And e1 e2)  = eval e1 && eval e2

-- 3. Example usage

-- This compiles:
expr1 :: Expr Int
expr1 = Add (IntLit 3) (IntLit 4)

-- This fails to compile – GHC will emit a type error:
-- expr2 :: Expr Int
-- expr2 = Add (BoolLit True) (IntLit 5)

Running ghc -Wall TypedExpr.hs produces no warnings for expr1, but attempts to compile expr2 result in a clear error that the second operand of Add must be Expr Int, not Expr Bool. The error message is concise because the GADT already encoded the constraint.

Trade‑offs and Limitations

Aspect	Benefit	Drawback
Type Safety	Prevents impossible patterns at compile time.	Requires more explicit type annotations in complex code.
Readability	Expresses intent clearly when familiar.	Can be intimidating to newcomers; error messages may be verbose.
Compilation Time	Negligible for small modules.	May increase compile times in large codebases due to richer inference.
Runtime Performance	No overhead; GHC optimizes away GADT tags.	None.

Because GADTs add information to the type checker, the compiler sometimes needs guidance. Adding explicit type signatures or using -Werror=missing-deriving can help surface ambiguous errors early.

Actionable Steps for Your Project

1. Start Small. Wrap a single feature (e.g., arithmetic) in a GADT before expanding.
2. Use -Wall and -Werror. These flags surface missing annotations and ambiguous types.
3. Profile Compilation. If you hit long compile times, consider refactoring large GADT modules into smaller, type‑checked units.
4. Document Constructor Semantics. A brief comment per constructor clarifies the intended result type for collaborators.
5. Leverage -ddump-tc. When debugging, this flag shows the inferred type of each expression, confirming that the GADT behaves as expected.

By following these guidelines, you can harness GADTs to make your Haskell code safer and more maintainable without sacrificing performance.