Skip to content
LumenaryAcademy
Practice 55 min

Algebraic data types and records

Model your domain with sums and products, so that the compiler knows every shape your data can take.

Code tested · 5AI-draftedAwaiting review by a computer scientist
MotivationH

Types that say exactly what you mean

Suppose you are writing software for a delivery service. A parcel is either waiting at the depot, in transit with a particular driver, or delivered at a particular time. In many languages you would model this with an object holding a status string, a driver field that is sometimes null, and a delivery-time field that is sometimes null. Nothing stops a bug from producing a parcel whose status says "waiting" but which also has a delivery time. The data can be in states that make no sense, and every function must defend itself against them.

Haskell lets you say exactly what you mean:

haskell
data Parcel
  = Waiting
  | InTransit Driver
  | Delivered Time

A parcel is one of three things, and each carries precisely the data that belongs to it. A delivered parcel has a time and no driver; a waiting one has neither. The impossible states cannot even be written down. Experienced programmers call this making illegal states unrepresentable, and it is one of the most practical ideas Haskell has spread to other languages: Rust's enum, Swift's enum with associated values, Kotlin's sealed classes, TypeScript's discriminated unions and Java's sealed interfaces with records all express it.

This lesson shows how to declare such types, how to work with them by pattern matching, and how the two most important ones in the standard library, Maybe and Either, replace null references and many exceptions.

DefinitionsH

Declaring types

Definition— data declaration and constructors

data T = C1 fields | C2 fields | ... declares a new type T whose values are built with the constructors C1, C2 and so on. Constructor names start with a capital letter. Each constructor can carry zero or more fields, written as their types. A constructor is also an ordinary function: Circle :: Double -> Shape.

Definition— Sum type and product type

A type with several constructors, this or that, is a sum type (Bool = False | True). A constructor with several fields, this and that, is a product type (a pair is the simplest). Types built from sums of products are called algebraic data types.

Definition— Record

A record gives each field a name: data Book = Book { title :: String, year :: Int }. Each name becomes a function that extracts the field (title :: Book -> String), and b { year = 2026 } builds a copy of b with one field changed. Nothing is modified: records are immutable like everything else.

Definition— deriving

deriving (Show, Eq, Ord) asks the compiler to write standard instances for you: show to print a value as source code, == comparing constructor by constructor and field by field, and an ordering in which earlier constructors come first and fields are compared left to right.

Definition— newtype and type synonym

newtype Celsius = Celsius Double declares a genuinely new type with exactly one constructor and one field. It costs nothing at run time (the wrapper is erased) but the compiler will not let you mix it up with other Doubles. type Station = String is only a synonym: a second name for an existing type, useful for documentation, with no extra checking.

Worked examplesH

Sums, records, recursion

A sum type

haskell
-- A sum type: a shape is a circle OR a rectangle OR a triangle.
-- Each constructor carries its own fields.
data Shape
  = Circle Double
  | Rectangle Double Double
  | Triangle Double Double Double
  deriving (Show, Eq)

area :: Shape -> Double
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
area (Triangle a b c) = sqrt (s * (s - a) * (s - b) * (s - c)) -- Heron's formula
  where
    s = (a + b + c) / 2

corners :: Shape -> Int
corners shape = case shape of
  Circle _ -> 0
  Rectangle _ _ -> 4
  Triangle {} -> 3

main :: IO ()
main = do
  let shapes = [Circle 1, Rectangle 3 4, Triangle 3 4 5]
  mapM_ (\s -> putStrLn (show s ++ " has area " ++ show (area s))) shapes
  print (map corners shapes)
  print (Rectangle 3 4 == Rectangle 3 4, Rectangle 3 4 == Rectangle 4 3)
  print (map Circle [0.5, 2])
text
Circle 1.0 has area 3.141592653589793
Rectangle 3.0 4.0 has area 12.0
Triangle 3.0 4.0 5.0 has area 6.0
[0,4,3]
(True,False)
[Circle 0.5,Circle 2.0]

To work with a Shape you match on its constructor, and the pattern names the fields. Triangle {} is a handy pattern that matches a constructor regardless of its fields. Derived equality compares field by field, so a 3-by-4 rectangle is not equal to a 4-by-3 one; if you wanted those to be equal, you would write the Eq instance yourself (lesson 6 shows how). The last line uses Circle as a function and maps it over a list of radii.

