0098: Email Tutorials ‐ FP 12 ‐ Declaring Types and Classes

FP12 Graham Hutton Video

Table of Contents

1. Big Picture: What “declaring types” means in Haskell
2. type Declarations (Type Synonyms) 2.1 Why use them 2.2 Parameterized type synonyms 2.3 Limitations (why they can’t be recursive)
3. data Declarations (Algebraic Data Types) 3.1 Constructors and what they really are 3.2 Pattern matching on constructors 3.3 Constructors with parameters
4. Parameterized Data Types: Maybe for safe failure 4.1 Why “safe” functions matter 4.2 safeDiv and safeHead
5. Recursive Data Types 5.1 Peano naturals (Nat) 5.2 Conversions (natToInt, intToNat) 5.3 Recursive addition and multiplication
6. Tree-like Recursive Types: Expression Trees (Expr) 6.1 Building expressions 6.2 size and eval
7. Folding Over Expressions (foldE) 7.1 Why folds matter 7.2 Defining foldE 7.3 Defining eval and size using foldE
8. Binary Trees with Data in Leaves (Tree a)
9. (Bonus) Intro to Typeclasses and deriving (practical basics)
10. Practice Exercises (with solutions)

1) Big Picture: What “declaring types” means in Haskell

So far, you used built-in types like Int, Bool, and lists. This lecture shows how to create your own types in two ways:

• type: rename an existing type (synonym).
• data: create a brand new type with one or more constructors.

Think of it like this:

• type = “alias” (same underlying type)
• data = “new structure” (new shape of values)

2) type Declarations (Type Synonyms)

2.1 What it does

A type declaration introduces a new name for an existing type:

type String = [Char]

This means String is not a new type at runtime; it’s just a friendlier name for [Char].

2.2 Why use it

To make types more readable and meaningful:

type Pos = (Int, Int)

origin :: Pos
origin = (0,0)

left :: Pos -> Pos
left (x,y) = (x-1, y)

Without Pos, you’d see (Int,Int) -> (Int,Int) everywhere, and it’s less clear that those pairs represent positions.

2.3 Parameterized type synonyms

Type synonyms can take parameters:

type Pair a = (a,a)

copy :: a -> Pair a
copy x = (x,x)

2.4 Important limitation: type can’t be recursive

This is not allowed:

type Tree = (Int, [Tree])   -- ❌ not allowed

Recursive “real structures” must be built with data, not type.

3) data Declarations (Algebraic Data Types)

3.1 What it does

A data declaration creates a new type by listing constructors:

data Bool = False | True

Here:

• Bool is the type name
• False and True are constructors

3.2 Constructors are functions

This is a core mental model: constructors are functions that build data.

For example, with:

data Answer = Yes | No | Unknown

You can pattern match:

flipA :: Answer -> Answer
flipA Yes     = No
flipA No      = Yes
flipA Unknown = Unknown

3.3 Constructors with parameters

Constructors can carry data:

data Shape = Circle Float | Rect Float Float

• Circle takes one Float radius
• Rect takes two Floats (width and height)

Compute area by pattern matching:

area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y

4) Parameterized Data Types: Maybe

4.1 Why use Maybe?

Some standard functions can crash:

• division by zero
• taking the head of an empty list

Maybe represents “this might fail”:

data Maybe a = Nothing | Just a

• Nothing = failure
• Just x = success and result x

4.2 Safe examples

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv m n = Just (m `div` n)

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

Using Maybe forces the caller to handle failure safely.

5) Recursive Data Types (Peano Naturals)

5.1 Declaring a recursive natural number type

data Nat = Zero | Succ Nat

Values look like:

• Zero = 0
• Succ Zero = 1
• Succ (Succ Zero) = 2
• …

5.2 Convert to/from Int

natToInt :: Nat -> Int
natToInt Zero     = 0
natToInt (Succ n) = 1 + natToInt n

intToNat :: Int -> Nat
intToNat 0 = Zero
intToNat n = Succ (intToNat (n-1))

