Haskell 5: Algebraic Data Types: Defining Your Own Types

Part 5 of Haskell from First Principles.

The snippets are independent examples. Later declarations of Point, Shape, or Student replace the earlier presentation. Maybe and Either are already in the Prelude; their declarations here explain their structure and should not be redefined alongside the Prelude versions.

Parts 1–4 established functions, types, pattern matching, and list recursion.

So far, however, the examples have mostly used built-in types such as Int, Bool, and [a].

Custom algebraic data types let us represent a problem directly in the type system.

This is one of the most important parts of Haskell. Once you understand algebraic data types (ADTs), you can represent trees, mathematical expressions, syntax trees, optional values, errors, and many other structures.

This article develops:

1. The grammar of data declarations.
2. The distinction between type constructors and data constructors.
3. Sum types and product types.
4. Parameterized types such as Maybe a.
5. Pattern matching on custom types.
6. Recursive data types, including binary trees.
7. Record syntax.
8. The distinction between data, type, and newtype.

A small arithmetic-expression interpreter brings these ideas together.

---

5.1 Why do we need to define our own types?

Suppose we want to represent three colors: red, green, and blue.

One possibility is to use integers:

red = 0
green = 1
blue = 2

But this representation has a problem: what does 17 mean? Is it a valid color?

The type system does not enforce our intended restriction.

Instead, Haskell allows us to introduce a new type:

data Color = Red | Green | Blue
  deriving (Eq, Show)

Let us examine the syntax.

Part	Role
data	Introduces the declaration
Color	Names the type constructor
Red | Green | Blue	Lists the alternative data constructors

The declaration says:

A value of type Color can be constructed using exactly one of the three constructors: Red, Green, or Blue.

Now we can write:

favoriteColor :: Color
favoriteColor = Blue

And functions can operate on the new type:

colorCode :: Color -> Int
colorCode Red   = 1
colorCode Green = 2
colorCode Blue  = 3

For example:

colorCode Red     -- 1
colorCode Blue    -- 3

Notice how pattern matching from Block 4 works naturally with this new type.

The final line of our type declaration,

deriving (Eq, Show)

asks the compiler to automatically generate equality and string-representation functionality. Section 5.9 explains these derived instances.

5.2 Type constructors versus data constructors

This is the first important conceptual distinction.

Consider again:

data Color = Red | Green | Blue

Here:

• Color is a type constructor.
• Red, Green, and Blue are data constructors.

They operate at different levels.

A type constructor forms a type. A data constructor produces a value belonging to a type.

For our example:

Red :: Color
Green :: Color
Blue :: Color

But Color itself is not a value.

For example, this is invalid:

x = Color

because Color names a type rather than a data constructor.

Constructors can be functions

Consider a new declaration:

data Point = Point Double Double
  deriving (Show, Eq)

This introduces a type named Point and a data constructor also named Point.

The constructor has type:

Point :: Double -> Double -> Point

This looks exactly like a function type!

We can use it to create values:

p1 :: Point
p1 = Point 1.0 2.0
 
p2 :: Point
p2 = Point 3.0 4.0

Notice that the same spelling Point appears in both roles, but Haskell distinguishes them by syntactic context and namespace.

The constructor Point takes two Double arguments and returns a value of type Point.

In fact, data constructors behave like functions when constructing values.

For example:

makePoint :: Double -> Double -> Point
makePoint = Point

This is valid because Point is already a constructor function of the required type.

A constructor can also be partially applied:

pointOnX1 :: Double -> Point
pointOnX1 = Point 1.0

Then:

pointOnX1 5.0

constructs:

Point 1.0 5.0

Naming conventions

Haskell follows a naming convention that is also important to its grammar.

Category	Examples	Naming rule
Type constructors	Int, Bool, Color, Maybe	Start uppercase
Data constructors	Red, Blue, Just, Nothing	Start uppercase
Variables/functions	x, square, colorCode	Start lowercase
Type variables	a, b, result	Start lowercase

