Pearls of Functional Algorithm Design Skill

Core Methodology: Design by Calculation

Instead of inventing an efficient algorithm, derive it from a clear, correct specification by applying algebraic laws.

Process:

1. Write a clear, obviously correct specification (even if O(n²) or O(n!))
2. Apply equational reasoning and algebraic laws (fusion, scan lemma, etc.)
3. Transform the specification into an efficient implementation
4. The result is provably correct by construction

Why this matters: the specification is the proof; efficiency is a consequence of algebraic manipulation, not an independent claim.

---

Fundamental Patterns

Divide and Conquer Derivation

Starting from a specification that processes a list naively, apply:

• Scan lemma: if f (scanl op e xs) = g xs, derive a single-pass solution
• Fold fusion: foldr f e . map g = foldr (f . g) e
• List homomorphism: functions that can be computed in parallel (divide-and-conquer)

Maximum Segment Sum (Classic)

Specification (O(n²)):

mss = maximum . map sum . segs
segs xs = [drop i (take j xs) | j <- [0..n], i <- [0..j]]

Derived (O(n) via scan):

mss = maximum . scanl (λa x → max 0 (a + x)) 0

Key law used: maximum . map (maximum . map sum . tails) . inits = scanl (...)

Smallest Free Number

Specification (O(n log n)):

minfree = head . filter (`notElem` xs) $ [0..]

Derived (O(n)): Use partition: count elements ≤ n/2, if count < n/2+1 then answer is in [0..n/2], else in [n/2+1..]

minfree xs = minfrom 0 (length xs, xs)
minfrom a (n, xs)
  | n == 0 = a
  | otherwise = if m == b - a
                then minfrom b (n - m, bs)
                else minfrom a (m, as)
  where (as, bs) = partition (< b) xs
        b = a + 1 + n `div` 2
        m = length as

---

String Matching Algorithms (Derived)

Knuth-Morris-Pratt (KMP)

Derived from the naive O(nm) specification by noting that on mismatch, you already know some characters of the pattern from what you just matched.

Specification:

matches pat = map (pat `isPrefixOf`) . tails

Derivation approach: define next function (failure function) that avoids re-scanning matched characters. The next-function is itself derived by induction on the pattern.

Boyer-Moore

Also derived from specification by calculating the “bad character” and “good suffix” shift functions from the pattern alone.

---

Greedy Algorithm Derivation

Chapter “Unravelling greedy algorithms” shows the conditions under which a greedy approach works:

Condition: a greedy choice is valid when:

1. The problem has optimal substructure
2. A locally optimal choice never needs to be revised (greedy choice property)

Bird derives these conditions algebraically rather than arguing informally.

Practical test: if the problem can be expressed as minimum . filter valid . map cost . permutations, check if a greedy ordering produces the same result as exhaustive search by proving a “greedy condition” lemma.

---

Functional Data Structures

Burrows-Wheeler Transform (Data Compression)

-- Forward BWT: produces transformed string + index
bwt :: String → (String, Int)
bwt xs = (map last rotations, position xs rotations)
  where rotations = sort [drop i xs ++ take i xs | i <- [0..n-1]]
        n = length xs

-- The BWT groups similar characters together → better compression

Suffix Arrays (Ranking Suffixes)

Build sorted suffix array in O(n log n) by:

1. Sort suffixes by first character
2. Sort by first 2 characters using ranks from step 1
3. Double the comparison length each time → O(n log n) total

Derived from the simple O(n² log n) sort via a radix sort argument.

---

Loopless Algorithms

A loopless algorithm generates successive values of a combinatorial sequence where each next value is computed in O(1) time.

Example (Fibonacci sequence): maintain a small state that can be updated in O(1) per step.

Johnson-Trotter permutation generation: generate all n! permutations of n elements where each successive permutation differs by a single adjacent transposition.

Key insight: instead of recomputing from scratch, maintain invariants that allow O(1) update.

---

Inside Convex Hull

Problem: given a set of points and a query point, determine if the query is inside the convex hull.

Derived algorithm:

1. Sort points by angle around centroid
2. Binary search to find the triangle sector containing the query
3. Point-in-triangle test

Linear preprocessing, O(log n) per query. Derived from the obvious O(n) scan by recognizing the rotational monotonicity.

---

Key Algebraic Laws Used Throughout

-- Map fusion
map f . map g = map (f . g)

-- Filter fusion
filter p . filter q = filter (λx → p x && q x)

-- Fold/unfold (deforestation)
foldr f e . map g = foldr (f . g) e

-- Scan lemma
map (foldr op e) . tails = scanr op e

-- Banana split (process a list once for two results)
(map f &&& map g) = map (f &&& g)

---

Practical Takeaways for Algorithm Design

1. Start with the clearest specification, even if inefficient
2. Apply fusion laws to eliminate intermediate data structures
3. Look for scan/fold equivalences to convert O(n²) to O(n)
4. When a greedy works, you can prove it algebraically, not just argue by intuition
5. Loopless algorithms maintain state invariants for O(1) next-step updates
6. Equational reasoning produces correct-by-construction algorithms — no need for separate proofs