21  Reduce and accumulate

You have a list of data frames from an API and you need to merge them all into one. map() will not help: it treats every element in isolation and never looks at what came before. What you need is a way to take two things, combine them, feed the result into the next combination, and keep going until one thing remains. That operation is Reduce().

map() (Chapter 19) replaces loops that apply a function element by element. Reduce() replaces the other kind: loops that carry state from one pass to the next, like a running total or a chain of merges that folds data frames together one by one.

21.1 Left fold

Reduce() takes a binary function and a list, then combines the elements pairwise from left to right:

Reduce(`+`, 1:5)
#> [1] 15

That computes ((((1 + 2) + 3) + 4) + 5). The first call is f(1, 2), which gives 3; then f(3, 3), giving 6; then f(6, 4), giving 10; then f(10, 5), giving 15. Each intermediate result becomes the left argument of the next call, which is why this is called a left fold (Haskell’s foldl): the parentheses nest to the left.

With a named function the folding structure becomes visible:

Reduce(paste, c("the", "cat", "sat", "on", "the", "mat"))
#> [1] "the cat sat on the mat"

Each step takes the accumulated string and pastes the next word onto it. The accumulator grows; the list shrinks. When nothing remains, the accumulator is the answer.

21.2 The init argument

What does Reduce(f, x) do when x has one element? It returns that element without calling f. And with zero elements?

Reduce(`+`, list())
#> NULL

NULL, because there is nothing to combine and Reduce() has no idea what nothing adds up to. Anything downstream that expected a number now has NULL instead. The init argument tells it:

Reduce(`+`, list(), init = 0)
#> [1] 0

With init, the fold starts by calling f(init, x[[1]]) instead of f(x[[1]], x[[2]]), so it always has something to work with, even on an empty list. The value to pass is the one that leaves the operation unchanged: 0 for addition, 1 for multiplication, "" for paste0, NULL for c(). Section 4.1 called this the identity element. For intersect you would want the universal set, which R has no way to write, so you typically peel off the first element yourself.

TipOpinion

Always pass init to Reduce(). Without it, your code returns NULL on empty input and behaves subtly differently on length-1 input. The identity element makes the fold total: it works for every list, including the empty one, and it still works six months from now when some upstream function returns zero results.

An associative operation with an identity element is a monoid, the structure from Section 4.1 that has since reappeared as verb composition, the pipe, and ggplot2 layers. Reduce() is the operation that collapses one: given a list and an associative binary function, it produces a single value. Piping is a fold over a list of functions with composition as the operation and the identity function as init; building a ggplot layer by layer is a fold over a list of layers with + as the operation and ggplot() as init. Associativity is also what makes a fold splittable: chunks can be folded separately and their results folded again without changing the answer, which is the shape of Google’s MapReduce (Dean and Ghemawat, 2004), map() followed by a monoid fold across a warehouse of machines.

21.3 Right fold

Reduce() folds from the left by default. Setting right = TRUE reverses the nesting:

Reduce(`-`, 1:4)
#> [1] -8
Reduce(`-`, 1:4, right = TRUE)
#> [1] -2

The left fold computes (((1 - 2) - 3) - 4) = -8. The right fold computes (1 - (2 - (3 - 4))) = -2. For associative operations (addition, multiplication, paste0, c(), intersect, union) the direction does not matter; you get the same answer either way, and left fold is the natural default. The difference only surfaces for non-associative operations: subtraction, division, exponentiation.

In R, right = TRUE is rarely needed. If you find yourself reaching for a right fold, ask first whether your binary function simply has its arguments in the wrong order.

Haskell has foldl and foldr as separate functions, and there the choice matters. With lazy evaluation a right fold can stop early, even on an infinite list, when the combining function does not need its second argument; a left fold over a long list builds a tower of unevaluated thunks before anything is added. R’s Reduce() evaluates eagerly, so right = TRUE only changes the nesting order.