Symbolic constructors such as : are a special syntactic form.

---

5.3 Sum types: choosing between alternatives

The declaration:

data Color = Red | Green | Blue

defines a sum type.

Why is it called a sum?

Because a value of the type is selected from a collection of alternatives.

Suppose we define:

data Answer = Yes | No | Unknown
  deriving (Eq, Show)

Counting fully defined constructor values, there are three possibilities:

$$|\mathrm{Answer}|=3.$$

Now consider:

data Coin = Heads | Tails
  deriving (Eq, Show)

There are two possible values:

$$|\mathrm{Coin}|=2.$$

More generally, if types $A$ and $B$ are disjoint alternatives in a tagged union, then:

$$|A+B|=|A|+|B|.$$

The $+$ symbol represents a choice between alternatives.

This is why these constructions are called sum types.

A more useful example: geometric shapes

Consider:

data Shape
  = Circle Double
  | Rectangle Double Double
  deriving (Show)

A value of type Shape is either:

• A circle, represented by its radius.
• A rectangle, represented by its width and height.

For example:

s1 = Circle 3.0
 
s2 = Rectangle 4.0 5.0

Both values have type Shape.

Notice that constructors can carry additional data.

We can define:

area :: Shape -> Double
 
area (Circle r) = pi * r * r
 
area (Rectangle w h) = w * h

For example:

area (Circle 2.0)        -- approximately 12.566
area (Rectangle 3.0 4.0) -- 12.0

Here, the pattern:

Circle r

matches a Circle value and extracts its radius.

Similarly:

Rectangle w h

matches a Rectangle value and extracts its width and height.

The constructors are doing two related but opposite jobs:

Position	Example	Meaning
Expression	Circle 3.0	Construct a value
Pattern	Circle r	Decompose a value

This is the same construction/decomposition duality we saw with lists in Block 4.

---

5.4 Product types: combining multiple values

Now consider:

data Point = Point Double Double
  deriving (Show)

A point consists of two coordinates.

The geometric model is a Cartesian product:

$$\mathbb{R}\times \mathbb{R}.$$

The symbol $\times$ represents a Cartesian product.

This is the idea behind a product type. Double represents coordinates with finite-precision floating-point values rather than exact mathematical real numbers.

For example:

data Student = Student String Int
  deriving (Show)

A Student value contains both a name and an age.

alice = Student "Alice" 20

We can extract the fields by pattern matching:

studentName :: Student -> String
studentName (Student name age) = name
 
studentAge :: Student -> Int
studentAge (Student name age) = age

Or, more concisely:

studentName (Student name _) = name
 
studentAge (Student _ age) = age

Recall that _ is the wildcard pattern introduced in Block 4.

Why is it called a product?

Suppose a type $A$ has $m$ possible values and type $B$ has $n$ possible values.

Then a pair $(a,b)$, where $a\in A$ and $b\in B$, has:

$$m\times n$$

possible values.

For example:

data BoolPair = BoolPair Bool Bool
  deriving (Show)

There are four possible values:

BoolPair False False
BoolPair False True
BoolPair True False
BoolPair True True

Because:

$$2\times 2=4.$$

This explains the terminology. These cardinality equations count total values. Lazy Haskell also admits undefined computations and partially defined structures, which the simple arithmetic does not count.

Sum types versus product types

Sum type	Product type
A or B	A and B
Choose one tagged alternative	Combine components in one constructor
Cardinalities add	Cardinalities multiply

The mathematical correspondence is:

$$\boxed{\text{Sum type}⟷+}$$ $$\boxed{\text{Product type}⟷\times }$$

These are called algebraic data types because more complicated data types can be built by combining sums and products.

5.5 Combining sums and products

Let us revisit the earlier example:

data Shape
  = Circle Double
  | Rectangle Double Double

This is simultaneously a sum and a product construction.

A Shape is either a Circle containing one number, or a Rectangle containing two numbers.

