0097: Email Tutorials – How to think recursively

FP11 Graham Hutton Video

A 7-step process for writing recursive functions

1. Name the function (short, conventional names in Haskell).
2. Write the type (types guide the design).
3. Enumerate cases (write the “skeleton” by pattern matching).
4. Define the simple cases (often base cases).
5. List ingredients you can use (parameters, the function itself, useful operators/constants).
6. Define the other cases (often recursive case(s), reduce the problem size).
7. Think about the result: can you generalize the type? can you simplify the definition (wildcards, merging cases, using foldr, etc.)?

Example 1: sum of a list

Skeleton (cases)

sum' []     = ...
sum' (x:xs) = ...

Simple case

Empty list sums to 0 (identity for +).

Recursive case

Add head to sum of tail:

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

Step 7: generalize + simplify

Generalize beyond Int, and recognize it’s a fold:

sum' :: Num a => [a] -> a
sum' = foldr (+) 0

Example 2: drop n elements from a list

Enumerate cases (0/n) × ([]/(x:xs)) ⇒ 4 cases

drop' 0 []       = ...
drop' 0 (x:xs)   = ...
drop' n []       = ...
drop' n (x:xs)   = ...

Simple cases

• Dropping 0 returns the list unchanged.
• Dropping from [] returns [] (design choice: don’t crash).

Recursive case idea

To drop n>0 from (x:xs), drop n-1 from xs.

Step 7: simplify with wildcards + merge cases

drop' :: Int -> [a] -> [a]
drop' 0 xs      = xs
drop' _ []      = []
drop' n (_:xs)  = drop' (n-1) xs

Example 3: init (remove last element of a non-empty list)

Goal: init [1,2,3] = [1,2].

Key move: pick the right “simple case”

The “easy” moment is when the tail is empty — i.e., the list has exactly one element.

Pattern-matching version (cleaner than guards)

init' :: [a] -> [a]
init' [_]    = []
init' (x:xs) = x : init' xs

And since the single element isn’t used:

init' :: [a] -> [a]
init' [_]    = []
init' (x:xs) = x : init' xs

⚠️ Note: the type can’t express “non-empty list” in plain Haskell 98 style, so init [] is still possible at the type level; the problem statement forbids it (and the real Prelude init errors on []).

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Quizz & Progress Badge NFT