4.1 What "algebraic" means

An algebraic data type (ADT) is built from two algebra-like operations:

• Sum ("or"): a value is one of several alternatives → multiple constructors.
• Product ("and"): a constructor carries several fields → fields multiply together.

data Bool   = False | True                     -- pure sum (2 = 1 + 1 values)
data Point  = Pt Double Double                 -- pure product
data Shape  = Circle Double                    -- sum of products
            | Rect Double Double

Counting values: Shape ≈ Double + (Double × Double) — the type's structure literally is an algebraic expression. That's the origin of the name.

4.2 Constructors are functions; patterns take them apart

ghci> :t Circle
Circle :: Double -> Shape

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

perimeter :: Shape -> Double
perimeter (Circle r) = 2 * pi * r
perimeter (Rect w h) = 2 * (w + h)

Pattern matching over an ADT is exhaustive checking for free: forget the Rect equation and GHC warns "non-exhaustive patterns". Whole classes of runtime errors disappear.

4.3 Enumerations and records

data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
  deriving (Eq, Ord, Show, Enum, Bounded)

isWeekend :: Day -> Bool
isWeekend d = d >= Sat

-- record syntax names the fields and generates accessor functions
data Student = Student { name :: String, roll :: Int, cgpa :: Double }
  deriving Show

topper :: Student -> Bool
topper s = cgpa s >= 9.0

4.4 Parameterised types: Maybe and Either

ADTs can take type parameters — the same definitions work for every element type:

data Maybe a  = Nothing | Just a            -- "an a, or absence of one"
data Either a b = Left a | Right b          -- "an a OR a b" (often: error or result)

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv a b = Just (a `div` b)

