How Do Fold Accumulators Work?

A fold accumulator, often simply called a "fold" or "reduce," is a higher-order function in functional programming that processes a data structure (like a list) and accumulates a final result.

It works by successively applying a combining function to each element of the collection and an accumulating value, known as the accumulator. The operation "folds" the entire data structure down into a single, summary value.

The fundamental components of a fold

A fold operation is defined by three key elements:

• The Data Structure: The collection of items to be processed, typically a list, array, or other iterable.
• The Accumulator (Initial Value): A starting value of a chosen data type. This value holds the intermediate and final result of the folding process. The accumulator's type can be different from the type of the elements in the data structure.
• The Combining Function: A function that takes two arguments: the current accumulator value and the next element from the data structure. It returns the new accumulator value, which is then used in the next step of the fold.

The process continues by passing the result of the combining function as the new accumulator for the next iteration. This repeats until all elements in the data structure have been processed.

Left fold vs. right fold

The two main types of folds are defined by the order in which they process the data structure.

Left fold (foldl or reduce)

A left fold processes the list from left to right, combining the current accumulator with the next element. The combining function's arguments are typically (accumulator, element).

Example: Summing a listConsider the list [1,2,3]open bracket 1 comma 2 comma 3 close bracket

[1,2,3]

and the + combining function, with an initial accumulator value of 0.

1. Initial state:accumulator = 0, element = 1. The combining function is +(0, 1), which returns 1.
2. Next step:accumulator = 1, element = 2. The combining function is +(1, 2), which returns 3.
3. Final step:accumulator = 3, element = 3. The combining function is +(3, 3), which returns 6.
4. Final result: 6.

The sequence of operations is (((0 + 1) + 2) + 3). The operations are performed in a left-associative manner.

Right fold (foldr)

A right fold processes the list from right to left, combining the last element with the initial value first. The combining function's arguments are typically (element, accumulator).

Example: Summing a listUsing the same list [1,2,3]open bracket 1 comma 2 comma 3 close bracket

[1,2,3]

, + function, and initial value 0:

1. The right fold works conceptually by starting at the end of the list. The structure of the operation is 1 + (2 + (3 + 0)).
2. Initial state: The fold combines the last element (3) with the initial value (0). The combining function is +(3, 0), which returns 3.
3. Next step: The second-to-last element (2) is combined with the result from the previous step. The function is +(2, 3), which returns 5.
4. Final step: The first element (1) is combined with the result. The function is +(1, 5), which returns 6.
5. Final result: 6.

Why the direction matters

For associative and commutative operations like addition and multiplication, the result of a left or right fold is the same. However, for non-commutative operations (e.g., subtraction, string concatenation, or building a new list), the direction is critical.

Example: Building a list in reverseUsing foldl with a function that prepends an element (cons):

• foldl cons [] [1, 2, 3] -> ((( [] cons 1 ) cons 2 ) cons 3) -> (3, 2, 1)

Using foldr with cons to achieve the same result as map:

• foldr cons [] [1, 2, 3] -> (1 cons (2 cons (3 cons []))) -> (1, 2, 3)

The power and versatility of folds

Folds are a foundational concept in functional programming because they are powerful enough to express many other list-processing functions, including map and filter.

Implementing map with a fold

map can be implemented with a right fold by applying a function f to each element and building a new list with the results.

map f list = foldr (\x acc -> (f x) : acc) [] list

Implementing filter with a fold

filter can be implemented with a right fold by conditionally adding elements to the accumulated list.

filter p list = foldr (\x acc -> if p x then x : acc else acc) [] list

Accumulators in imperative programming

The accumulator pattern also appears in imperative programming, though it is often less explicit. A for loop that aggregates a value is effectively an imperative fold with an accumulator.

Python for loop example

numbers = [1, 2, 3]
total = 0 # The accumulator
for n in numbers:
    total = total + n # The combining function
# final value of total is 6

Use code with caution.

This is equivalent to Python's built-in reduce function.

from functools import reduce
numbers = [1, 2, 3]
reduce(lambda acc, x: acc + x, numbers, 0)

Use code with caution.

In summary, the fold accumulator is a powerful, low-level abstraction for processing data structures. It simplifies complex operations by providing a concise, reusable pattern for iterating and accumulating a final result. Understanding folds is key to grasping the core principles of functional programming.