Fold

Suppose you want to sum up an array of numbers. You write this pseudocode:

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

Later you want to multiply together an array of factors. You write this pseudocode:

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

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

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

When you step back, you 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 "".
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

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" }

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 you are iterating through an array and producing some new value, you 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

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

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 subprogram 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. 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. In parameters are read from, while out parameters are written to. Data is sent back to the caller via a return statement or expression. A language's passing mechanics dictate how parameters and return values are shared with the caller. Most languages only pass copies of the actual parameters, which means reassignment has no effect on the caller. If data is expensive to copy or is to be modified by the function, then it must be shared differently. Languages achieve this sharing in various ways. C and C++ pass a copy of data's address as a pointer. Java, JavaScript, and Ruby pass a copy of the address, too, but these references don't support address operations. C++ and Rust pass an alias that acts as a second name for the memory. 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.