Exercises

  1. Use Reduce() to compute the product of the numbers 1 through 6 (i.e., 6 factorial). Check your answer against factorial(6).
  2. What is Reduce(intersect, list(c(1,2,3,4), c(2,3,4,5), c(3,4,5,6)))? Work through the steps by hand, then verify.
  3. Write a Reduce() call that merges three data frames by a shared "id" column. (Hint: merge is a binary function.)
  4. Explain why Reduce(/, c(120, 2, 3, 4, 5)) gives 1 with a left fold and something different with a right fold.

21.4 accumulate: keeping the intermediates

Sometimes you want every intermediate step, and only the last one comes out of Reduce(): the running total after each deposit, the growing sentence after each word, the high-water mark after each measurement. Base R handles this by adding a single argument:

Reduce(`+`, 1:5, accumulate = TRUE)
#> [1]  1  3  6 10 15

Running totals: 1, 3, 6, 10, 15. This is the scan operation (Haskell’s scanl, APL’s \). Where fold collapses a list to a single value, scan collapses it to a list of all the values the fold passed through on its way to the answer.

Reduce(max, c(3, 1, 4, 1, 5, 9, 2, 6), accumulate = TRUE)
#> [1] 3 3 4 4 5 9 9 9

A running maximum, where each value is the largest seen so far. The 1s and the 2 cannot drag the maximum back down; it can only rise or hold steady.

Reduce(paste, c("one", "two", "three", "four"), accumulate = TRUE)
#> [1] "one"                "one two"            "one two three"     
#> [4] "one two three four"

A sentence assembling itself one word at a time.

21.5 purrr::reduce() and purrr::accumulate()

The purrr package provides reduce() and accumulate() as tidyverse-flavored alternatives:

reduce(1:5, `+`)
#> [1] 15
accumulate(1:5, `+`)
#> [1]  1  3  6 10 15

Same results. The differences from base Reduce() are syntactic: .x and .f instead of positional arguments, .init instead of init, and .dir = "backward" instead of right = TRUE. The purrr versions also accept lambda-style formulas, though anonymous functions with \() are clearer.

purrr also has reduce2(), which has no base equivalent: it folds over two lists in parallel, handing an extra argument from the second list at each step:

reduce2(
  c("a", "b", "c"),
  c("-", "+"),
  \(acc, val, sep) paste0(acc, sep, val)
)
#> [1] "a-b+c"

The binary function receives three arguments: the accumulator, the current element from the first list, and the corresponding element from the second list. The second list must be one element shorter than the first (or the same length if .init is provided), because the first element of the first list seeds the accumulator.

21.6 Practical patterns

When split() or repeated API calls hand you a list of data frames, Reduce(rbind, dfs) stacks them:

dfs <- list(
  data.frame(x = 1:2, y = c("a", "b")),
  data.frame(x = 3:4, y = c("c", "d")),
  data.frame(x = 5:6, y = c("e", "f"))
)
Reduce(rbind, dfs)
#>   x y
#> 1 1 a
#> 2 2 b
#> 3 3 c
#> 4 4 d
#> 5 5 e
#> 6 6 f

Each step binds two frames and copies the growing result, so on a long list the cost is O(n2). do.call(rbind, dfs) binds all of them in one call, and list_rbind() from Section 19.4 does the same for tibbles.

Walking into a deeply nested structure one key at a time is a fold too:

nested <- list(a = list(b = list(c = 42)))
Reduce(\(x, i) x[[i]], c("a", "b", "c"), init = nested)
#> [1] 42