Mathematically, its structure resembles:

$$\mathrm{Shape}=\mathrm{Double}+(\mathrm{Double}\times \mathrm{Double}).$$

The Circle and Rectangle constructor tags distinguish the two alternatives.

An important observation is that most interesting data types are combinations of sums and products.

For example, consider:

data Message
  = TextMessage String
  | NumberMessage Int
  | PairMessage String Int

The mathematical structure is:

$$\mathrm{Message}=\mathrm{String}+\mathrm{Int}+(\mathrm{String}\times \mathrm{Int}).$$

This algebraic viewpoint is helpful for both type design and program correctness.

---

5.6 Parameterized types: Maybe a

So far, our custom types have been concrete types.

But Haskell also supports type definitions with type parameters.

One particularly useful example is Maybe.

Its definition, in simplified form, is:

data Maybe a
  = Nothing
  | Just a

Maybe is already provided by Haskell, so you don’t need to redefine it.

Let us analyze the syntax.

The type constructor Maybe takes a type parameter a.

For example:

Maybe Int
Maybe Bool
Maybe String

are all types.

The constructors are:

Nothing :: Maybe a
 
Just :: a -> Maybe a

The Nothing constructor represents the absence of a value.

The Just constructor wraps an existing value.

Examples:

Just 3        :: Maybe Int
 
Just True     :: Maybe Bool
 
Just "hello"  :: Maybe String
 
Nothing       :: Maybe a

Why is Maybe useful?

Recall our first function from Block 4:

first (x:xs) = x

It fails on the empty list.

Instead, we can define a function that explicitly represents the possibility of failure:

safeHead :: [a] -> Maybe a
 
safeHead [] = Nothing
 
safeHead (x:xs) = Just x

Now:

safeHead [1,2,3]   -- Just 1
 
safeHead []        -- Nothing

No runtime pattern-match failure is necessary.

Furthermore, the type itself communicates that the result might be absent:

safeHead :: [a] -> Maybe a

This is a very important feature of Haskell: the type system can explicitly represent different possible outcomes of a computation.

Pattern matching on Maybe

Suppose we want to use the result.

valueOrZero :: Maybe Int -> Int
 
valueOrZero Nothing = 0
 
valueOrZero (Just x) = x

For example:

valueOrZero Nothing    -- 0
 
valueOrZero (Just 5)   -- 5

The function has to account for both constructors.

This is preferable to assuming that a value always exists.

A more general function

We can make the fallback value an argument:

valueOr :: a -> Maybe a -> a
 
valueOr fallback Nothing = fallback
 
valueOr fallback (Just x) = x

For example:

valueOr 0 Nothing        -- 0
 
valueOr 0 (Just 5)       -- 5
 
valueOr "unknown" Nothing -- "unknown"

Notice the polymorphic type:

a -> Maybe a -> a

We can understand it using the rules from Block 2: the fallback value, the value wrapped by Just, and the result all have the same type a.

A mathematical interpretation

If a type $A$ has $n$ possible values, then Maybe A has $n+1$ possible values.

There is one additional possibility, Nothing.

Thus:

$$|\mathrm{Maybe}(A)|=1+|A|.$$

This is another example of a sum type.

---

5.7 Type constructors can take multiple type parameters

Consider a computation that may fail with an error message.

Maybe a can indicate failure:

Nothing

but it cannot explain the reason for failure.

The Prelude also provides Either; its simplified declaration is:

data Either a b
  = Left a
  | Right b

This type has two type parameters.

Its constructors are:

Left  :: a -> Either a b
 
Right :: b -> Either a b

The type Either String Int, for example, can represent either a string error message or an integer result.

Right 42 :: Either String Int
 
Left "Invalid input" :: Either String Int

A function can make this distinction explicit:

safeDivide :: Integer -> Integer -> Either String Integer
 
safeDivide x 0 = Left "Division by zero"
 
safeDivide x y = Right (x `div` y)

