Algebraic data types

Algebraic data types (ADTs) are Haskell’s principal mechanism for declaring user-defined types. The mechanism — sum types, product types, recursive types, and the data/newtype/type declaration forms — is the foundation on which the type system rests. Combined with pattern matching (the conventional way to consume ADTs), the mechanism admits direct expression of data shapes that more traditional languages model with classes, inheritance, and visitor patterns. ADTs are pervasive in Haskell code; nearly every non-trivial program defines several.

This page covers the data declaration forms, the relationship between sums and products, records and field selectors, newtypes, type aliases, and the conventions for using each.

The data declaration

A data declaration introduces a new type and its constructors:

data Bool = True | False
data Direction = North | East | South | West
data Color = Red | Green | Blue

The form: data <TypeName> = <Constructor1> | <Constructor2> | .... Each constructor is a separate value of the type; constructors with the same arguments are different values:

let d :: Direction
    d = North

case d of
    North -> "n"
    East  -> "e"
    South -> "s"
    West  -> "w"

The above types are enumerations — finitely many constants, no associated data. The data declaration is more general:

Sum types and product types

A sum type (also called a tagged union or a discriminated union) has multiple constructors, each tagging a different alternative:

data Shape
    = Circle Double            -- radius
    | Square Double            -- side
    | Rectangle Double Double  -- width, height
    | Triangle Double Double Double  -- three sides

A product type combines several values into one. The syntax is the same as a sum type with one constructor:

data Point = Point Double Double
data Pair a b = Pair a b
data RGB = RGB Int Int Int

The terminology algebraic data type comes from the algebraic interpretation:

• A sum type A | B | C represents the disjoint union of A, B, and C. Cardinality: |A| + |B| + |C|.
• A product type A B represents the cartesian product. Cardinality: |A| × |B|.

Combinations admit complex shapes:

data Shape
    = Circle Double                    -- one Double
    | Rectangle Double Double          -- two Doubles
    | Polygon [Point]                  -- a list of points
    | Composite Shape Shape            -- recursive

Constructor application

Constructors are functions:

data Point = Point Double Double

origin :: Point
origin = Point 0 0

scale :: Double -> Point -> Point
scale s (Point x y) = Point (s * x) (s * y)

The constructor Point has type Double -> Double -> Point; it takes two Doubles and produces a Point. The application Point 3 4 constructs a value; the pattern (Point x y) destructs one.

For nullary constructors (no arguments), the constructor is a value:

data Direction = North | East | South | West

n :: Direction
n = North           -- North is a value of type Direction

Recursive types

A type may refer to itself in its constructors:

data List a = Nil | Cons a (List a)

example :: List Int
example = Cons 1 (Cons 2 (Cons 3 Nil))

The Cons constructor takes an a and a List a; the type is recursive. The standard library’s [] type is essentially this construction:

data [a] = [] | a : [a]    -- conceptual; the actual syntax is special

Recursive types admit the conventional data structures:

data Tree a = Leaf | Node (Tree a) a (Tree a)

singleton :: a -> Tree a
singleton x = Node Leaf x Leaf

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = singleton x
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

Trees, graphs (with care; graphs require references), and higher-arity recursive structures are all expressed through data declarations.

Type parameters

A data declaration may have type parameters:

data Maybe a = Nothing | Just a
data Either a b = Left a | Right b
data Pair a b = Pair a b
data List a = Nil | Cons a (List a)
data Tree a = Leaf | Node (Tree a) a (Tree a)

The type parameters appear in the constructors’ arguments. The resulting type is parametric; Maybe Int, Maybe String, Maybe (Maybe a) are all valid types.

Records

A record syntax admits named fields:

data Person = Person
    { name  :: String
    , age   :: Int
    , email :: Maybe String
    }

The record syntax produces:

• The constructor Person (with the same name as the type, by convention).
• Field selectors — functions name, age, email that extract the corresponding field.

Construction admits two forms:

-- Positional:
alice :: Person
alice = Person "Alice" 30 (Just "alice@example.com")

-- With field names:
bob :: Person
bob = Person { name = "Bob", age = 28, email = Nothing }

Field access:

n :: String
n = name alice            -- field selector as a function

Record update produces a new record with selected fields modified:

older :: Person
older = alice { age = 31 }       -- copy alice, change age

The record-update syntax is compact for changing one field; for changing many, the positional form is often clearer.

