Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 57 ยท Advanced types

GADTs, Type Families and DataKinds

Use GADTs for a type-safe expression evaluator, type families to compute types, and DataKinds with phantom types to make illegal states unrepresentable.

Ordinary algebraic data types let every constructor build a value of the same type: Circle 1.0 and Rect 2 3 are both Shape. That is often too coarse. Suppose you model a tiny language with numbers and booleans. A plain Expr type would happily let you write "add True to 3", and your evaluator would have to return a Maybe or crash.

This lesson shows three related features that let the type carry more information, so wrong programs fail to compile: GADTs, type families and DataKinds. They are advanced, so go slowly. The Haskell blocks are read-only because GHC is not installed on this site. The runnable stand-ins in JavaScript can only check the same rules at run time, and they say so.

Types that know more

GADT Each constructor picks its own result type.
Type family A function from types to types.
DataKinds Values become type-level labels.

All three are checked at compile time.

1 / 2

The problem: an untyped expression tree

Here is the ordinary version:

HASKELL
data Expr
  = IntE Int
  | BoolE Bool
  | Add Expr Expr
  | If Expr Expr Expr
  | Eq Expr Expr

eval :: Expr -> Maybe (Either Int Bool)

The evaluator must handle Add (BoolE True) (IntE 3) somehow, and every caller must unpack an Either Int Bool. The bug is in the expression, but we only find out when we run it. We would like Add (BoolE True) (IntE 3) to be rejected by GHC.

GADTs: constructors with their own result types

A generalised algebraic data type is declared with where and an explicit signature for each constructor, and the result type may be more specific than the declared type:

HASKELL
# LANGUAGE GADTs #

data Expr a where
  IntE  :: Int  -> Expr Int
  BoolE :: Bool -> Expr Bool
  Add   :: Expr Int -> Expr Int -> Expr Int
  Eq    :: Expr Int -> Expr Int -> Expr Bool
  If    :: Expr Bool -> Expr a -> Expr a -> Expr a

Read the constructor types as rules. Add takes two Expr Int and gives an Expr Int. If needs a boolean condition, and both branches must have the same type a, whatever it is. Now Add (BoolE True) (IntE 3) is a type error, because BoolE True has type Expr Bool and Add wants Expr Int.

The evaluator is where the payoff shows:

HASKELL
eval :: Expr a -> a
eval (IntE n)    = n
eval (BoolE b)   = b
eval (Add x y)   = eval x + eval y
eval (Eq x y)    = eval x == eval y
eval (If c t e)  = if eval c then eval t else eval e

The return type is just a: an Expr Int evaluates to an Int, an Expr Bool to a Bool, with no Maybe and no Either. In the IntE n clause, GHC learns from the pattern that a is Int, so returning n is fine. This is called type refinement by pattern matching. There are two small costs: you usually need an explicit type signature on functions that match on a GADT, because GHC cannot infer them, and deriving (Show) needs the standalone form deriving instance Show (Expr a).

HASKELL
example :: Expr Int
example = If (Eq (IntE 2) (Add (IntE 1) (IntE 1))) (IntE 100) (IntE 0)

-- eval example == 100

GADTs also describe things like a vector whose length is part of its type, a well-typed stack machine, or a state machine whose transitions are checked. (If you have not seen trees evaluated yet, Recursive Data Types and Trees builds the plain version first.)

Type families: functions on types

A type family computes a type from other types, the way a normal function computes a value. A closed family lists its equations in order, like a function definition with patterns:

HASKELL
# LANGUAGE TypeFamilies #

import Data.Kind (Type)
import Data.Text (Text)

type family Elem (c :: Type) :: Type where
  Elem [a]  = a
  Elem Text = Char

firstElem :: [a] -> Elem [a]
firstElem = head            -- Elem [a] reduces to a

GHC reduces Elem [Int] to Int while it type checks. The more common use is an associated type, a family that belongs to a type class:

HASKELL
# LANGUAGE TypeFamilies #

import Data.Kind (Type)

class Container f where
  type Item f :: Type
  empty  :: f
  insert :: Item f -> f -> f
  toL    :: f -> [Item f]

instance Container [a] where
  type Item [a] = a
  empty  = []
  insert = (:)
  toL    = id

Each instance says what Item means for it. A set of Int might define Item IntSet = Int, while a text buffer could say Item Text = Char. This is how libraries such as vector and mono-traversable talk about "the element type of a container" without making the element a separate class parameter. There are also open families, where any module may add equations, and data families, where each instance gets its own constructors.