Now imagine adding a fourth constructor, Hexagon Double, a year from now. With -Wall, GHC immediately lists every function whose patterns no longer cover all cases: area, corners, and any other. In a large codebase that warning is worth a great deal; it turns "find every place that needs updating" from a search into a checklist the compiler writes for you.

Records, Maybe and Either

Two types from the Prelude deserve to be memorised. Here are their complete definitions:

haskell
data Maybe a = Nothing | Just a
data Either a b = Left a | Right b

Maybe a is "an a, or nothing": the honest type of a lookup that may fail. Either e a is "an error of type e, or a result of type a". By convention Left holds the error and Right the result (it is the right answer). Neither is built into the language; they are ordinary algebraic data types with a type parameter.

haskell
-- A product type with named fields: a record.
data Book = Book
  { title :: String,
    author :: String,
    year :: Int,
    copies :: Int
  }
  deriving (Show, Eq)

catalogue :: [Book]
catalogue =
  [ Book {title = "Things Fall Apart", author = "Chinua Achebe", year = 1958, copies = 2},
    Book {title = "Ficciones", author = "Jorge Luis Borges", year = 1944, copies = 0}
  ]

-- Maybe: there may be no such book.
findBook :: String -> [Book] -> Maybe Book
findBook wanted books = case filter (\b -> title b == wanted) books of
  (b : _) -> Just b
  [] -> Nothing

-- Either: borrowing succeeds with the updated book, or fails with a reason.
borrow :: Book -> Either String Book
borrow b
  | copies b <= 0 = Left ("no copies of " ++ title b ++ " are left")
  | otherwise = Right b {copies = copies b - 1}

checkOut :: String -> String
checkOut wanted = case findBook wanted catalogue of
  Nothing -> wanted ++ ": not in the catalogue"
  Just book -> case borrow book of
    Left reason -> wanted ++ ": sorry, " ++ reason
    Right updated -> wanted ++ ": borrowed, " ++ show (copies updated) ++ " left"

main :: IO ()
main = do
  mapM_ (putStrLn . checkOut) ["Things Fall Apart", "Ficciones", "Dune"]
  print (findBook "Ficciones" catalogue)
  print (map year catalogue)
text
Things Fall Apart: borrowed, 1 left
Ficciones: sorry, no copies of Ficciones are left
Dune: not in the catalogue
Just (Book {title = "Ficciones", author = "Jorge Luis Borges", year = 1944, copies = 0})
[1958,1944]

The signature findBook :: String -> [Book] -> Maybe Book tells every caller that the book might not exist, and the caller cannot use the result as a Book without first matching on Just. There is no null to forget to check. Likewise, borrow returns either a reason for failing or the updated book, and checkOut must handle both.

The record update b {copies = copies b - 1} builds a new Book, equal to b except in one field; the catalogue itself is unchanged. The nested case in checkOut is a little clumsy; lesson 7 shows how Maybe and Either can be chained without the staircase.

A recursive type