Record-syntax pitfalls

The original record syntax has several historical issues:

• Field-name collisions: two records cannot have fields with the same name in the same module without elaborate workarounds.
• No automatic update for nested records: changing person.address.city requires explicit reconstruction.
• The field selector is a partial function: if a sum type has constructors with different fields, the selector is undefined for the wrong constructor.

Several modern extensions address these:

• DuplicateRecordFields (Java’s RecordType.field syntax) — admits same-named fields across types.
• OverloadedRecordDot (Java 9+ syntax) — admits person.name syntactic sugar.
• RecordWildCards — admits Person {..} to bring all fields into scope:

{-# LANGUAGE RecordWildCards #-}

greet :: Person -> String
greet Person {..} = "Hello, " ++ name ++ ", age " ++ show age

For nested-record updates, libraries (microlens, lens) provide lenses — composable getters and setters that admit person & address . city .~ "Berlin".

Type parameters in records

data Container a = Container
    { contents :: [a]
    , label    :: String
    }

c :: Container Int
c = Container { contents = [1, 2, 3], label = "numbers" }

The type parameter is part of the type’s name; field selectors carry it through:

contents :: Container a -> [a]
label    :: Container a -> String

newtype

A newtype declaration introduces a single-constructor wrapper around a single type:

newtype Age = Age Int
newtype Name = Name String
newtype Wrapped a = Wrapped { unwrap :: a }

The runtime representation is identical to the wrapped type — there is no overhead — but the type system treats them as distinct:

n :: Int
n = 42

a :: Age
a = Age 42         -- ok

a' :: Age
a' = 42            -- ERROR: 42 is not an Age

The principal uses:

• Type-level distinctions: distinguish a UserId from an OrderId even though both are Ints underneath.
• Multiple type-class instances: a single underlying type can have several different Semigroup instances by wrapping in different newtypes (Sum Int, Product Int, Min Int, Max Int).
• Adding a documentation layer: the Age Int reads more clearly than the bare Int.

newtype is restricted to one constructor with one argument. For multi-constructor or multi-argument cases, use data.

The principal advantage over data is zero cost: the compiler erases the wrapper at runtime. A function that takes an Age is generated to take an Int; the only difference is the type-level distinction.

Type aliases (type)

A type declaration introduces an alias — a synonym for an existing type:

type Name = String
type Age = Int
type Point = (Double, Double)
type Predicate a = a -> Bool

A type alias is interchangeable with the underlying type — the compiler treats them as the same. Aliases are documentation; they do not introduce new types:

n :: Name
n = "Alice"     -- ok

s :: String
s = n           -- ok; Name is just String

The conventional choice between type and newtype:

• type for documentation: rename a type for clarity but admit free interchange.
• newtype for type safety: distinguish two types that are structurally identical.

Smart constructors

A smart constructor is a function that constructs a value with validation:

module Data.Email (Email, mkEmail, getEmail) where

newtype Email = Email String

mkEmail :: String -> Maybe Email
mkEmail s
    | '@' `elem` s = Just (Email s)
    | otherwise    = Nothing

getEmail :: Email -> String
getEmail (Email s) = s

The constructor Email is not exported; users must go through mkEmail, which validates. The mechanism is the conventional Haskell idiom for invariant-preserving types.

The export list of the module:

module Data.Email
    ( Email          -- export the type but not the constructor
    , mkEmail        -- exported
    , getEmail       -- exported
    ) where

Without the constructor in the export list, users cannot bypass mkEmail. The mechanism is the Haskell equivalent of a private constructor in Java/C#.

Strict fields

By default, ADT fields are lazy — values are stored as thunks until forced. The bang annotation (!) marks a field as strict:

data Counter = Counter !Int    -- the Int is evaluated immediately on construction

The mechanism reduces space leaks for accumulating values; the conventional discipline is to make numeric fields strict unless laziness is genuinely needed.

The StrictData language extension makes all fields strict by default:

{-# LANGUAGE StrictData #-}

data Point = Point Double Double    -- both fields strict

The Strict extension makes everything (including let bindings) strict; it is rarely used and admits substantial behavioural changes.

The full treatment of laziness and strictness is in Laziness.

Existential types

The ExistentialQuantification extension admits hiding a type variable inside a constructor:

{-# LANGUAGE ExistentialQuantification #-}

data Showable = forall a. Show a => Showable a

heterogeneous :: [Showable]
heterogeneous = [Showable 42, Showable "hello", Showable True]

displayAll :: [Showable] -> String
displayAll xs = unwords [show x | Showable x <- xs]

The Showable constructor admits any type with a Show instance; the type variable a is existentially quantified, meaning the consumer cannot recover it specifically (only the constraints declared in the constructor — Show a here).

The mechanism admits heterogeneous collections and certain plugin-style architectures. The conventional alternative is type classes plus dispatch; existential types are appropriate when the constraint is small and the alternatives are awkward.

GADTs

Generalised algebraic data types (GADTs extension) admit constructors that return more specific types than the type’s general signature would allow:

{-# LANGUAGE GADTs #-}

data Expr a where
    IntLit  :: Int -> Expr Int
    BoolLit :: Bool -> Expr Bool
    Add     :: Expr Int -> Expr Int -> Expr Int
    Eq      :: (Eq a) => Expr a -> Expr a -> Expr Bool
    If      :: Expr Bool -> Expr a -> Expr a -> Expr a

eval :: Expr a -> a
eval (IntLit n)   = n
eval (BoolLit b)  = b
eval (Add e1 e2)  = eval e1 + eval e2
eval (Eq e1 e2)   = eval e1 == eval e2
eval (If c t e)   = if eval c then eval t else eval e

The mechanism admits type-safe expression trees — pattern-matching on the constructor refines the type variable, so the compiler knows Add e1 e2 is an Expr Int and that + is admissible.

GADTs are an advanced topic; treated briefly here. The standard library uses them sparingly; library code (parser combinators, type-aware interpreters) uses them more.

Phantom types

A phantom type is a type parameter that does not appear in any constructor:

data Tagged tag a = Tagged a

newtype UserId = UserId Int
newtype OrderId = OrderId Int

userId :: Tagged UserId Int
userId = Tagged 42

orderId :: Tagged OrderId Int
orderId = Tagged 100

-- Compiler enforces:
process :: Tagged UserId Int -> ()
process _ = ()

process userId   -- ok
process orderId  -- ERROR: type mismatch

The phantom type carries no runtime information; the compiler uses it solely to enforce constraints. The mechanism is the conventional Haskell idiom for type-safe identifiers and unit-of-measure types.

Common patterns

Sum types for state

data ConnectionState
    = Disconnected
    | Connecting
    | Connected { since :: UTCTime }
    | Failed String

The pattern admits modeling state machines with the type system; pattern matching on the constructor admits the appropriate handling for each state.

Maybe and Either as control-flow types

findUser :: UserId -> Maybe User
parseInt :: String -> Either String Int

The conventional Haskell idiom for “may not have a value” (Maybe) and “value or error” (Either).

Newtype-based validation

newtype NonEmpty a = NonEmpty (a, [a])

mkNonEmpty :: [a] -> Maybe (NonEmpty a)
mkNonEmpty [] = Nothing
mkNonEmpty (x:xs) = Just (NonEmpty (x, xs))

The pattern guarantees the contained list is non-empty by construction.

Record types for configuration

data Config = Config
    { host    :: String
    , port    :: Int
    , timeout :: Int
    , verbose :: Bool
    }

defaultConfig :: Config
defaultConfig = Config
    { host    = "localhost"
    , port    = 8080
    , timeout = 30
    , verbose = False
    }

custom :: Config
custom = defaultConfig { port = 9090, verbose = True }

The record-update syntax admits “default with overrides” — the conventional Haskell pattern for configuration.

A note on the limits of ADTs

ADTs are extremely flexible but have limits:

• No subtyping: an Animal does not contain a Dog and a Cat in the OOP sense. The pattern is sum type with constructors: data Animal = Dog | Cat.
• No mutability in the type: a data value is immutable; modification produces a new value.
• No reference equality: two Point 3 4 values are equal by Eq but are distinct heap objects.
• Default representation: the JVM-style boxed-and-tagged representation; for unboxed value-like types, use newtype with strict fields or unboxed types (advanced).

The combination of data, newtype, type, records, and the mechanisms above (existential, GADTs, phantom types) covers the substantial majority of Haskell’s data-modelling needs. Most non-trivial Haskell programs define several ADTs; the discipline of choosing the right shape is a substantial part of fluency in the language.