5.3 Addition and multiplication recursively

add :: Nat -> Nat -> Nat
add Zero     n = n
add (Succ m) n = Succ (add m n)

Multiplication as repeated addition:

mult :: Nat -> Nat -> Nat
mult Zero     _ = Zero
mult (Succ n) m = add (mult n m) m

Termination intuition: each recursive step reduces the first Nat toward Zero.

6) Expression Trees (Expr)

6.1 Type declaration

data Expr = Val Int | Add Expr Expr | Mul Expr Expr

6.2 Build an expression

Expression: 1 + (2 * 3) becomes:

e :: Expr
e = Add (Val 1) (Mul (Val 2) (Val 3))

6.3 Size and evaluation

Count how many numbers (Val) occur:

size :: Expr -> Int
size (Val _)   = 1
size (Add x y) = size x + size y
size (Mul x y) = size x + size y

Evaluate numerically:

eval :: Expr -> Int
eval (Val n)   = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y

7) Folding Over Expressions (foldE)

7.1 Why folds matter

A fold captures the “primitive recursion pattern” for a structure. For lists, foldr replaces (:) and []. For expressions, foldE replaces Val, Add, and Mul.

7.2 Define foldE

foldE :: (Int -> a) -> (a -> a -> a) -> (a -> a -> a) -> Expr -> a
foldE fVal fAdd fMul = go
  where
    go (Val n)   = fVal n
    go (Add x y) = fAdd (go x) (go y)
    go (Mul x y) = fMul (go x) (go y)

7.3 Rebuild eval and size using foldE

eval :: Expr -> Int
eval = foldE id (+) (*)

size :: Expr -> Int
size = foldE (const 1) (+) (+)

This is a big moment: once you have a fold, many functions become one-liners.

8) Binary Trees with data in leaves

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

• Leaf a stores a value
• Node left right stores two subtrees

Example tree:

t :: Tree Int
t = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))

9) Bonus: Typeclasses and deriving (practical basics)

Even though your transcript focused more on type/data, the chapter title mentions “types and classes”. Here’s the most practical piece you’ll use immediately:

9.1 The problem

If you do:

data Answer = Yes | No | Unknown

GHC might not automatically know how to print it nicely, compare it, etc.

9.2 The fix: derive common classes

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

• Show lets you print values in GHCI.
• Eq lets you use == and /=.

Example:

Yes == No      -- False
show Unknown   -- "Unknown"

You’ll see deriving (Eq, Ord, Show, Read) a lot.

10) Practice Exercises (with solutions)

Exercise A — safeTail

Write a safe tail that fails on empty list:

safeTail :: [a] -> Maybe [a]
safeTail []     = Nothing
safeTail (_:xs) = Just xs

Exercise B — Expression: number of operators

Count how many Add/Mul nodes appear:

ops :: Expr -> Int
ops = foldE (const 0) (\a b -> 1 + a + b) (\a b -> 1 + a + b)

Exercise C — Tree leaf count

leafCount :: Tree a -> Int
leafCount (Leaf _)   = 1
leafCount (Node l r) = leafCount l + leafCount r

Glossary of Terms

• Type: A classification of values (e.g., Int, Bool, [Char]).
• Declare a type: In Haskell you declare types (not “define” them), using type or data.
• Type synonym: A nickname for an existing type (made with type).
• Algebraic Data Type (ADT): A custom type defined by listing its possible shapes/values (made with data).
• Constructor: A function that builds a value of a data type (e.g., Just, Nothing, Leaf, Node).
• Pattern matching: Deconstructing values by matching on their constructors (e.g., (x:xs), Just x, Node l r).
• Parameterized type: A type that takes a type parameter (e.g., Maybe a, Tree a).
• Recursive type: A type that refers to itself in its definition (e.g., data Nat = Zero | Succ Nat).
• Fold: A higher-order function that captures a common recursion pattern, replacing constructors with functions.

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Quizz & Progress Badge NFT