Haskell Folds Illustrated

Now that I’ve submitted my PhD thesis for examination (finally!) I can spend some time fiddling around with things that are unrelated to it. After a hiatus of several months I’m finally back to playing with Haskell.

One of the things that make Haskell notoriously hard and non-intuitive to learn is the idea of functions that act on other functions (higher order functions). Folds were the first thing that really made things fit together in my mind and helped me understand the strengths of functional programming and why people rave about elegance in haskell.

What is a fold in Haskell?

A fold is Haskell’s general way of replacing a loop. Whenever a program starts with an initial value, visits each element of a collection, and updates a result, it is folding.

In an imperative language, summing a list might look like this:

total = 0
for value in values:
    total = total + value

In Haskell, the same pattern is captured by foldl (+) 0 values. The combining function is (+), 0 is the initial accumulator (often called the seed), and values is the list being consumed.

Reading the type signatures

Haskell’s two basic list folds traverse the structure in different directions:

foldl :: (acc -> element -> acc) -> acc -> [element] -> acc
foldr :: (element -> acc -> acc) -> acc -> [element] -> acc

The names acc and element are more descriptive than the conventional single-letter type variables. Both functions take three arguments:

1. a function that combines one list element with an accumulator;
2. an initial accumulator; and
3. a list of elements.

Both return the final accumulator. The apparently reversed combining functions are important: foldl supplies the accumulator first, while foldr supplies the current element first.

For example, foldl (+) 0 [1, 2, 3] uses 0 as the first accumulator, combines it with 1, then combines that result with 2, and finally with 3.

The left fold, illustrated

flowchart LR
  Z["seed: 0"] --> F1["f accumulator element"]
  X1["element: 1"] --> F1
  F1 -->|"accumulator: 1"| F2["f accumulator element"]
  X2["element: 2"] --> F2
  F2 -->|"accumulator: 3"| F3["f accumulator element"]
  X3["element: 3"] --> F3
  F3 --> R["result: 6"]

A left fold groups its applications from the left:

foldl (+) 0 [1, 2, 3]
= ((0 + 1) + 2) + 3
= 6

The grouping becomes easier to see with a non-associative operation such as subtraction:

foldl (-) 0 [1, 2, 3]
= ((0 - 1) - 2) - 3
= -6

The right fold, illustrated

flowchart LR
  X1["element: 1"] --> F1["f element accumulator"]
  X2["element: 2"] --> F2["f element accumulator"]
  X3["element: 3"] --> F3["f element accumulator"]
  Z["seed: 0"] --> F3
  F3 -->|"accumulator: 3"| F2
  F2 -->|"accumulator: 5"| F1
  F1 --> R["result: 6"]

A right fold groups applications from the right:

foldr (+) 0 [1, 2, 3]
= 1 + (2 + (3 + 0))
= 6

Again, subtraction exposes the difference:

foldr (-) 0 [1, 2, 3]
= 1 - (2 - (3 - 0))
= 2

The traversal direction is therefore observable whenever the combining function is not associative. It also affects laziness and memory use, even when both folds eventually produce the same value.

foldl vs foldr vs foldl'

The most useful rule of thumb is:

Function	Use it when	Important property
foldr	Producing a lazy structure or short-circuiting	Can work with infinite lists when the combining function does not always need its second argument
foldl	You specifically need a lazy accumulator	Builds a chain of deferred computations and is rarely the best choice for strict reductions
foldl'	Computing a strict running result such as a sum, product, count, or checksum	Forces the accumulator at every step, usually avoiding the large thunk built by foldl

foldl' lives in Data.List, so practical strict reductions commonly begin with:

import Data.List (foldl')

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

Why can foldl use so much memory?

Because Haskell is lazy, foldl (+) 0 [1, 2, 3] can construct a deferred expression resembling this before doing the additions:

(((0 + 1) + 2) + 3)

On a large list, that chain of unevaluated work can occupy substantial memory. foldl' evaluates the accumulator at each step instead. Its strictness is only to weak head normal form, so an accumulator with lazy fields may need additional care, but it is the normal default for simple numeric reductions.

Why can foldr work with infinite lists?

foldr gives the combining function the first element before it must reach the end of the list. If that function can produce part of its answer without evaluating the recursive accumulator, the consumer can make progress. For example:

take 3 (foldr (:) [] [1..])
-- [1,2,3]

foldr (\x rest -> x > 3 || rest) False [1..]
-- True

This is conditional, not magical. foldr (+) 0 [1..] still never produces a finite sum because (+) needs the recursive result. A left fold, meanwhile, must reach the end before it can return its outermost result, so it cannot finish traversing an infinite list.

Examples of folds

Summing a list

For a strict numerical total, prefer foldl':

import Data.List (foldl')

sumValues :: [Double] -> Double
sumValues = foldl' (+) 0

Numerical integration

A simple rectangular approximation to the integral of a sampled signal $x[t]$, with sample period $\Delta T$, is:

$S = \sum_{i=0}^{N} x[i] \cdot \Delta T$

The direct fold keeps the accumulator strict and also behaves sensibly for an empty list:

import Data.List (foldl')

simpleIntegral :: Double -> [Double] -> Double
simpleIntegral dT = foldl' (\area sample -> area + sample * dT) 0

This is the same state update used by the integral term of a discrete PID controller. In a real controller, the accumulator might also store the previous error, enforce anti-windup limits, or track time explicitly.

Scans and filtering

Sometimes the intermediate accumulator values are the result we want. A scan uses the same update pattern as a fold but returns every intermediate state. That makes it useful for filters and state histories.

For an exponential moving average,

$$S_t = \begin{cases} Y_1 & \text{if } t = 0 \\ \alpha Y_t + (1-\alpha)S_{t-1} & \text{if } t > 0, \end{cases}$$

we can write:

ema :: Double -> [Double] -> [Double]
ema alpha = scanl1 update
  where
    update previous current =
      alpha * current + (1 - alpha) * previous

Unlike foldl1, which returns only a final value, scanl1 returns the first sample and every subsequently filtered sample. Both functions are partial on an empty list, so production code should either rule out empty input or represent it with a type such as NonEmpty.

Checksums and state machines

An accumulator need not be a number. It can be a parser state, a histogram, a rolling checksum, or a record holding several pieces of sensor state. A small byte checksum is still the same pattern:

import Data.Bits (xor)
import Data.List (foldl')
import Data.Word (Word8)

checksum :: [Word8] -> Word8
checksum = foldl' xor 0

A parser can similarly fold tokens into a state containing the current syntax context and any values parsed so far. A robotics pipeline might fold timestamped measurements into an orientation estimate. The types change; the pattern of repeatedly updating state does not.

Common questions and mistakes

When should I use foldl'?

Use it for a finite list when each step should update a strict result: sums, products, counts, extrema, checksums, and many Map- or record-building loops. Use foldr when laziness, short-circuiting, or constructing a list-like result matters.

Does foldr traverse a list faster than foldl'?

Not inherently. Their evaluation behaviour is different, and the surrounding program matters. foldr can fuse well with lazy list producers and consumers; foldl' is usually a good fit for consuming a whole finite list into one strict value. Benchmark the complete operation when performance matters.

Why does foldl not reverse a list automatically?

The direction of a fold determines how function applications are nested, not the order in which values must appear in the output. The combining function makes that choice. Prepending each new element reverses a finite list:

reverseWithFold :: [a] -> [a]
reverseWithFold = foldl' (flip (:)) []

Using foldl' (++) [] instead preserves the order but repeatedly walks the growing accumulator, making it inefficient.

Why does foldl not short-circuit?

A left fold cannot expose its final result until it has reached the end of the input. A right fold can short-circuit when its combining function ignores the recursive result in some cases, as (||) and (&&) do.

Are foldl1 and foldr1 safer shortcuts?

They remove the need to provide a seed by using an element from the list, but they fail on empty lists. Prefer a seeded fold when there is a natural identity value, or use NonEmpty when the input must contain at least one element.

Summing up

Folds capture a common computational shape: start with a state and update it from a sequence of inputs. That shape appears in totals, numerical integration, PID controllers, complementary filters, checksums, parsers, histograms, and sensor-fusion algorithms.

The practical choice is usually straightforward: reach for foldl' when reducing a finite list to a strict value, and use foldr when producing a lazy structure or taking advantage of short-circuiting. More important than memorising that rule is learning to see the accumulator-and-update pattern. Once it becomes familiar, many explicit loops collapse into small, reusable functions.

For another example of folds and scans in practice, see Learning Haskell Through Google Code Jam.

References

1. Learn You a Haskell: Higher-Order Functions
2. Data.List documentation
3. Hutton, Graham. “A tutorial on the universality and expressiveness of fold.” Journal of Functional Programming 9.4 (1999): 355–372.
4. Exponential Moving Average