Examples:

safeDivide 10 2
-- Right 5
 
safeDivide 10 0
-- Left "Division by zero"

Notice that the return type is:

Either String Integer

rather than simply:

Integer

The function may produce either an error or a successful integer result.

This is a common way to represent errors. The example uses arbitrary-precision Integer, so the demonstration is about division by zero without adding bounded-Int overflow behavior.

Both types make the alternatives visible to callers; a caller can inspect them with pattern matching.

---

5.8 Recursive data types: binary trees

Now we arrive at one of the most important ideas in this block.

Recall from Block 4 that lists have a recursive structure:

$$\mathrm{List}(a)=1+a\times \mathrm{List}(a).$$

Here, $1$ represents the single possibility of an empty list.

We can define other recursive structures in Haskell.

For example, consider a binary tree:

data Tree a
  = Empty
  | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

Let us carefully analyze this declaration.

A tree is either:

1. Empty, an empty tree.
2. Node x left right, containing a value x and two subtrees.

The constructors have types:

Empty :: Tree a
 
Node :: a -> Tree a -> Tree a -> Tree a

The interesting part is that the type being defined, Tree a, appears inside its own definition.

This is a recursive data type.

Constructing a tree

For example:

tree :: Tree Int
tree =
  Node 5
    (Node 2 Empty Empty)
    (Node 8 Empty Empty)

This represents:

          Node 5
         /      \
     Node 2    Node 8
     /   \     /   \
 Empty Empty Empty Empty

Three Node constructors and four Empty constructors make this Tree Int.

Pattern matching on trees

We can define the number of nodes in a tree:

size :: Tree a -> Int
 
size Empty = 0
 
size (Node x left right) =
  1 + size left + size right

For our example:

size tree    -- 3

This definition is directly analogous to the recursive list-length function from Block 4.

The structure of the data determines the structure of the recursion.

For an empty tree:

$$S(\mathrm{Empty})=0.$$

For a node:

$$S(\mathrm{Node}(x,l,r))=1+S(l)+S(r).$$

Summing the values in a tree

We can similarly write:

sumTree :: Num a => Tree a -> a
 
sumTree Empty = 0
 
sumTree (Node x left right) =
  x + sumTree left + sumTree right

For our tree:

sumTree tree    -- 15

because:

$$5+2+8=15.$$

Mapping a function over a tree

Now consider a more general operation:

mapTree :: (a -> b) -> Tree a -> Tree b
 
mapTree f Empty = Empty
 
mapTree f (Node x left right) =
  Node (f x) (mapTree f left) (mapTree f right)

This function applies f to every value in the tree while preserving the tree’s structure.

For example:

mapTree (+1) tree

produces:

Node 6
  (Node 3 Empty Empty)
  (Node 9 Empty Empty)

The type:

(a -> b) -> Tree a -> Tree b

shows that mapTree can transform the element type.

For example, it could map integers to strings:

mapTree show tree

This transforms a Tree Int into a Tree String.

Part 8 connects this pattern to Functor.

Recursive types and mathematical induction

The recursive definition of Tree suggests a natural proof principle.

To prove a property $P(t)$ for every finite tree $t$, we can:

1. Prove $P(\mathrm{Empty})$.
2. Assume $P(l)$ and $P(r)$, then prove $P(\mathrm{Node}(x,l,r))$.

This is called structural induction.

It is closely related to the structure of recursive functions over trees.

---

5.9 Automatically deriving type-class instances

You may have noticed that our examples often contain:

deriving (Show, Eq)

What does this mean?

Recall from Block 2 that type classes describe available operations.

For example:

(==) :: Eq a => a -> a -> Bool

Equality comparison is available for types with an Eq instance.

Similarly:

show :: Show a => a -> String

converts a value into a string representation, provided its type has a Show instance.

By default, declaring a new data type does not automatically provide all possible operations.

But Haskell can derive certain instances.

Consider:

