Fold

Suppose we want to sum up an array of numbers. We write this pseudocode:

sum = 0
for each x in xs
  sum = sum + x

sum = 0
for each x in xs
  sum = sum + x

Later we want to multiply together an array of factors. We write this pseudocode:

product = 1
for each x in xs
  product = product * x

product = 1
for each x in xs
  product = product * x

Still later we want to concatenate together an array of strings and insert trailing linebreaks. We write this pseudocode:

text = ""
for each line in lines
  text = text + line + "\n"

text = ""
for each line in lines
  text = text + line + "\n"

When we step back, we notice that these are all the same algorithm: iterate through a collection and combine each item into the result. Since the result variable accumulates the items one at a time, it is called the accumulator. The three tasks differ in only two ways:

1. The initial value of the accumulator. For these three tasks, the initial value is 0, 1, or "", but it could be anything.
2. The operation that mixes an item into the accumulator. For these three tasks, it's addition, multiplication, or concatenation.

Algorithms with this structure follow the fold pattern. Some call it the reduce pattern, but this term suggests that the final accumulation is smaller or simpler than the original collection, which isn't necessarily the case. In fact, saying anything concrete about the final accumulation is difficult. The final result is shaped entirely by the caller's mixing operation. Visually, the fold pattern performs this operation:

The items are folded into some unknown structure, which is shown here as a cloud.

Since the fold operation has two holes, it is factored out into a higher-order function that accepts two parameters. It has this pseudocode implementation:

class Collection
  items = ...

  function fold(accumulator, mix)
    for i in 0 to items.size
      accumulator = mix(accumulator, items[i])
    return accumulator

class Collection
  items = ...

  function fold(accumulator, mix)
    for i in 0 to items.size
      accumulator = mix(accumulator, items[i])
    return accumulator

Ruby implements the fold pattern in the inject method of its Array class. The initial accumulator is passed as a normal parameter, and the mixing operation is passed as a block:

sum = xs.inject(0) { |sum, x| sum + x }
product = xs.inject(1) { |product, x| product * x }
text = lines.inject("") { |text, line| text + line + "\n" }

sum = xs.inject(0) { |sum, x| sum + x }
product = xs.inject(1) { |product, x| product * x }
text = lines.inject("") { |text, line| text + line + "\n" }

The first parameter to the block is the accumulator, and the second is the current item. The block mixes in the current item and returns the new accumulator, which will be sent along to the next iteration.

The fold operation is far more abstract than map and filter. If we have an algorithm that iterates through an array and produces some new value, we can almost certainly express it as a fold. In fact, even map and filter are special cases of fold. A map operation may be implemented with this inject call:

new_items = items.inject([]) do |new_items, item|
  new_items.push(transform(item))
end

new_items = items.inject([]) do |new_items, item|
  new_items.push(transform(item))
end

Likewise, a filter operation may be implemented with this inject call:

keepers = items.inject([]) do |keepers, item|
  if predicate(item)
    keepers.push(item)
  end
  keepers
end

keepers = items.inject([]) do |keepers, item|
  if predicate(item)
    keepers.push(item)
  end
  keepers
end

Python implements the fold operation in its reduce function. List comprehensions do not have as much expressive power as reduce. They strictly produce lists, whereas reduce can produce any kind of data.

Summary

Programmers decompose complex programs into functions. This decomposition has several benefits: each function is given a meaningful name, has a focused mission, is reusable, simplifies the calling context, and safely operates within its own scope. They can't be entirely separate from the main execution, however, as we need to send data to them and receive data from them. Data is sent to a function via parameters, which may be positional or named. They may be assigned default values. The number of a function's parameters is its arity, which may be fixed or variadic. Most languages only pass copies of the actual parameters. Data that is expensive to copy or might be updated by the callee is shared by reference. References may operate like pointers without address semantics, while others are aliases. Some languages allow multiple or overloaded definitions of a function—provided each definition has a unique signature. Parameters and return values are often plain data, but higher-order functions receive or return functions. Such functions allow algorithms to be written with procedural holes. Map, filter, and fold are three common and useful higher-order functions for iterating over collections.