haskell
-- A recursive, parameterised type: a binary search tree of any ordered type.
data Tree a = Leaf | Node (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x t@(Node left v right)
  | x < v = Node (insert x left) v right
  | x > v = Node left v (insert x right)
  | otherwise = t -- already present

member :: Ord a => a -> Tree a -> Bool
member _ Leaf = False
member x (Node left v right)
  | x < v = member x left
  | x > v = member x right
  | otherwise = True

toList :: Tree a -> [a]
toList Leaf = []
toList (Node left v right) = toList left ++ [v] ++ toList right

depth :: Tree a -> Int
depth Leaf = 0
depth (Node left _ right) = 1 + max (depth left) (depth right)

fromList :: Ord a => [a] -> Tree a
fromList = foldl (flip insert) Leaf

main :: IO ()
main = do
  let t = fromList [50, 30, 70, 20, 40, 60, 80, 30 :: Int]
  print (toList t)
  print (member 40 t, member 45 t, depth t)
  let w = fromList (words "the cat sat on the mat")
  print (toList w, depth w)
  print (depth (fromList [1 .. 100 :: Int]))
text
[20,30,40,50,60,70,80]
(True,False,3)
(["cat","mat","on","sat","the"],5)
100

Tree a is defined in terms of itself, just as a list is. The type parameter a makes it a tree of anything; the functions that need to compare elements say so with Ord a =>. Insertion does not modify the tree: it builds a new path from the root to the new node and shares every untouched subtree with the old tree, so it costs time proportional to the depth, not the size. That sharing is safe precisely because nothing can ever change.

The last line shows the weakness of a plain binary search tree: inserting already-sorted keys produces a tree that is really a list, 100 levels deep. Production code uses balanced trees, such as the size-balanced trees behind Data.Map and Data.Set in the containers package, which stay logarithmic whatever the order of insertion.

newtype and type synonyms

haskell
-- newtype: a new type with the same runtime representation as an old one.
newtype Celsius = Celsius Double deriving (Show, Eq, Ord)

newtype Fahrenheit = Fahrenheit Double deriving (Show)

toFahrenheit :: Celsius -> Fahrenheit
toFahrenheit (Celsius c) = Fahrenheit (c * 9 / 5 + 32)

-- A type synonym is only a second name: no new type, no extra checking.
type Station = String

hottest :: [(Station, Celsius)] -> Maybe (Station, Celsius)
hottest [] = Nothing
hottest readings = Just (foldr1 warmer readings)
  where
    warmer a b = if snd a >= snd b then a else b

main :: IO ()
main = do
  let readings = [("Windhoek", Celsius 31.5), ("Reykjavik", Celsius 4), ("Chennai", Celsius 36)]
  print (hottest readings)
  print (hottest [])
  case hottest readings of
    Just (station, c) -> putStrLn (station ++ " is hottest: " ++ show (toFahrenheit c))
    Nothing -> putStrLn "no readings"
  print (maybe "no data" fst (hottest readings))
text
Just ("Chennai",Celsius 36.0)
Nothing
Chennai is hottest: Fahrenheit 96.8
"Chennai"

Passing a Fahrenheit where a Celsius is expected is now a compile-time error, though both are plain Doubles in memory. Professionals use newtypes constantly for identifiers (newtype UserId = UserId Int), units and validated values. The empty-list equation of hottest comes first, so foldr1, which needs a non-empty list, is only reached safely. The function maybe default f m takes apart a Maybe in one step: default for Nothing, f x for Just x.

IntuitionH

Why algebraic?

Count the values of each type. Bool has 2. A pair (Bool, Bool) has 2 × 2 = 4: a product. Either Bool Bool has 2 + 2 = 4, the Lefts plus the Rights: a sum. Maybe Bool has 1 + 2 = 3. The unit type () has 1 value and plays the role of the number 1; a type with no constructors at all has 0 values. A function type Bool -> Bool has 2² = 4 values; in general, a -> b behaves like an exponent.

This is more than a curiosity. When you design a type, count its values and compare with the situations you need to represent. The status-string-plus-nullable-fields design of the parcel has far more values than there are real parcel states; the data Parcel version has exactly as many as needed. The closer the count, the fewer impossible cases your functions must handle.

History & global context

Where algebraic data types came from

Algebraic data types and pattern matching are older than Haskell. They appeared together in Hope, a small functional language designed by Rod Burstall, David MacQueen and Donald Sannella at the University of Edinburgh around 1980, and in the ML family that grew up alongside it; Haskell's designers took them as a matter of course. For decades they were considered an academic curiosity in industry, where data was modelled with classes, inheritance and null references.

That has changed decisively. Swift (2014) and Rust (2015) put sum types with pattern matching at the centre of their designs; Kotlin added sealed classes, TypeScript discriminated unions, C# switch expressions over records, and Java gained records (Java 16), sealed interfaces (Java 17) and pattern matching for switch (Java 21). When you meet these features in other languages, you are meeting the ideas of this lesson, often with the same vocabulary: sum types, product types, exhaustiveness checking.

ExplanationH

How professionals model data

A few habits you will see in well-kept Haskell code:

  • Newtypes for identifiers and units. UserId, OrderId, Cents, Metres. Mixing them up becomes impossible, at no run-time cost.
  • Smart constructors. Put a newtype in a module that exports the type but not its constructor, plus a function such as mkEmail :: String -> Either String Email that validates. Every Email in the program has then been checked once, at the boundary.
  • Sum types instead of flags. Instead of Bool arguments (render True False), declare data Mode = Draft | Final. Call sites become self-explanatory.
  • Strict fields for data you will keep. Writing data Point = Point !Double !Double makes fields be evaluated when the value is built. Lesson 8 explains why that prevents memory leaks; many teams make record fields strict by default.
  • Modern record syntax. Plain Haskell records have two annoyances: field names are global functions, so two records in one module cannot both have a name field, and access is written name p rather than p.name. Two GHC extensions, both available since GHC 9.2, fix this, and you will see them in most recent codebases:
haskell
{-# LANGUAGE OverloadedRecordDot #-}
{-# LANGUAGE DuplicateRecordFields #-}

data Person = Person {name :: String, age :: Int} deriving (Show)

data Pet = Pet {name :: String, species :: String} deriving (Show)

greeting :: Person -> String
greeting p = "Hello, " ++ p.name ++ " (" ++ show p.age ++ ")"

main :: IO ()
main = do
  let p = Person {name = "Aiyana", age = 29}
      q = Pet {name = "Biscuit", species = "dog"}
  putStrLn (greeting p)
  putStrLn q.name
text
Hello, Aiyana (29)
Biscuit

The {-# LANGUAGE ... #-} lines at the top of a file are pragmas that switch on language extensions for that file. Projects often enable their favourite extensions for every file at once in the .cabal file instead.

Common misconceptionsH

Common misconceptions

Misconception

"Nothing is just Haskell's null." Null in Java or C# can hide inside any reference, and the type system does not tell you where. Nothing can only appear where the type says Maybe, and you cannot use a Maybe Book as a Book without handling the Nothing case. That difference eliminates a whole class of crashes.

Misconception

"A record is like an object." A record holds data and nothing else: no methods, no hidden state, no inheritance. Behaviour lives in ordinary functions, and sharing behaviour across types is the job of type classes (next lesson). The separation feels odd for a week and then feels natural.

Misconception

"Field accessors are always safe." In a type with several constructors, a field that exists only in some of them gives you a partial function. With data Item = Book { pages :: Int } | Song { seconds :: Int }, calling pages on a Song crashes. Prefer pattern matching for multi-constructor types, or give every constructor the same fields. Recent GHCs can warn about such partial fields (-Wpartial-fields).

Misconception

"deriving Show is how you display values to users." show produces Haskell source code for debugging, with quotes, escapes and constructor names. For messages a person reads, write a function such as describe :: Shape -> String.

Exercises

Exercises

1. Algebraic data types and records

Warm-upComputational

What does this program print?

main :: IO ()
main = do
  let codes = [(254, "Kenya"), (55, "Brazil"), (82, "South Korea")]
  print (lookup 55 codes, lookup 44 codes)

2. Algebraic data types and records

CoreHuman

How many different values does the type Either Bool (Maybe Bool) have (ignoring non-terminating computations)?

3. Algebraic data types and records

CoreHuman

A payment is made either in cash, by card (with the card's last four digits), or by mobile money (with a phone number). Which declaration models this best?

Choose one

4. Algebraic data types and records

CoreComputational

What does this program print?

data Point = Point {x :: Int, y :: Int} deriving (Show)

main :: IO ()
main = do
  let p = Point {x = 1, y = 2}
      q = p {y = 5}
  print (x q + y p, y q)

5. Algebraic data types and records

CoreComputational

What does this program print?

data Priority = Low | Medium | High deriving (Show, Eq, Ord)

main :: IO ()
main = print (maximum [Medium, Low, High, Low], Medium < Low)

6. Algebraic data types and records

StretchComputational

What does this program print?

data Tree = Leaf | Node Tree Int Tree

insert :: Int -> Tree -> Tree
insert x Leaf = Node Leaf x Leaf
insert x t@(Node l v r)
  | x < v = Node (insert x l) v r
  | x > v = Node l v (insert x r)
  | otherwise = t

depth :: Tree -> Int
depth Leaf = 0
depth (Node l _ r) = 1 + max (depth l) (depth r)

main :: IO ()
main = print (depth (foldl (flip insert) Leaf [3, 1, 2, 5, 4]))

7. Algebraic data types and records

CoreHuman

A function charge :: AccountId -> Amount -> IO () is accidentally called as charge amount accountId. Both are Ints underneath. Which declarations make GHC reject the mistaken call?

Choose one

Further reading and resources