Pattern Matching and Recursion

Pattern matching and recursion are core techniques in functional programming that work hand-in-hand to process data structures and implement algorithms.

See also: Algebraic Data Types, Lists and List Comprehensions, Functions and Equations, Higher-Order Functions, Error Handling

Pattern Matching

See: Algebraic Data Types, Lists and List Comprehensions, Functions and Equations

Basic Syntax

Pattern matching is often used in function definitions:

functionName pattern1 = result1
functionName pattern2 = result2
functionName pattern3 = result3

The patterns are tried in order until one matches.

Patterns for Different Types

• Numbers and Characters: See Equational Reasoning
• Lists: See Lists and List Comprehensions
• Tuples: See Algebraic Data Types
• ADTs: See Algebraic Data Types

Matching on Numbers and Characters

isZero :: Int -> Bool
isZero 0 = True
isZero _ = False
 
isVowel :: Char -> Bool
isVowel 'a' = True
isVowel 'e' = True
isVowel 'i' = True
isVowel 'o' = True
isVowel 'u' = True
isVowel _ = False

Matching on Lists

isEmpty :: [a] -> Bool
isEmpty [] = True
isEmpty _ = False
 
head' :: [a] -> a
head' [] = error "Empty list"
head' (x:_) = x
 
tail' :: [a] -> [a]
tail' [] = error "Empty list"
tail' (_:xs) = xs
 
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs

Matching on Tuples

fst' :: (a, b) -> a
fst' (x, _) = x
 
snd' :: (a, b) -> b
snd' (_, y) = y
 
addPairs :: [(Int, Int)] -> [Int]
addPairs [] = []
addPairs ((x, y):ps) = (x + y) : addPairs ps

Matching on Algebraic Data Types

data Shape = Circle Float | Rectangle Float Float
 
area :: Shape -> Float
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
 
data Tree a = Leaf | Node a (Tree a) (Tree a)
 
treeDepth :: Tree a -> Int
treeDepth Leaf = 0
treeDepth (Node _ left right) = 1 + max (treeDepth left) (treeDepth right)

Pattern Guards

Pattern guards add conditions to patterns:

absoluteValue :: Int -> Int
absoluteValue n
  | n < 0     = -n
  | otherwise = n
 
grade :: Int -> String
grade score
  | score >= 90 = "A"
  | score >= 80 = "B"
  | score >= 70 = "C"
  | score >= 60 = "D"
  | otherwise   = "F"

case Expressions

Pattern matching can also be done within expressions using case:

describePair :: (Int, Int) -> String
describePair pair = case pair of
  (0, 0) -> "Origin"
  (0, _) -> "Y-axis"
  (_, 0) -> "X-axis"
  (x, y) -> "Point at (" ++ show x ++ "," ++ show y ++ ")"

Recursion

See: Functions and Equations, Higher-Order Functions, Lists and List Comprehensions

Anatomy of Recursive Functions

1. Base case(s): Simple scenarios where the result is directly computed
2. Recursive case(s): Complex scenarios where the result depends on smaller instances of the same problem

List Processing with Recursion

See: Lists and List Comprehensions, Higher-Order Functions

length' :: [a] -> Int
length' [] = 0                -- Base case
length' (_:xs) = 1 + length' xs  -- Recursive case
 
map' :: (a -> b) -> [a] -> [b]
map' _ [] = []               -- Base case
map' f (x:xs) = f x : map' f xs  -- Recursive case
 
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []            -- Base case
filter' p (x:xs)             -- Recursive case
  | p x       = x : filter' p xs
  | otherwise = filter' p xs

Recursive Numerical Functions

-- Factorial
factorial :: Integer -> Integer
factorial 0 = 1                    -- Base case
factorial n = n * factorial (n-1)  -- Recursive case
 
-- Fibonacci
fibonacci :: Int -> Integer
fibonacci 0 = 0                              -- Base case 1
fibonacci 1 = 1                              -- Base case 2
fibonacci n = fibonacci (n-1) + fibonacci (n-2)  -- Recursive case

Tree Traversal with Recursion

See: Algebraic Data Types

-- Sum all values in a tree
treeSum :: Tree Int -> Int
treeSum Leaf = 0
treeSum (Node value left right) = value + treeSum left + treeSum right
 
-- Map a function over all values in a tree
treeMap :: (a -> b) -> Tree a -> Tree b
treeMap _ Leaf = Leaf
treeMap f (Node value left right) = Node (f value) (treeMap f left) (treeMap f right)

Mutual Recursion

See: Equational Reasoning

Functions can also be mutually recursive, calling each other:

isEven :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n-1)
 
isOdd :: Int -> Bool
isOdd 0 = False
isOdd n = isEven (n-1)

Tail Recursion

See: Evaluation Strategies

Tail recursion is a special case where the recursive call is the last operation:

-- Not tail recursive
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs  -- Must do addition after recursive call
 
-- Tail recursive version with accumulator
sumTail :: [Int] -> Int
sumTail xs = sumHelper xs 0
  where
    sumHelper [] acc = acc
    sumHelper (x:xs) acc = sumHelper xs (acc + x)  -- Recursive call is last operation

Benefits of tail recursion:

• Can be optimized by the compiler into iteration
• Doesn’t grow the call stack
• Prevents stack overflow for large inputs

Key Points to Remember

1. Pattern matching is a fundamental technique for working with data in Haskell
2. Patterns are tried in order; use _ as a catch-all pattern
3. Recursion replaces loops in functional programming
4. Every recursive function needs at least one base case to terminate
5. Tail recursion can be more efficient for large inputs