data Color = Red | Green | Blue
  deriving (Eq, Show)

Now these expressions work:

Red == Blue     -- False
 
Red == Red      -- True
 
show Green      -- "Green"

The compiler generates implementations based on the constructors.

For equality, different constructors compare unequal. Values built with the same constructor compare their corresponding fields, provided those field types also support equality.

For Show, the compiler generates a textual representation reflecting the constructor structure.

This is convenient, but only certain type classes support automatic deriving in ordinary Haskell. Part 7 studies type classes and instances.

---

5.10 Record syntax: naming constructor fields

Consider:

data Student = Student String Int
  deriving (Show)

This works, but it isn’t always easy to remember which argument means what.

Is the first argument the name or the age?

Haskell provides record syntax:

data Student = Student
  { studentName :: String
  , studentAge  :: Int
  }
  deriving (Show)

Now we can construct a student using named fields:

alice :: Student
alice = Student
  { studentName = "Alice"
  , studentAge = 20
  }

The compiler automatically creates field accessor functions:

studentName :: Student -> String
 
studentAge :: Student -> Int

For example:

studentName alice    -- "Alice"
 
studentAge alice     -- 20

We can also construct the same value positionally:

bob = Student "Bob" 22

Record syntax names fields of an ordinary algebraic data type. For this single-constructor Student, both selectors cover every fully constructed value. If a field appears on only some constructors of a sum type, its selector is partial: applying it to another constructor raises an error. Pattern matching can make that missing-field case explicit.

Record updates

Suppose Alice becomes 21 years old.

We can write:

olderAlice = alice { studentAge = 21 }

The result is a new Student value with the updated age.

It does not mutate the original alice.

For example:

studentAge alice       -- 20
 
studentAge olderAlice  -- 21

This is important: record update syntax creates a new value rather than modifying an existing one.

---

5.11 data versus type versus newtype

Haskell provides three closely related constructs:

data
 
type
 
newtype

They have different meanings.

data: introduce a new algebraic data type

We already know this one:

data Point = Point Double Double
  deriving (Show)

This introduces a new type called Point, with a constructor that holds two Double values.

A value of type Point is distinct from an ordinary pair of Double values.

type: create a type synonym

Consider:

type Name = String

This introduces a new name for an existing type.

For example:

greet :: Name -> String
greet name = "Hello, " ++ name

But Name is not a genuinely new type.

It is simply another name for String.

Therefore:

greet "Alice"

works directly.

We can also define:

type Coordinate = (Double, Double)

Here, the type (Double, Double) is a tuple type.

The declaration gives it a more descriptive name.

newtype: introduce a distinct wrapper type

Now suppose we want to represent a user ID.

We could write:

type UserId = Int

But this would make UserId interchangeable with Int, which may be undesirable.

Instead, we can write:

newtype UserId = UserId Int
  deriving (Eq, Show)

Now:

user1 :: UserId
user1 = UserId 123

The type UserId is distinct from Int.

For example:

getUserId :: UserId -> Int
getUserId (UserId n) = n

You cannot generally pass an Int where a UserId is expected without explicitly constructing a UserId.

Unlike an ordinary data declaration, newtype has exactly one constructor and one field, with the same runtime representation as its underlying type. This also changes behavior around undefined values: UserId undefined is itself undefined, while a lazy data wrapper can expose its constructor around an undefined field. Thus newtype is not semantically interchangeable with data in every lazy program. See the Haskell Report on datatype renamings.

Comparison

Construct	Creates a distinct type?	Main purpose
type	No	Give an existing type another name
newtype	Yes	Wrap one value in a distinct type
data	Yes	Define a general algebraic data type

Use data for general alternatives and multiple fields; use newtype when a distinct single-field wrapper expresses the intended model.

---

5.12 Application: representing mathematical expressions

Let us now apply what we have learned to a concrete example.

Suppose we want to represent arithmetic expressions such as:

$$(2+3)\times 4.$$