lookupRoll :: String -> [(String, Int)] -> Maybe Int
lookupRoll _ [] = Nothing
lookupRoll k ((k', v) : rest)
  | k == k'   = Just v
  | otherwise = lookupRoll k rest

Maybe is Haskell's answer to the "null pointer" — absence is visible in the type, and the compiler forces every caller to handle the Nothing case. (Compare Java's Optional, Rust's Option — both are this ADT.)

4.5 Recursive algebraic types

A constructor field may be the type being defined — giving lists and trees:

-- the built-in list, if we defined it ourselves:
data List a = Nil | Cons a (List a)

-- binary tree
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 l v r)
  | x < v     = Node (insert x l) v r
  | x > v     = Node l v (insert x r)
  | otherwise = t                          -- already present

inorder :: Tree a -> [a]
inorder Leaf         = []
inorder (Node l v r) = inorder l ++ [v] ++ inorder r

-- build a BST and read it back sorted: 'tree sort'
treeSort :: Ord a => [a] -> [a]
treeSort = inorder . foldr insert Leaf

4.6 ADTs model your domain precisely

The design slogan: make illegal states unrepresentable.

-- an arithmetic expression language — the classic exam example
data Expr = Num Double
          | Add Expr Expr
          | Mul Expr Expr
          | Neg Expr

eval :: Expr -> Double
eval (Num n)   = n
eval (Add a b) = eval a + eval b
eval (Mul a b) = eval a * eval b
eval (Neg a)   = negate (eval a)

ghci> eval (Add (Num 2) (Mul (Num 3) (Num 4)))   -- 2 + 3*4
14.0

Ten lines define a complete interpreter: the ADT is the abstract syntax tree and pattern matching is the evaluator. This pattern — data type + recursive interpreter — scales up to real compilers, JSON parsers and rule engines, and it reappears in Prolog form in Unit 4 (structure inspection).

4.7 data vs type vs newtype — the three declaration forms

Why newtype matters: type Age = Int lets you accidentally add an age to a roll number; newtype Age = Age Int makes that a compile-time error while costing nothing at runtime. "Differentiate data, type and newtype" is a recurring 3-mark question — this table is the full answer.

4.8 The Maybe toolkit — total functions from partial ones

head, tail and division are partial (crash on some inputs). ADTs make them total:

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

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

-- consuming a Maybe: pattern match, or the catch-all eliminator
fromMaybe :: a -> Maybe a -> a
fromMaybe d Nothing  = d
fromMaybe _ (Just x) = x

ghci> fromMaybe 0 (safeHead [])
0
ghci> fromMaybe 0 (safeHead [7,8])
7

Either upgrades Nothing to an explanation: by convention Left carries the error, Right the result ("right" = correct):

safeDiv2 :: Int -> Int -> Either String Int
safeDiv2 _ 0 = Left "division by zero"
safeDiv2 a b = Right (a `div` b)

4.9 More tree programs (the standard exam set)

size :: Tree a -> Int                          -- number of Nodes
size Leaf         = 0
size (Node l _ r) = 1 + size l + size r

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

mirror :: Tree a -> Tree a
mirror Leaf         = Leaf
mirror (Node l v r) = Node (mirror r) v (mirror l)

treeMap :: (a -> b) -> Tree a -> Tree b        -- map, generalised to trees
treeMap _ Leaf         = Leaf
treeMap f (Node l v r) = Node (treeMap f l) (f v) (treeMap f r)

contains :: Ord a => a -> Tree a -> Bool       -- BST search, O(depth)
contains _ Leaf = False
contains x (Node l v r)
  | x == v    = True
  | x < v     = contains x l
  | otherwise = contains x r

Note the family resemblance: one equation per constructor — Leaf and Node — exactly as list functions have one for [] and one for (:). Structural recursion scales to any algebraic type.

4.10 Extending the interpreter — the classic follow-up question

"Add subtraction and division to Expr, where division by zero must be reported." Combine the ADT with Maybe:

data Expr2 = Num2 Double
           | Add2 Expr2 Expr2
           | Sub2 Expr2 Expr2
           | Div2 Expr2 Expr2

evalSafe :: Expr2 -> Maybe Double
evalSafe (Num2 n)   = Just n
evalSafe (Add2 a b) = combine (+) (evalSafe a) (evalSafe b)
evalSafe (Sub2 a b) = combine (-) (evalSafe a) (evalSafe b)
evalSafe (Div2 a b) = case (evalSafe a, evalSafe b) of
                        (Just _, Just 0)  -> Nothing          -- ÷ 0 caught!
                        (Just x, Just y)  -> Just (x / y)
                        _                 -> Nothing

combine :: (Double -> Double -> Double) -> Maybe Double -> Maybe Double -> Maybe Double
combine f (Just x) (Just y) = Just (f x y)
combine _ _        _        = Nothing

ghci> evalSafe (Div2 (Num2 6) (Add2 (Num2 1) (Num2 1)))
Just 3.0
ghci> evalSafe (Div2 (Num2 6) (Sub2 (Num2 1) (Num2 1)))
Nothing

Failure propagates automatically through combine — no exceptions, no flags, just the type system routing the Nothing.

Exam pointers

• "Define algebraic data type; explain sum and product types" — §4.1's two bullets plus Shape as the worked example, and the value-counting remark for the top mark.
• The Tree block (insert, inorder, size, depth, treeSort) is the most common 8-mark program of this unit — practise writing it cold.
• "Why is Maybe better than null/-1?" — absence is in the type; the compiler forces handling; no invalid value can masquerade as data.
• When asked to "design a data type for X" (library books, shapes, JSON...): constructors for each alternative, fields for each component, then one recursive function over it to show it works.

Self-check

1. How many values does (Bool, Bool) have? And Either Bool Bool? (Product vs sum, concretely.)
2. Write occurs :: Eq a => a -> Tree a -> Bool for arbitrary (non-BST) trees.
3. Why does treeSort produce a sorted list? Which property of insert and inorder combine to guarantee it?
4. Convert data Temp = Cold | Warm | Hot into the value-count "algebra" view.
5. Extend Expr with a Pow Expr Expr constructor and the matching eval equation.