DataKinds and phantom types

A phantom type is a type parameter that does not appear in any field. It exists only so the type checker can tell values apart:

HASKELL
newtype Distance unit = Distance Double

data Meters
data Feet

addDistance :: Distance u -> Distance u -> Distance u
addDistance (Distance a) (Distance b) = Distance (a + b)

-- addDistance (Distance 1 :: Distance Meters) (Distance 2 :: Distance Feet)
-- is a type error: Meters and Feet differ

Meters and Feet are empty types used purely as labels. The compiler now refuses to add metres to feet, and the runtime representation is still one Double (for a newtype, the wrapper disappears completely).

DataKinds goes further: it lets you use the constructors of an ordinary data type as types. Instead of inventing empty data Meters, you reuse an enumeration, and a kind signature says the parameter must be one of its values:

HASKELL
# LANGUAGE DataKinds, KindSignatures #

data DoorState = Opened | Closed

newtype Door (s :: DoorState) = Door String

openDoor :: Door 'Closed -> Door 'Opened
openDoor (Door name) = Door name

closeDoor :: Door 'Opened -> Door 'Closed
closeDoor (Door name) = Door name

front :: Door 'Closed
front = Door "front"

The tick in 'Closed marks "the promoted constructor, not a type" (you can often omit it when there is no name clash). Now openDoor (openDoor front) does not compile, because the first call produces Door 'Opened, which openDoor does not accept. The state machine lives in the types.

Combine DataKinds with a GADT and you get the famous length-indexed vector, where head can only be applied to a vector whose type says it is non-empty:

HASKELL
# LANGUAGE DataKinds, GADTs, KindSignatures #

import Data.Kind (Type)

data Nat = Z | S Nat

data Vec (n :: Nat) (a :: Type) where
  VNil  :: Vec 'Z a
  VCons :: a -> Vec n a -> Vec ('S n) a

vhead :: Vec ('S n) a -> a
vhead (VCons x _) = x      -- no VNil case needed: it cannot happen

GHC knows that vhead is only called on Vec ('S n) a, so the VNil case is impossible and does not need a clause.

When to use these features

Type-level programming is a tool with a price: error messages get harder to read, and code becomes harder for newcomers. Reach for it when:

  • a runtime error case keeps appearing that a type could remove (the evaluator that returns Maybe),
  • a protocol or state machine has steps that must happen in order,
  • units, IDs or currencies of the same representation must not be mixed up (phantom types are cheap and beginner friendly).

For everything else, plain data types, Maybe and Either and tests are usually the better trade. The extension names themselves are explained in GHC Extensions Worth Knowing.

Stand-ins in JavaScript

JavaScript has no compile-time types, so these stand-ins do the checking at run time. They show which programs the types would reject, but only when the program runs. In Haskell the rejection happens before anything runs, and the evaluator needs no error branch at all.

JS A typed expression evaluator (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The second stand-in imitates DataKinds and phantom types: a "state label" that decides which operations are allowed.

JS A door whose state is part of its type (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

In Haskell neither openDoor opened nor the metres-plus-feet call would reach the point of being run, and the label costs nothing at run time.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What makes a GADT different from an ordinary data type?

    In a GADT, a constructor such as IntE :: Int -> Expr Int fixes the type parameter, so matching on it tells GHC more about the type.
  2. 2. Why can the GADT evaluator have the type Expr a -> a?

    The constructors only allow well-typed trees, and pattern matching refines a to the right type in each clause.
  3. 3. What is a type family?

    A type family such as Elem [a] = a is evaluated by the type checker, like a function on types.
  4. 4. What does DataKinds allow?

    DataKinds promotes data constructors to the type level, which is useful for state machines and length-indexed vectors.
  5. 5. What is a phantom type parameter?

    Phantom parameters have no runtime content. They let the type checker keep apart values with the same representation, such as metres and feet.

Summary

  • GADTs let each constructor choose its result type, so evaluators can be written as Expr a -> a with no error case.
  • Pattern matching on a GADT refines the type; functions over GADTs need explicit signatures.
  • Type families compute types: closed, open, and associated with a type class.
  • Phantom types label values at no run-time cost; DataKinds promotes constructors so the labels can be an ordinary enumeration.
  • Combining GADTs and DataKinds gives length-indexed vectors and checked state machines.
  • Use these tools when they remove a real runtime error case. Otherwise prefer simpler types.

Next: Lenses and Optics.