Scrolls
6 min read
On this page

Recursion Patterns

Haskell has no for or while. Loops are recursion, full stop. This sounds limiting until you realize that almost every loop you write is one of three or four patterns, and the standard library already has names for them. Most of the time you'll use map, filter, foldr, or foldl' instead of writing recursion by hand. But knowing how those are built — and when to write recursion directly — is what separates "Haskell code that works" from "Haskell code that fits."

Base Case + Recursive Case

Every recursive function has the same shape: handle the empty/zero/trivial case, and reduce the non-trivial case to a smaller version of itself. For lists, that usually means:

-- Sum a list
sumList :: [Int] -> Int
sumList []     = 0                     -- base case
sumList (x:xs) = x + sumList xs        -- recursive case

Read it as: the sum of an empty list is zero; the sum of a non-empty list is the head plus the sum of the tail. This is structural recursion: you decompose the list one element at a time, and the recursion is guaranteed to terminate because the input gets strictly smaller.

A few more in the same shape:

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

doubleAll :: [Int] -> [Int]
doubleAll []     = []
doubleAll (x:xs) = x * 2 : doubleAll xs

allPositive :: [Int] -> Bool
allPositive []     = True
allPositive (x:xs) = x > 0 && allPositive xs

These three are length, map (* 2), and all (> 0). You'll never write them by hand in real code. But recognizing the pattern is what lets you reach for map instead.

Structural Recursion

Structural recursion follows the shape of the data. For lists: empty case and cons case. For trees: leaf case and branch case. For natural numbers (rare in real code, common in textbook examples): zero case and successor case.

data Tree a = Leaf | Node (Tree a) a (Tree a)

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

treeSum :: Num a => Tree a -> a
treeSum Leaf         = 0
treeSum (Node l x r) = x + treeSum l + treeSum r

The recursive call always operates on a substructure of the input. This is the safest kind of recursion because termination is obvious from the type.

Accumulator Recursion

Sometimes you need to thread a running value through the computation. The pattern is to add a "state" parameter that you pass along:

-- Sum, but with an accumulator
sumList' :: [Int] -> Int
sumList' xs = go 0 xs
  where
    go acc []     = acc
    go acc (x:xs) = go (acc + x) xs

The wrapper sumList' calls a helper go with an initial accumulator of zero. Each recursive call updates the accumulator and continues with the tail. When the list is empty, return the accumulator.

This pattern is the recursive equivalent of:

def sum_list(xs):
    acc = 0
    for x in xs:
        acc = acc + x
    return acc

Accumulator recursion is essential when:

  • You're building a result that depends on what you've seen so far (running averages, max so far, parser state).
  • You want tail recursion for performance reasons (more on this below).
  • You're reversing a list, where each step prepends to the accumulator:
reverse' :: [a] -> [a]
reverse' xs = go [] xs
  where
    go acc []     = acc
    go acc (x:xs) = go (x : acc) xs

This is O(n). The naive reverse xs = reverse (tail xs) ++ [x] is O(n²) because of repeated ++.

Tail Recursion (And Why It Matters Less in Haskell)

A function is tail recursive if the recursive call is the last thing it does, with no pending operation around it:

-- Tail recursive: the recursive call IS the result
go :: Int -> [Int] -> Int
go acc []     = acc
go acc (x:xs) = go (acc + x) xs

-- Not tail recursive: there's an addition waiting on the result
sumList :: [Int] -> Int
sumList []     = 0
sumList (x:xs) = x + sumList xs

In strict languages like Scheme or Scala, tail recursion matters a lot because the compiler can turn it into a loop and avoid stack overflow. In Haskell, the story is more nuanced:

Laziness changes the picture. The naive sumList doesn't immediately add x to the recursive result; it builds a thunk like x + (x' + (x'' + ...)). The stack doesn't blow up during recursion — it blows up later when something forces the thunk. So tail recursion isn't the magic bullet it is in strict languages.

The real fix is usually strictness, not tail recursion. A tail-recursive go that lazily accumulates a giant thunk in acc will still leak memory. You need seq or a bang pattern:

