2.1 Pattern matching — branching on the shape of data

A pattern appears on the left of a defining equation and does two jobs at once: it tests the shape of the argument and names its parts.

Equations are tried top to bottom; the first matching one fires.

isEmpty :: [a] -> Bool
isEmpty []    = True
isEmpty (_:_) = False

2.2 The standard recursion template for lists

Because every list is either [] or x : xs, list recursion always has the shape:

f []     = ...base case: answer for the empty list...
f (x:xs) = ...combine x with the recursive result f xs...

Classic examples (memorise these — they are the most-asked exam codes):

-- length
len :: [a] -> Int
len []     = 0
len (_:xs) = 1 + len xs

-- sum
total :: [Int] -> Int
total []     = 0
total (x:xs) = x + total xs

-- append (++)
app :: [a] -> [a] -> [a]
app [] ys     = ys
app (x:xs) ys = x : app xs ys

-- reverse (naive, O(n^2))
rev :: [a] -> [a]
rev []     = []
rev (x:xs) = rev xs ++ [x]

-- map and filter, defined by hand
myMap :: (a -> b) -> [a] -> [b]
myMap _ []     = []
myMap f (x:xs) = f x : myMap f xs

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter _ [] = []
myFilter p (x:xs)
  | p x       = x : myFilter p xs
  | otherwise = myFilter p xs

2.3 Hand-evaluation (a guaranteed exam skill)

total [3,5,7]
= 3 + total [5,7]
= 3 + (5 + total [7])
= 3 + (5 + (7 + total []))
= 3 + (5 + (7 + 0))
= 15

2.4 Accumulating parameters — making recursion efficient

rev above is O(n²) because ++ re-walks the front list. The accumulator technique carries the partial answer along:

revFast :: [a] -> [a]
revFast xs = go xs []
  where go []     acc = acc
        go (y:ys) acc = go ys (y : acc)    -- tail recursion, O(n)

revFast [1,2,3]
= go [1,2,3] []
= go [2,3] [1]
= go [3] [2,1]
= go [] [3,2,1]
= [3,2,1]

A call whose result is immediately returned (no work after the call) is tail recursive — the compiler turns it into a loop.

2.5 Recursion patterns beyond one list

Two lists in step:

myZip :: [a] -> [b] -> [(a, b)]
myZip [] _          = []
myZip _ []          = []
myZip (x:xs) (y:ys) = (x, y) : myZip xs ys

Divide and conquer — quicksort, the famous two-liner:

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (p:xs) = qsort [ y | y <- xs, y < p ]
               ++ [p] ++
               qsort [ y | y <- xs, y >= p ]

Primitive recursion on numbers mixed with lists:

myTake :: Int -> [a] -> [a]
myTake 0 _      = []
myTake _ []     = []
myTake n (x:xs) = x : myTake (n-1) xs

2.6 Designing a recursive function — checklist

1. Write the type.
2. List the constructors of the input ([] and (:) for lists) — one equation each.
3. In the cons case, assume f xs already works (the inductive hypothesis!) and ask only: how do I combine x with it?
4. Check the base case really terminates the recursion (every call must shrink the input).
5. Test edge cases: empty list, one element, duplicates.

This is structural induction turned into a programming method — the deep reason functional programs are so often provably correct.

2.7 The sorting trio — insertion sort, merge sort, quicksort

Sorting algorithms are the most common "write a program" questions of this unit. All three follow the standard template:

-- insertion sort: insert each head into the sorted tail
insert :: Ord a => a -> [a] -> [a]
insert x []     = [x]
insert x (y:ys)
  | x <= y    = x : y : ys
  | otherwise = y : insert x ys

isort :: Ord a => [a] -> [a]
isort []     = []
isort (x:xs) = insert x (isort xs)

-- merge sort: split, sort halves, merge
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort front) (msort back)
  where (front, back) = splitAt (length xs `div` 2) xs

Trace of isort [3,1,2] (show this style of working in the exam):

isort [3,1,2]
= insert 3 (isort [1,2])
= insert 3 (insert 1 (isort [2]))
= insert 3 (insert 1 (insert 2 []))
= insert 3 (insert 1 [2])
= insert 3 [1,2]
= [1,2,3]

2.8 Proving properties by structural induction (worked proof)

The recursion template is also a proof template. To prove a property P(xs) for all finite lists: prove P([]) (base) and prove P(x:xs) assuming P(xs) (inductive step).

Claim: len (app xs ys) = len xs + len ys (with len, app from §2.2).

Base: len (app [] ys) = len ys              -- app.1
                      = 0 + len ys          -- arithmetic
                      = len [] + len ys     -- len.1   ✓

Step: assume len (app xs ys) = len xs + len ys.  Then
      len (app (x:xs) ys)
    = len (x : app xs ys)                   -- app.2
    = 1 + len (app xs ys)                   -- len.2
    = 1 + (len xs + len ys)                 -- induction hypothesis
    = (1 + len xs) + len ys                 -- associativity
    = len (x:xs) + len ys                   -- len.2 backwards ✓

Every line is justified by one defining equation or one known law — that justification column is where the marks are. The same scheme proves rev (app xs ys) = app (rev ys) (rev xs) and map f (map g xs) = map (f . g) xs, both classic exam proofs.

2.9 Pattern matching vs unification — a preview comparison

Haskell's pattern matching is one-directional: the pattern may contain variables, the value being matched may not be partly unknown. Prolog's unification (Unit 3) is two-directional — variables may appear on both sides. Keep this table for the inevitable comparison question:

2.10 Wildcards, as-patterns and overlap

-- as-pattern: name the WHOLE value and its parts at once
firstTwoSame :: Eq a => [a] -> [a]
firstTwoSame all@(x:y:_) | x == y = all
firstTwoSame _                    = []

Equation order matters when patterns overlap: put specific patterns first, catch-alls last. Writing myTake's equations in a different order changes its meaning on myTake 0 undefined — a subtle point that distinguishes top answers.

Exam pointers

• The §2.2 block (len, total, app, rev, myMap, myFilter) is the question bank — be able to write each from memory with its type.
• For traces: one rewrite per line, each justified by exactly one equation; finish with the fully evaluated value.
• "Prove by induction" questions follow §2.8's two-part shape exactly; always state the induction hypothesis explicitly.
• Accumulator transformation (naive rev → revFast) is a standard "improve the efficiency" question — quote the O(n²) → O(n) change and why (++ re-walks its left argument).

Self-check

1. Write myDrop :: Int -> [a] -> [a] in the style of myTake.
2. Trace app [1,2] [3] step by step.
3. Which equations of myZip fire for myZip [1] ['a','b'], and what is the result?
4. Prove total (app xs ys) = total xs + total ys by structural induction.
5. Why is rev quadratic? Where exactly does the extra work happen?
6. Rewrite maxList :: [Int] -> Int first with explicit recursion, then as foldr1 max.