Each step indexes one level deeper. The fold replaces a chain of [[ calls. (purrr’s pluck() does the same thing with better error messages.)

Set operations extend to any number of sets the same way:

sets <- list(c(1,2,3,4), c(2,3,4,5), c(3,4,5,6))
Reduce(intersect, sets)
#> [1] 3 4
Reduce(union, sets)
#> [1] 1 2 3 4 5 6

And accumulate() can model any sequential process where each step depends on the previous state. A bank balance after each deposit and withdrawal:

transactions <- c(100, -20, -30, 50, -10)
accumulate(transactions, `+`)
#> [1] 100  80  50 100  90

The running balance after each transaction. For more complex state, where the accumulator needs to carry multiple fields rather than a single number, use a list as the accumulator and a function that unpacks, updates, and repacks it.

Exercises

  1. Given words <- c("R", "is", "a", "functional", "language"), use accumulate() to produce the vector c("R", "R is", "R is a", "R is a functional", "R is a functional language").
  2. Write a Reduce() call that finds the intersection of the columns present in a list of data frames. (Hint: use names() and intersect.)
  3. Use accumulate() to compute a running product of c(2, 3, 5, 7). Verify that the last element equals prod(c(2, 3, 5, 7)).

21.7 Row-wise folds with c_across()

across() (Section 19.8) applies a function down each column. Folding across the columns within one row is a different direction, and it starts with rowwise(), which tells dplyr to treat each row as a group of one:

penguins <- palmerpenguins::penguins

penguins |>
  rowwise() |>
  mutate(bill_ratio = bill_length_mm / bill_depth_mm) |>
  ungroup() |>
  head(3)
#> # A tibble: 3 × 9
#>   species island   bill_length_mm bill_depth_mm flipper_length_mm body_mass_g
#>   <fct>   <fct>             <dbl>         <dbl>             <int>       <int>
#> 1 Adelie  Torgers…           39.1          18.7               181        3750
#> 2 Adelie  Torgers…           39.5          17.4               186        3800
#> 3 Adelie  Torgers…           40.3          18                 195        3250
#> # ℹ 3 more variables: sex <fct>, year <int>, bill_ratio <dbl>

c_across() gathers the named columns of the current row into a vector, so any summary function can take it:

df <- tibble(a = 1:3, b = 4:6, c = 7:9)
df |>
  rowwise() |>
  mutate(total = sum(c_across(a:c))) |>
  ungroup()
#> # A tibble: 3 × 4
#>       a     b     c total
#>   <int> <int> <int> <int>
#> 1     1     4     7    12
#> 2     2     5     8    15
#> 3     3     6     9    18

Each row’s a, b, and c values are collected into a vector, summed, and stored in total: the same fold Reduce() does down a list, run across the columns of a row instead.

rowwise() + c_across() processes one row at a time in R, so it scales poorly. On 100,000 rows, rowSums() finishes in milliseconds because it is vectorized in C; the rowwise() version takes tens of seconds. Use c_across() when the operation is genuinely complex or when you need tidyselect helpers to pick columns. Otherwise use rowSums() or pmax().

Exercises

  1. Using rowwise() and c_across(), compute the maximum of columns a, b, and c for each row of df <- tibble(a = c(3,1,4), b = c(1,5,9), c = c(2,6,5)).
  2. Rewrite the c_across() sum example using rowSums() instead. Which is clearer? Which is faster? (Try bench::mark() on a larger data frame.)
  3. Use rowwise() and c_across(where(is.numeric)) to compute the range (max minus min) of every numeric column for each row of penguins. Why would this be hard to do without c_across()?

21.8 When to fold and when not to

Reduce() is the right tool when you have a binary operation and a list of things to combine: merging data frames, chaining set operations, collapsing nested structures. It is the wrong tool when a vectorized function already exists. sum(x) is faster and clearer than Reduce(+, x). paste(x, collapse = " ") beats Reduce(paste, x). The base R cumulative functions (cumsum, cumprod, cummax, cummin) are compiled C and will always outperform accumulate(+, x). Reach for Reduce() when your binary operation has no built-in vectorized cousin.

Reduce() also becomes awkward when the accumulator needs complex state. If your fold carries a list with multiple fields and each step updates several of them conditionally, you are writing a state machine and the fold is in the way. An explicit loop or a recursive function (Chapter 22) shows the state updates where the reader can see them.

In 1999 Graham Hutton showed that fold can express any function on finite lists. That is a universality result, not practical advice. Just because something can be written as a fold does not mean it will be readable six months later.

TipOpinion

Fold is the underused functional. Next time you write a loop that carries an accumulator variable, growing it with each pass, try Reduce() first. You might not need that loop at all.