{-# LANGUAGE BangPatterns #-}

sumList :: [Int] -> Int
sumList = go 0
  where
    go !acc []     = acc                -- ! forces acc each iteration
    go !acc (x:xs) = go (acc + x) xs

Now each iteration evaluates the new accumulator before recursing, and the function runs in constant space.

For most "fold-like" tasks, just use foldl'. It's already strict and tail-recursive:

import Data.List (foldl')

sumList :: [Int] -> Int
sumList = foldl' (+) 0

We'll cover folds in detail next page.

Common Recursion Patterns

A few patterns come up so often it's worth naming them:

Map: per-element transformation

mapList :: (a -> b) -> [a] -> [b]
mapList _ []     = []
mapList f (x:xs) = f x : mapList f xs

You'll use map itself, but this is what's happening underneath.

Filter: per-element predicate

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

Fold: collapse to a value

foldList :: (a -> b -> b) -> b -> [a] -> b
foldList _ z []     = z
foldList f z (x:xs) = f x (foldList f z xs)

This is foldr. It's the most general list operation; almost everything else can be defined in terms of it.

Zip: walk two lists in parallel

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

Unfold: build up from a seed

The dual of fold. Given a starting value and a step function, produce a list:

import Data.List (unfoldr)

countdown :: Int -> [Int]
countdown = unfoldr step
  where
    step 0 = Nothing
    step n = Just (n, n - 1)

-- countdown 5 == [5, 4, 3, 2, 1]

Real use: parsing input chunks, generating sequences from state, lazy file readers.

A Realistic Example

Here's a function that splits a list at every occurrence of a delimiter — the kind of utility you'd write for a parser or log analyzer:

splitOn :: Eq a => a -> [a] -> [[a]]
splitOn d xs = go [] xs
  where
    go acc []     = [reverse acc]
    go acc (y:ys)
      | y == d    = reverse acc : go [] ys
      | otherwise = go (y : acc) ys

-- splitOn ',' "a,b,c" == ["a", "b", "c"]
-- splitOn ',' ""      == [""]

This combines structural recursion (walking the input list) with an accumulator (collecting the current chunk). The reverse at the end of each chunk is because we prepend during accumulation; if we appended, we'd get O(n²).

A more "Haskell-ish" version uses foldr:

splitOn :: Eq a => a -> [a] -> [[a]]
splitOn d = foldr step [[]]
  where
    step y (chunk:chunks)
      | y == d    = [] : chunk : chunks
      | otherwise = (y : chunk) : chunks

Both are O(n). The fold version is shorter but harder to read until you've seen the pattern. Pick whichever you and your team find clearer.

Mutual Recursion

Sometimes two functions call each other:

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

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

This is rare in practice — most cases are better written as a single function with a flag — but it's legal and shows up in parser combinators and tree walkers with multiple node types.

Common Pitfalls

Forgetting the base case. Without it, the function recurses forever. GHC won't catch this; you'll just hang at runtime. Always write the base case first.

Recursing on the wrong thing. f xs = ... f xs ... is infinite recursion. The recursive call must be on a smaller piece (tail xs, n - 1, a subtree).

Lazy accumulators that build giant thunks. This is the Haskell-specific footgun. If you write a tail-recursive accumulator and it runs out of memory on big inputs, you forgot to force the accumulator. Use a bang pattern or seq.

Reaching for recursion when map, filter, or foldr would do. Hand-written recursion has more places for bugs to hide. If your function fits a known pattern, use the named version.

reverse . map f pipelines. People sometimes write recursion to build a list in reverse, then reverse it at the end, when a foldr would build it correctly the first time.

Key Takeaways

Loops in Haskell are recursion. Most recursion follows one of four patterns: structural (walk the data shape), accumulator (thread state), unfold (build from a seed), or mutual (two functions calling each other). Tail recursion matters less in Haskell than in strict languages because laziness shifts when the stack actually grows; the real performance fix for accumulators is strictness, not tail position. Before writing recursion by hand, check if map, filter, foldr, or foldl' already does what you want. They almost always do.