Rather than directly calculating the result, we first want to represent the expression as a data structure.

We can define:

data Expr
  = Const Int
  | Add Expr Expr
  | Multiply Expr Expr
  deriving (Show, Eq)

This says that an expression is one of three possibilities:

1. A constant integer.
2. An addition of two expressions.
3. A multiplication of two expressions.

Notice the recursive structure.

Constructing an expression

The mathematical expression:

$$(2+3)\times 4$$

can be represented as:

expr :: Expr
expr =
  Multiply
    (Add (Const 2) (Const 3))
    (Const 4)

Visually:

         Multiply
         /      \
       Add     Const 4
      /   \
 Const 2  Const 3

This structure is called an abstract syntax tree (AST).

Compilers and interpreters frequently use such structures.

Writing an evaluator

Now let’s define an evaluator:

eval :: Expr -> Int
 
eval (Const n) = n
 
eval (Add x y) =
  eval x + eval y
 
eval (Multiply x y) =
  eval x * eval y

For example:

eval expr

returns:

20

Let us derive this.

$$\begin{array}{rl}& \mathrm{eval}(\mathrm{Multiply}(\mathrm{Add}(\mathrm{Const}(2),\mathrm{Const}(3)),\mathrm{Const}(4)))\\ & =\mathrm{eval}(\mathrm{Add}(\mathrm{Const}(2),\mathrm{Const}(3)))\times \mathrm{eval}(\mathrm{Const}(4))\\ & =(2+3)\times 4\\ & =20.\end{array}$$

Notice that the evaluator follows the recursive structure of the expression type exactly.

Each constructor has a corresponding equation.

Why is this example important?

It demonstrates a powerful pattern:

1. Define a recursive algebraic data type to represent a language.
2. Construct values representing expressions in that language.
3. Write recursive functions that interpret or transform those expressions.

For example, we could extend Expr with subtraction, division, variables, or function applications.

This is the foundation of interpreters, compilers, symbolic mathematics, and domain-specific languages.

It also illustrates an important philosophical point about Haskell: a program can itself be represented as a value, and another program can manipulate that value through ordinary functions.

---

5.13 The grammar of algebraic data types

Let us now summarize the new syntax formally.

A simplified Haskell data declaration has the structure:

DataDeclaration :=
    data TypeConstructor TypeVariable*
      = Constructor FieldType*
      | Constructor FieldType*
      | ...

For example:

data Color = Red | Green | Blue

or:

data Maybe a = Nothing | Just a

or:

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

In a prefix constructor declaration, parentheses group the applied type Tree a as one field. Without them, the constructor-field grammar would treat the tokens as separate field types. This is a grouping rule for declarations; in a signature such as Tree a -> Int, type application already binds more tightly than the arrow.

Type constructor application

In:

Maybe Int

Maybe is a type constructor applied to the type Int.

Similarly:

Tree Bool

is a type obtained by applying Tree to Bool.

This looks similar to ordinary function application:

f x

But type constructors operate at the type level, while ordinary functions operate at the value level.

A kind classifies a type constructor: for example, Maybe needs one type argument to form a concrete element type.

Data constructors and their signatures

Given:

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

the constructors have types:

Empty :: Tree a
 
Node :: a -> Tree a -> Tree a -> Tree a

Notice that a constructor can have zero or more arguments.

Every constructor produces a value of the declared type.

This also explains why the following would not be a valid constructor definition:

-- Invalid
data Strange = MakeStrange Int -> Bool

After a constructor name, ordinary field types are listed; we cannot write a function arrow there to describe the constructor’s result. The result is determined by the data declaration itself.

If we wanted a constructor holding a function, we would write:

data Strange = MakeStrange (Int -> Bool)

Then:

MakeStrange :: (Int -> Bool) -> Strange

This distinction between a field that is a function and the function type of a constructor is worth understanding.

---

5.14 Exercises

These exercises are designed to test your understanding of constructors, pattern matching, and recursive types.

Try each exercise before opening its solution. The undefined expressions in skeletons mark code to replace; evaluating an unfinished skeleton raises an error.

Exercise 5.1

Give the types of both constructors.

data Result a
  = Failure String
  | Success a

Solution

Failure :: String -> Result a
Success :: a -> Result a

Every constructor returns Result a; its fields determine its argument types.

Exercise 5.2

Convert Maybe Int to Int, returning -1 for Nothing.

getValue :: Maybe Int -> Int

Solution

getValue Nothing = -1
getValue (Just x) = x

Match both constructors, extracting the value stored in Just.

Exercise 5.3

Count the leaves in this alternative tree type.

data LeafTree a
  = Leaf a
  | Branch (LeafTree a) (LeafTree a)
 
countLeaves :: LeafTree a -> Int

Solution

countLeaves (Leaf _) = 1
countLeaves (Branch l r) =
  countLeaves l + countLeaves r

A Leaf contributes one. A Branch contributes the sum for its two subtrees. The different name LeafTree keeps this exercise distinct from the earlier Tree declaration.

Exercise 5.4

Predict the value and infer the type of swap.

data Pair a b = Pair a b
  deriving (Show)
 
swap (Pair x y) = Pair y x

After loading those definitions, evaluate:

ghci> swap (Pair 3 True)

Solution

swap :: Pair a b -> Pair b a

ghci> swap (Pair 3 True)
Pair True 3

Pattern matching extracts x = 3 and y = True; construction places them in the opposite order.

Exercise 5.5

Compute the height of the binary tree from Section 5.8. Count an empty tree as height 0.

height :: Tree a -> Int

Solution

height Empty = 0
height (Node _ l r) =
  1 + max (height l) (height r)

A nonempty tree has height one plus the larger subtree height. Thus a singleton node has height 1.

---

5.15 Summary

The main constructs have distinct roles:

Concept	Haskell syntax	Meaning
Define a type	data Color = Red | Blue	Introduce a new algebraic data type
Sum type	A | B	Choose one constructor
Product type	Point Double Double	Combine multiple fields
Parameterized type	Maybe a	Type constructor accepting a type parameter
Data constructor	Just 3	Construct a value
Pattern matching	Just x	Decompose a value
Recursive type	Tree a	A data type defined in terms of itself
Record	{ name :: String }	Give names to fields
Type alias	type Name = String	Give an existing type another name
Newtype	newtype Id = Id Int	Introduce a distinct single-field wrapper type

Data types determine computation structure

Consider the definition:

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

Its mathematical structure is:

$$T(A)=1+A\times T(A)\times T(A).$$

This single equation already tells us how to write many recursive algorithms.

For example, if we want to reduce a tree to a value of type $B$, we can specify:

• A value $z\in B$ for the empty tree.
• A combining function $g:A\times B\times B\to B$ for each nonempty node.

Then define:

$$\begin{array}{rl}F(\mathrm{Empty})& =z,\\ F(\mathrm{Node}(x,l,r))& =g(x,F(l),F(r)).\end{array}$$

This pattern describes size, sumTree, and many other tree algorithms.

We could even implement a general tree fold:

foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b
 
foldTree z g Empty = z
 
foldTree z g (Node x left right) =
  g x (foldTree z g left) (foldTree z g right)

Then:

size = foldTree 0 (\_ l r -> 1 + l + r)

and:

sumTree = foldTree 0 (\x l r -> x + l + r)

Here \ introduces an anonymous function. Part 6 develops lambdas and higher-order functions; the important point here is the recursion pattern shared by these definitions.

The important observation is that a recursive data type determines a general pattern of recursion over values of that type.

This is a deep connection between algebraic data types, recursion, and mathematical induction. It also motivates the structure-preserving transformations in Part 8.

---

← Part 4 · Series index · Part 6 →

Adapted from Block 5 of the GPT-produced Haskell tutorial, with editorial and technical corrections.