Fold (higher-order function)
Fold (higher-order function)
Main page
F

Fold (higher-order function)

logo
Community Hub0 subscribers
Read side by side
Fold (higher-order function)
View on Wikipedia
from Wikipedia
Comparison of
programming languages
Comparison of individual
languages

In functional programming, a fold is a higher-order function that analyzes a recursive data structure and, through use of a given combining operation, recombines the results of recursively processing its constituent parts, building up a return value. Fold is also termed as reduce, accumulate, aggregate, compress, or inject. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.

Folds are in a sense dual to unfolds, which take a seed value and apply a function corecursively to decide how to progressively construct a corecursive data structure, whereas a fold recursively breaks that structure down, replacing it with the results of applying a combining function at each node on its terminal values and the recursive results (catamorphism, versus anamorphism of unfolds).

As structural transformations

[edit]

Folds can be regarded as consistently replacing the structural components of a data structure with functions and values. Lists, for example, are built up in many functional languages from two primitives: any list is either an empty list, commonly called nil  ([]), or is constructed by prefixing an element in front of another list, creating what is called a cons  node (  Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), resulting from application of a cons function (written down as a colon (:) in Haskell). One can view a fold on lists as replacing  the nil at the end of the list with a specific value, and replacing each cons with a specific function. These replacements can be viewed as a diagram:

There's another way to perform the structural transformation in a consistent manner, with the order of the two links of each node flipped when fed into the combining function:

These pictures illustrate right and left fold of a list visually. They also highlight the fact that foldr (:) [] is the identity function on lists (a shallow copy in Lisp parlance), as replacing cons with cons and nil with nil will not change the result. The left fold diagram suggests an easy way to reverse a list, foldl (flip (:)) []. Note that the parameters to cons must be flipped, because the element to add is now the right hand parameter of the combining function. Another easy result to see from this vantage-point is to write the higher-order map function in terms of foldr, by composing the function to act on the elements with cons, as: 

 map f = foldr ((:) . f) []

where the period (.) is an operator denoting function composition.

This way of looking at things provides a simple route to designing fold-like functions on other algebraic data types and structures, like various sorts of trees. One writes a function which recursively replaces the constructors of the datatype with provided functions, and any constant values of the type with provided values. Such a function is generally referred to as a catamorphism.

On lists

[edit]

The folding of the list [1,2,3,4,5] with the addition operator would result in 15, the sum of the elements of the list [1,2,3,4,5]. To a rough approximation, one can think of this fold as replacing the commas in the list with the + operation, giving 1 + 2 + 3 + 4 + 5.[1]

In the example above, + is an associative operation, so the final result will be the same regardless of parenthesization, although the specific way in which it is calculated will be different. In the general case of non-associative binary functions, the order in which the elements are combined may influence the final result's value. On lists, there are two obvious ways to carry this out: either by combining the first element with the result of recursively combining the rest (called a right fold), or by combining the result of recursively combining all elements but the last one, with the last element (called a left fold). This corresponds to a binary operator being either right-associative or left-associative, in Haskell's or Prolog's terminology. With a right fold, the sum would be parenthesized as 1 + (2 + (3 + (4 + 5))), whereas with a left fold it would be parenthesized as (((1 + 2) + 3) + 4) + 5.

In practice, it is convenient and natural to have an initial value which in the case of a right fold is used when one reaches the end of the list, and in the case of a left fold is what is initially combined with the first element of the list. In the example above, the value 0 (the additive identity) would be chosen as an initial value, giving 1 + (2 + (3 + (4 + (5 + 0)))) for the right fold, and ((((0 + 1) + 2) + 3) + 4) + 5 for the left fold. For multiplication, an initial choice of 0 wouldn't work: 0 * 1 * 2 * 3 * 4 * 5 = 0. The identity element for multiplication is 1. This would give us the outcome 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.

Linear vs. tree-like folds

[edit]

The use of an initial value is necessary when the combining function f  is asymmetrical in its types (e.g. a → b → b), i.e. when the type of its result is different from the type of the list's elements. Then an initial value must be used, with the same type as that of f 's result, for a linear chain of applications to be possible. Whether it will be left- or right-oriented will be determined by the types expected of its arguments by the combining function. If it is the second argument that must be of the same type as the result, then f  could be seen as a binary operation that associates on the right, and vice versa.

When the function is a magma, i.e. symmetrical in its types (a → a → a), and the result type is the same as the list elements' type, the parentheses may be placed in arbitrary fashion thus creating a binary tree of nested sub-expressions, e.g., ((1 + 2) + (3 + 4)) + 5. If the binary operation f  is associative this value will be well-defined, i.e., same for any parenthesization, although the operational details of how it is calculated will be different. This can have significant impact on efficiency if f  is non-strict.

Whereas linear folds are node-oriented and operate in a consistent manner for each node of a list, tree-like folds are whole-list oriented and operate in a consistent manner across groups of nodes.

Special folds for non-empty lists

[edit]

One often wants to choose the identity element of the operation f as the initial value z. When no initial value seems appropriate, for example, when one wants to fold the function which computes the maximum of its two parameters over a non-empty list to get the maximum element of the list, there are variants of foldr and foldl which use the last and first element of the list respectively as the initial value. In Haskell and several other languages, these are called foldr1 and foldl1, the 1 making reference to the automatic provision of an initial element, and the fact that the lists they are applied to must have at least one element.

These folds use type-symmetrical binary operation: the types of both its arguments, and its result, must be the same. Richard Bird in his 2010 book proposes[2] "a general fold function on non-empty lists" foldrn which transforms its last element, by applying an additional argument function to it, into a value of the result type before starting the folding itself, and is thus able to use type-asymmetrical binary operation like the regular foldr to produce a result of type different from the list's elements type.

Implementation

[edit]

Linear folds

[edit]

Using Haskell as an example, foldl and foldr can be formulated in a few equations. 

 foldl :: (b -> a -> b) -> b -> [a] -> b
 foldl f z []     = z
 foldl f z (x:xs) = foldl f (f z x) xs

If the list is empty, the result is the initial value. If not, fold the tail of the list using as new initial value the result of applying f to the old initial value and the first element. 

 foldr :: (a -> b -> b) -> b -> [a] -> b
 foldr f z []     = z
 foldr f z (x:xs) = f x (foldr f z xs)

If the list is empty, the result is the initial value z. If not, apply f to the first element and the result of folding the rest.

Tree-like folds

[edit]

Lists can be folded over in a tree-like fashion, both for finite and for indefinitely defined lists: 

foldt f z []     = z
foldt f z [x]    = f x z
foldt f z xs     = foldt f z (pairs f xs)
 
foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
 
pairs f (x:y:t)  = f x y : pairs f t
pairs _ t        = t

In the case of foldi function, to avoid its runaway evaluation on indefinitely defined lists the function f must not always demand its second argument's value, at least not all of it, or not immediately (see example below).

Folds for non-empty lists

[edit]
foldl1 f [x]      = x
foldl1 f (x:y:xs) = foldl1 f (f x y : xs)

foldr1 f [x]      = x
foldr1 f (x:xs)   = f x (foldr1 f xs)

foldt1 f [x]      = x
foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs)
 
foldi1 f [x]      = x
foldi1 f (x:xs)   = f x (foldi1 f (pairs f xs))

Evaluation order considerations

[edit]

In the presence of lazy, or non-strict evaluation, foldr will immediately return the application of f to the head of the list and the recursive case of folding over the rest of the list. Thus, if f is able to produce some part of its result without reference to the recursive case on its "right" i.e., in its second argument, and the rest of the result is never demanded, then the recursion will stop (e.g., head == foldr (\a b->a) (error "empty list")). This allows right folds to operate on infinite lists. By contrast, foldl will immediately call itself with new parameters until it reaches the end of the list. This tail recursion can be efficiently compiled as a loop, but can't deal with infinite lists at all — it will recurse forever in an infinite loop.

Having reached the end of the list, an expression is in effect built by foldl of nested left-deepening f-applications, which is then presented to the caller to be evaluated. Were the function f to refer to its second argument first here, and be able to produce some part of its result without reference to the recursive case (here, on its left i.e., in its first argument), then the recursion would stop. This means that while foldr recurses on the right, it allows for a lazy combining function to inspect list's elements from the left; and conversely, while foldl recurses on the left, it allows for a lazy combining function to inspect list's elements from the right, if it so chooses (e.g., last == foldl (\a b->b) (error "empty list")).

Reversing a list is also tail-recursive (it can be implemented using rev = foldl (\ys x -> x : ys) []). On finite lists, that means that left-fold and reverse can be composed to perform a right fold in a tail-recursive way (cf.  1+>(2+>(3+>0)) == ((0<+3)<+2)<+1), with a modification to the function f so it reverses the order of its arguments (i.e., foldr f z == foldl (flip f) z . foldl (flip (:)) []), tail-recursively building a representation of expression that right-fold would build. The extraneous intermediate list structure can be eliminated with the continuation-passing style technique, foldr f z xs == foldl (\k x-> k . f x) id xs z; similarly, foldl f z xs == foldr (\x k-> k . flip f x) id xs z ( flip is only needed in languages like Haskell with its flipped order of arguments to the combining function of foldl unlike e.g., in Scheme where the same order of arguments is used for combining functions to both foldl and foldr).

Another technical point is that, in the case of left folds using lazy evaluation, the new initial parameter is not being evaluated before the recursive call is made. This can lead to stack overflows when one reaches the end of the list and tries to evaluate the resulting potentially gigantic expression. For this reason, such languages often provide a stricter variant of left folding which forces the evaluation of the initial parameter before making the recursive call. In Haskell this is the foldl' (note the apostrophe, pronounced 'prime') function in the Data.List library (one needs to be aware of the fact though that forcing a value built with a lazy data constructor won't force its constituents automatically by itself). Combined with tail recursion, such folds approach the efficiency of loops, ensuring constant space operation, when lazy evaluation of the final result is impossible or undesirable.

Examples

[edit]

Using a Haskell interpreter, the structural transformations which fold functions perform can be illustrated by constructing a string: 

λ> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"
 
λ> foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"
 
λ> foldt (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)"
 
λ> foldi (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"

Infinite tree-like folding is demonstrated e.g., in recursive primes production by unbounded sieve of Eratosthenes in Haskell: 

primes = 2 : _Y ((3 :) . minus [5,7..] . foldi (\(x:xs) ys -> x : union xs ys) [] 
                       . map (\p-> [p*p, p*p+2*p..]))
_Y g = g (_Y g)     -- = g . g . g . g . ...

where the function union operates on ordered lists in a local manner to efficiently produce their set union, and minus their set difference.

A finite prefix of primes is concisely defined as a folding of set difference operation over the lists of enumerated multiples of integers, as 

primesTo n = foldl1 minus [[2*x,3*x..n] | x <- [1..n]]

For finite lists, e.g., merge sort (and its duplicates-removing variety, nubsort) could be easily defined using tree-like folding as 

mergesort xs = foldt merge [] [[x] | x <- xs]
nubsort   xs = foldt union [] [[x] | x <- xs]

with the function merge a duplicates-preserving variant of union.

Functions head and last could have been defined through folding as 

head = foldr (\x r -> x) (error "head: Empty list")
last = foldl (\a x -> x) (error "last: Empty list")

In various languages

[edit]
Language Left fold Right fold Left fold without initial value Right fold without initial value Unfold Notes
APL func⍨/⌽initval,vector func/vector,initval func⍨/⌽vector func/vector
C# 3.0 ienum.Aggregate(initval, func) ienum.Reverse().Aggregate(initval, func) ienum.Aggregate(func) ienum.Reverse().Aggregate(func) Aggregate is an extension method
ienum is an IEnumerable<T>
Similarly in all .NET languages
C++ std::accumulate(begin, end, initval, func) std::accumulate(rbegin, rend, initval, func) in header <numeric>
begin, end, rbegin, rend are iterators
func can be a function pointer or a function object
C++17 (initval op ... op pack) (pack op ... op initval) (... op pack) (pack op ...) Fold expression (only for variadic templates): op is a binary operator (both ops must be the same, e.g., (std::cout << ... << args)), pack is an unexpanded parameter pack.
C++23 std::ranges::fold_left(range, initval, func) std::ranges::fold_right(range, initval, func) std::ranges::fold_left_first(range, func) std::ranges::fold_right_last(range, func) Both std::ranges::fold_left_first and std::ranges::fold_right_last return std::optional considering the emptiness of range.
CFML obj.reduce(func, initial) obj.reduce(func) Where func receives as arguments the result of the previous operation (or the initial value on the first iteration); the current item; the current item's index or key; and a reference to the obj
Clojure (reduce func initval list) (reduce func initval (reverse list)) (reduce func list) (reduce func (reverse list)) See also clojure.core.reducers/fold
Common Lisp (reduce func list :initial-value initval) (reduce func list :from-end t :initial-value initval) (reduce func list) (reduce func list :from-end t)
D reduce!func(initval, list) reduce!func(initval, list.reverse) reduce!func(list) reduce!func(list.reverse) in module std.algorithm
Elixir List.foldl(list, acc, fun) List.foldr(list, acc, fun) See documentation for example usage
Elm List.foldl(Fun, Accumulator, List) List.foldr(Fun, Accumulator, List) See also List API [1]
Erlang lists:foldl(Fun, Accumulator, List) lists:foldr(Fun, Accumulator, List)
F# List.fold func initval list
Seq.fold func initval sequence 		List.foldBack func list initval List.reduce func list
Seq.reduce func sequence 		List.reduceBack func list Seq.unfold func initval
Gleam list.fold(list, initial, func)
yielder.fold(yielder, initial, func) 		list.fold_right(list, initial, func) list.reduce(list, func)
yielder.reduce(yielder, func) 		yielder.unfold(initial, func)
Gosu Iterable.fold(f(agg, e))
Iterable.reduce(init, f(agg, e))
Iterable.partition(f(e)) 		All are extension methods on Java's Iterable interface, arrays are also supported
Groovy list.inject(initval, func) list.reverse().inject(initval, func) list.inject(func) list.reverse().inject(func)
Haskell foldl func initval list foldr func initval list foldl1 func list foldr1 func list unfoldr func initval For foldl, the folding function takes arguments in the opposite order as that for foldr.
Haxe Lambda.fold(iterable, func, initval)
J verb~/|. initval,array verb/ array,initval verb~/|. array verb/ array u/y applies the dyad u between the items of y. "J Dictionary: Insert"
Java 8+ stream.reduce(initval, func) stream.reduce(func)
JavaScript 1.8
ECMAScript 5 		array.reduce(func, initval)[3] array.reduceRight(func,initVal) array.reduce(func) array.reduceRight(func) The reducer main arguments are accumulator and current value, and we can use optional arguments like index and array. array.reduceRight((acc, value, idx, array)=>{}, initvalue)
Julia foldl(op, itr; [init]) foldr(op, itr; [init]) foldl(op, itr) foldr(op, itr)
Kotlin Iterable.fold(initval, func) Iterable.foldRight(initval, func) Iterable.reduce(func) Iterable.reduceRight(func) Other collections also support fold[4] and reduce.[5] There is also Result.fold(onSuccess, onFailure),[6] which reduces a Result<T> (either success or failure) to the return type of onSuccess and onFailure.
LFE (lists:foldl func accum list) (lists:foldr func accum list)
Logtalk fold_left(Closure, Initial, List, Result) fold_right(Closure, Initial, List, Result) Meta-predicates provided by the meta standard library object. The abbreviations foldl and foldr may also be used.
Maple foldl(func, initval, sequence) foldr(func, initval, sequence) foldl(func, sequence) foldr(func, sequence)
Mathematica Fold[func, initval, list] Fold[func, initval, Reverse[list]] Fold[func, list] Fold[func, Reverse[list]] NestWhileList[func,, initval, predicate] Fold without an initial value is supported in versions 10.0 and higher.
MATLAB fold(@func, list, defaultVal) fold(@func, flip(list), defaultVal) fold(@func, list) fold(@func, flip(list)) Requires Symbolic Math Toolbox, supported from R2016b.
Maxima lreduce(func, list, initval) rreduce(func, list, initval) lreduce(func, list) rreduce(func, list)
OCaml List.fold_left func initval list
Array.fold_left func initval array 		List.fold_right func list initval
Array.fold_right func array initval
Oz {FoldL List Func InitVal} {FoldR List Func InitVal}
PARI/GP fold( f, A )
Perl reduce block initval, list reduce block list in List::Util module
PHP array_reduce(array, func, initval) array_reduce(array_reverse(array), func, initval) array_reduce(array, func) array_reduce(array_reverse(array), func) When initval is not supplied, NULL is used, so this is not a true foldl1. Before PHP 5.3, initval can only be integer. func is a callback Archived 2020-11-28 at the Wayback Machine. Try array_reduce online.
Python 2.x reduce(func, list, initval) reduce(lambda x, y: func(y, x), reversed(list), initval) reduce(func, list) reduce(lambda x, y: func(y, x), reversed(list))
Python 3.x functools.reduce(func, list, initval) functools.reduce(lambda x, y: func(y, x), reversed(list), initval) functools.reduce(func, list) functools.reduce(lambda x, y: func(y, x), reversed(list)) In module functools.[7]
R Reduce(func, list, initval) Reduce(func, list, initval, right=TRUE) Reduce(func, list) Reduce(func, list, right=TRUE) R supports right folding and left or right folding with or without an initial value through the right and init arguments to the Reduce function.
Racket (foldl func initval list) (foldr func initval list)
Ruby enum.inject(initval, &block)
enum.reduce(initval, &block) 		enum.reverse_each.inject(initval, &block)
enum.reverse_each.reduce(initval, &block) 		enum.inject(&block)
enum.reduce(&block) 		enum.reverse_each.inject(&block)
enum.reverse_each.reduce(&block) 		In Ruby 1.8.7+, can also pass a symbol representing a function instead of a block.
enum is an Enumeration
Please notice that these implementations of right folds are wrong for non-commutative &block (also initial value is put on wrong side).
Rust iterator.fold(initval, func) iterator.rev().fold(initval, func) iterator.reduce(func) iterator.rev().reduce(func) iterator.rev() requires iterator to be a DoubleEndedIterator.[8]
Scala list.foldLeft(initval)(func)
(initval /: list)(func) 		list.foldRight(initval)(func)
(list :\ initval)(func) 		list.reduceLeft(func) list.reduceRight(func) Scala's symbolic fold syntax was intended to resemble the left- or right-leaning tree commonly used to explain the fold operation,[9] but has since been reinterpreted as an illustration of a toppling domino.[10] The colon comes from a general Scala syntax mechanism whereby the apparent infix operator is invoked as a method on the left operand with the right operand passed as an argument, or vice versa if the operator's last character is a colon, here applied symmetrically.

Scala also features the tree-like folds using the method list.fold(z)(op).[11]

Scheme R6RS (fold-left func initval list)
(vector-fold func initval vector) 		(fold-right func initval list)
(vector-fold-right func initval vector) 		(reduce-left func defaultval list) (reduce-right func defaultval list) (unfold p f g seed [tail-gen])
unfold-right p f g seed [tail]
(vector-unfold f length initial-seed ···)
(vector-unfold-right f length initial-seed ···) 		srfi/1 srfi/43
Smalltalk aCollection inject: aValue into: aBlock aCollection reduce: aBlock ANSI Smalltalk doesn't define #reduce: but many implementations do.
Standard ML foldl func initval list
Array.foldl func initval array 		foldr func initval list
Array.foldr func initval array 		The supplied function takes its arguments in a tuple. For foldl, the folding function takes arguments in the same order as for foldr.
Swift array.reduce(initval, func)
reduce(sequence, initval, func) 		array.reverse().reduce(initval, func)
XPath fold-left($input, $zero, $action)
array:fold-left($input, $zero, $action) 		fold-right($input, $zero, $action)
array:fold-right($input, $zero, $action) 		Two functions exist for each case because XPath offers sequences for unstructured and arrays for structured data.
Xtend iterable.fold(initval,[func]) iterable.reduce[func]

Universality

[edit]

Fold is a polymorphic function. For any g having a definition 

 g [] = v
 g (x:xs) = f x (g xs)

then g can be expressed as[12] 

 g = foldr f v

Also, in a lazy language with infinite lists, a fixed point combinator can be implemented via fold,[13] proving that iterations can be reduced to folds: 

 y f = foldr (\_ -> f) undefined (repeat undefined)

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Fold (higher-order function)

View on Grokipedia
from Grokipedia
In functional programming, a fold is a higher-order function that takes a binary combining operation, an initial accumulator value, and a data structure—most commonly a list—and iteratively applies the operation to each element, accumulating a result that reduces the entire structure to a single value.[1] This process encapsulates a fundamental pattern of recursion, enabling concise and reusable implementations of operations like summation, product, or concatenation without explicit loops or mutable state.[1] Folds promote declarative code by abstracting away the details of traversal and combination, making them a cornerstone of functional paradigms in languages such as Haskell, Lisp, and Scala.[1] Folds come in two primary variants distinguished by their evaluation order: fold-right (foldr), which processes the data structure from right to left by recursively applying the combining function to the tail before the head, and fold-left (foldl), which processes from left to right using an accumulator to avoid deep recursion in strict languages.[1] For example, in Haskell, foldr (+) 0 [1,2,3] yields 6 by computing 1 + (2 + (3 + 0)), while foldl (+) 0 [1,2,3] computes ((0 + 1) + 2) + 3, both producing the same result for associative operations but differing in associativity handling and stack usage.[1] These variants extend beyond lists to trees, graphs, and other recursive structures, supporting generalized reductions like mapping or filtering when composed with other functions.[1] The concept of fold traces its origins to recursion theory in the 1950s, with early formalization in Stephen Kleene's work on recursive functions, but its practical adoption in programming began with Kenneth Iverson's APL language in 1962, where the reduction operator / implemented a left-fold for array aggregation, such as summing vectors with +/x.[1] John Backus further advanced it in his 1978 Turing Award lecture, introducing the "insertion" functional form /f in the FP language as a primitive for composing sequences hierarchically, exemplified by /+ for summation, to liberate programming from imperative styles.[2] By the 1990s, fold was systematized in modern functional languages, with Grant Malcolm's 1990 work proving its universality—demonstrating that any list-processing function satisfying certain conditions equals a fold—solidifying its expressive power for deriving operations like map and reverse.[1] Folds are notable for their universality and expressiveness, allowing a wide range of algorithms to be defined succinctly; for instance, the map function can be expressed as foldr (\x xs -> f x : xs) [], highlighting how folds capture structural transformations without pattern-specific code.[1] In practice, they underpin efficient implementations in libraries (e.g., Haskell's Data.List) and parallel computing, where associative folds enable divide-and-conquer strategies like in MapReduce frameworks.[1] Their emphasis on immutability and composition has influenced broader software design, reducing bugs in concurrent and data-intensive applications.[2]

Fundamentals

Definition

In functional programming, a fold is a higher-order function that reduces a data structure, such as a list, to a single value by iteratively applying a binary operation to accumulate results. It takes three arguments: a binary combining function ff, an initial accumulator value zz, and the data structure xsxs. The operation proceeds by successively applying ff to elements of xsxs and the current accumulator, starting from zz, until the entire structure is processed, yielding a final value.[1] The general signature is \fold(f,z,xs)\fold(f, z, xs), where ff combines an element from the structure with the accumulator (of type α→β→β\alpha \to \beta \to \beta), zz provides the base case (of type β\beta), and xsxs is the input structure (e.g., a list of type [α][\alpha]), producing an output of type β\beta. This formulation encapsulates a pattern of recursion, where the base case (an empty structure) returns zz, and non-empty cases apply ff to the head element and the fold of the tail. Folds rely on higher-order functions, which accept other functions as parameters, and recursion, though the details of recursive implementation are abstracted away.[1] Unlike map, which applies a function to each element of a structure while preserving its size and shape (e.g., transforming a list into another list of equal length), fold generalizes associative reductions such as summation (\fold(+)0xs\fold(+) 0 xs) or concatenation (\fold(:)[]xs\fold(:) [] xs), collapsing the structure into a scalar or simpler form without retaining the original dimensionality.[1]

As Structural Transformations

Fold functions serve as catamorphisms, which recursively apply a binary operation to deconstruct algebraic data types—such as lists or trees—into a single value, effectively inverting the structure-building process of anamorphisms.[3] Algebraically, folds respect monoid structures, where the combining function is associative and the initial accumulator serves as the identity, governed by the recursive equation
fold(f,z,\cons(x,xs))=f(x,fold(f,z,xs)) \text{fold}(f, z, \cons(x, xs)) = f(x, \text{fold}(f, z, xs))
with the empty case yielding the identity fold(f,z,\nil)=z\text{fold}(f, z, \nil) = z.[4] This approach extends to other recursive data types beyond lists; for instance, on binary trees, a fold recursively combines node values with those of subtrees, systematically reducing the entire structure while preserving its algebraic form.[3] Folds exhibit totality, remaining well-defined across all inputs—including vacuous or empty structures—due to the explicit initial value that handles base cases without divergence.[4] In contemporary category theory, folds are formalized as unique homomorphisms from the initial algebra of a base functor to any target algebra, a framework that gained traction in functional programming research after the 1990s to support rigorous analysis of recursive patterns.[4]

Folds on Lists

Linear Folds

Linear folds, also known as sequential or catamorphic folds on lists, process the elements of a linear data structure in a fixed order, applying a binary combining function cumulatively to reduce the list to a single value starting from an initial accumulator. There are two primary variants: the left fold (foldl), which associates operations from left to right, and the right fold (foldr), which associates from right to left. The right fold is non-strict, allowing lazy evaluation in languages like Haskell, whereas the left fold typically requires strict evaluation to avoid space inefficiencies.[5][6] The mathematical formulation for a left fold on a list [x1,x2,…,xn][x_1, x_2, \dots, x_n] with combining function ff and initial value zz is:
foldl(f,z,[x1,x2,…,xn])=(…((z f x1) f x2)…f xn) \text{foldl}(f, z, [x_1, x_2, \dots, x_n]) = (\dots((z \, f \, x_1) \, f \, x_2) \dots f \, x_n)
In contrast, the right fold is:
foldr(f,z,[x1,x2,…,xn])=(x1 f (x2 f …(xn f z)… )) \text{foldr}(f, z, [x_1, x_2, \dots, x_n]) = (x_1 \, f \, (x_2 \, f \, \dots (x_n \, f \, z) \dots ))
These expressions highlight the associative grouping: left folds build nested applications from the inside out starting at the accumulator, while right folds nest from the end of the list inward.[6][5] Key differences arise in evaluation strategy and resource usage. The left fold consumes O(1) stack space in strict implementations but can accumulate O(n) space in lazy settings through unevaluated thunks, potentially leading to space leaks; a strict variant like foldl' forces evaluation at each step to maintain constant space. The right fold, being lazy and non-strict, builds a right-associated spine of thunks that uses O(n) space but enables streaming and parallel evaluation, as independent subcomputations can be distributed across processors for associative operations.[5][7] Common use cases include computing sums or products on flat lists, where the operation is associative, ensuring foldl and foldr yield identical results; for example, summing [1,2,3] with addition and initial 0 produces 6 in both cases. For non-associative operations, the choice determines the grouping, such as in string concatenation where left folds may reverse order inefficiently without strictness, while right folds preserve it naturally. Equivalence between left and right folds requires the combining function to be associative (i.e., $ (x , f , y) , f , z = x , f , (y , f , z) $) and often an identity element for the initial value.[6][5]

Tree-like Folds

Tree-like folds extend the fold operation to process lists in a balanced, recursive manner, dividing the input into halves and folding the sublists before combining their results with the binary operation ff, which must be associative to ensure correctness independent of the grouping. This approach constructs a tree of computations, contrasting with linear folds that scan sequentially from one end. The initial value zz must serve as a right identity for ff (i.e., for all xx, f x z=xf\, x\, z = x), as is standard for such reductions over monoids; under this assumption, the base case for a single element returns xx (equivalent to f x zf\, x\, z). The concept is detailed in functional algorithm design, where such folds enable efficient processing of large or infinite structures by leveraging associativity. The algorithm recursively splits the list at its midpoint: for a non-empty list xsxs, compute the left half leftleft and right half rightright, then apply tree_fold(f,z,left)tree\_fold(f, z, left) and tree_fold(f,z,right)tree\_fold(f, z, right) in parallel, and combine as f(tree_fold(f,z,left),tree_fold(f,z,right))f(tree\_fold(f, z, left), tree\_fold(f, z, right)), with base cases tree_fold(f,z,[])=ztree\_fold(f, z, []) = z and tree_fold(f,z,[x])=xtree\_fold(f, z, [x]) = x (adjusting for odd lengths by placing the middle element appropriately, e.g., combining it with one subtree). This yields a computation tree of depth O(log⁡n)O(\log n), compared to the O(n)O(n) depth of linear folds. For non-empty inputs, zz is effectively absorbed due to the identity assumption, ensuring the result matches the linear fold. Key advantages include reduced risk of stack overflow from deep recursion, as the balanced structure limits call stack usage to logarithmic depth, and inherent support for parallelism by allowing independent computation of subtrees on multi-core processors, GPUs, or distributed systems. In parallel settings, the tree structure facilitates divide-and-conquer strategies, where subfolds execute concurrently before a final reduction, achieving linear speedups for associative operations without synchronization overhead.[8][9] Modern implementations appear in parallel functional libraries from the 2010s, such as Haskell's par-monad and evaluation strategies, which use tree-like reductions for tasks like parallel scans or aggregations over large datasets, enabling deterministic parallelism in pure functional code.[10]

Special Folds for Non-empty Lists

Special folds for non-empty lists, such as foldl1 and foldr1, are variants of the standard linear fold operations that do not require an explicit initial accumulator value, instead using the first or last element of the input as the starting point.[11] These functions assume the input structure is non-empty and process elements associatively from left to right (foldl1) or right to left (foldr1). For a non-empty list [x1, x2, ..., xn], foldl1 f [x1, x2, ..., xn] computes (...((x1 fx2)fx3) ...f xn), where f is a binary function.[11] Similarly, foldr1 f [x1, x2, ..., xn] yields x1 f(x2f(...f xn)... ).[11] The type signature in Haskell, for instance, is foldl1 :: Foldable t => (a -> a -> a) -> t a -> a, applicable to lists and other foldable structures like tuples or trees.[11] These special folds relate directly to their linear counterparts by implicitly deriving the initial accumulator from the input itself, making them equivalent to foldl f (head xs) (tail xs) for foldl1 in the case of lists.[12] Unlike general linear folds, which handle empty inputs via the provided accumulator, foldl1 and foldr1 raise runtime exceptions—such as "empty list"—when applied to empty structures, enforcing the non-empty precondition at execution time.[11] This design simplifies the function signature by omitting the accumulator parameter, streamlining usage in contexts where emptiness is precluded. The primary advantage of these folds lies in their conciseness for scenarios with guaranteed non-empty inputs, such as data pipelines or intermediate results in functional compositions, where specifying an identity element would be redundant or unavailable.[13] For operations without a natural identity, like computing the product of numbers, foldl1 (*) directly yields the result without needing a multiplicative identity of 1.[14] However, this comes at the cost of partiality: applying them to potentially empty inputs risks undefined behavior and exceptions, potentially complicating error handling in broader applications.[11] Common examples include finding the maximum element in a list via foldl1 max, which leverages the comparison function without an initial value, as the first element serves as the baseline.[11] Another is summing a non-empty sequence with foldr1 (+) [1..4], equaling 10, demonstrating right-associative evaluation suitable for lazy contexts.[11] These folds prove particularly useful for reductions like greatest common divisors or string concatenations where associativity holds and the input size is known to be at least one. In modern functional languages post-2000, safety patterns mitigate the risks of these partial functions, such as Haskell's Data.List.NonEmpty type, which encodes non-emptiness at the type level and provides total versions like head :: NonEmpty a -> a without runtime checks.[15] This approach, integrated into the base library since 2016 (with GHC 8.0), allows composing folds over NonEmpty structures—e.g., foldr1 on NonEmpty lists—to avoid exceptions entirely while preserving the simplified signature.[15]

Implementation

Linear Fold Algorithms

Linear fold algorithms implement the standard left and right folds over linear data structures like lists by sequentially applying a binary combining function to an accumulator and each element. These algorithms differ in their evaluation direction and recursion strategy, with right folds typically using explicit recursion and left folds benefiting from iterative accumulation to achieve constant space usage.[5] The right fold, often denoted as foldr, processes the list from the end to the beginning through recursion, building the result by applying the function to the head element and the folded tail. Its pseudocode is as follows: 
foldr f z [] = z
foldr f z (x : xs) = f x (foldr f z xs)
This recursive structure replaces the list's cons cells with function applications, enabling lazy evaluation where the accumulator is only computed as needed. In terms of space complexity, foldr requires O(n) stack space in a strict context due to the recursive calls, but lazy evaluation in functional languages like Haskell mitigates this by allowing O(1) space for operations that short-circuit or build lazy structures, such as list construction.[11][5] In contrast, the left fold, denoted as foldl, accumulates from the beginning of the list and is naturally suited to an iterative implementation, avoiding deep recursion. A recursive version appears tail-recursive: 
foldl f z [] = z
foldl f z (x : xs) = foldl f (f z x) xs
However, due to laziness, this builds a chain of O(n) unevaluated thunks in the accumulator, leading to O(n) space usage and potential stack overflows on large inputs. To optimize, an iterative loop version in pseudocode (imperative style for clarity in non-functional contexts) initializes the accumulator to the zero value and updates it sequentially: 
function foldl_iter(f, z, xs):
    acc = z
    for each x in xs:
        acc = f(acc, x)
    return acc
This loop runs in O(1) space, processing elements left-to-right without recursion. For functional settings, a strict variant foldl' forces evaluation of the accumulator at each step (e.g., using sequencing to reach weak head normal form), ensuring tail recursion and constant O(1) space even under laziness, which is essential for strict reductions like summation on finite lists.[11][5]

Tree-like Fold Algorithms

Tree-like fold algorithms employ a recursive divide-and-conquer strategy to process lists in a balanced, tree-structured manner, enabling efficient parallelization when the combining function ff is associative. This approach contrasts with linear folds by constructing an implicit binary tree over the input list, where sublists are recursively folded and results combined at each level, achieving logarithmic depth suitable for concurrent execution.[16] The core pseudocode for a tree-like fold can be expressed recursively as follows: 
function tree_fold(f, z, xs):
    if xs is empty:
        return z
    if length(xs) == 1:
        return f(z, head(xs))
    else:
        let left = first half of xs
        let right = second half of xs
        let left_res = tree_fold(f, z, left)
        let right_res = tree_fold(f, z, right)
        return f(left_res, right_res)
This formulation assumes that the initial value z is a neutral element for f (i.e., f z x = x and f x z = x), which is common for parallel reductions like summation but not general for arbitrary accumulators. For odd-length lists, the split typically assigns the extra element to one subtree (e.g., the right), ensuring complete coverage without loss; alternatively, a single-element base case handles the remainder explicitly. This recursion requires ff to be associative to guarantee correctness regardless of bracketing, as non-associative operations may yield varying results across unbalanced splits. The sequential time complexity remains O(n)O(n) due to visiting each element once, while the recursion depth (space and potential parallel span) is O(log⁡n)O(\log n), making it stack-efficient compared to linear right-folds.[16] In parallel variants, the recursive calls on sublists can be executed concurrently by spawning threads or tasks for each subtree, followed by a join to combine results via ff. This yields a parallel span of O(log⁡n)O(\log n) with sufficient processors, enabling work-efficient parallelism where total work is still O(n)O(n). Implementations often include a sequential cutoff for small sublists (e.g., length below a threshold) to avoid recursion overhead.[16] On 2020s hardware with deep cache hierarchies and multi-core processors, pure recursive tree folds can suffer from poor locality due to scattered memory access in deep recursion; to mitigate this, modern implementations incorporate chunking at the leaves, where base cases process small sequential chunks (e.g., 32–1024 elements) iteratively before entering the tree reduction phase. This reduces effective depth, minimizes thread divergence, and enhances cache utilization by coalescing accesses within chunks, often boosting throughput by 2–3× on GPUs while maintaining the O(log⁡n)O(\log n) span.[17]

Handling Evaluation Order

In strict evaluation regimes, fold operations require the immediate computation of their arguments before applying the combining function, which guarantees prompt results but can lead to stack overflows in deeply recursive calls unless implemented tail-recursively. A canonical example is the strict left fold, such as foldl', which evaluates the accumulator at each iteration to prevent the accumulation of suspended computations, thereby avoiding space leaks while sacrificing the ability to benefit from partial evaluation in large or infinite structures.[11] This approach is particularly useful in performance-critical reductions where full materialization of intermediate results is acceptable.[18] Conversely, lazy evaluation in foldr defers computation by constructing a spine of thunks, allowing the function to process infinite lists effectively if the consumer only demands a finite portion, as evaluation proceeds from the right and enables short-circuiting. However, this thunk-building can cause space leaks when unevaluated expressions retain references to the entire structure, delaying garbage collection and inflating memory usage until forced evaluation occurs.[19] In linear folds, this laziness supports modular composition but requires careful management to mitigate leaks, whereas tree-like folds may distribute thunks more evenly for balanced demand-driven computation.[20] Key considerations for evaluation order include the associativity of the combining function f: associative operations permit reordering of applications for optimizations like deforestation or parallel execution without semantic changes, but non-associative f demands preservation of the fold direction to maintain correctness. In parallel folds within multi-threaded settings, non-associative f can yield non-deterministic outcomes due to unpredictable interleaving of evaluations across threads, a challenge addressed in 2010s research on parallel functional languages through requirements for associativity in reduction operations.[21] For debugging in lazy systems, profiling tools that track thunk accumulation and memory retention are essential to identify and resolve space leaks, often by inserting strictness annotations or restructuring the fold.[20]

Examples and Applications

Conceptual Examples

One common conceptual illustration of the fold operation is computing the sum of a list of numbers. Consider the list [1, 2, 3] and a right fold using addition with an initial accumulator value of 0. The process begins by associating the operation from the right: 1 is combined with the fold of the remaining list [2, 3], which itself is 2 combined with the fold of [3], which is 3 combined with 0, yielding 3; then 2 + 3 = 5; finally, 1 + 5 = 6. Thus, the overall result is 6. Another example is reversing a list, which demonstrates fold's ability to reconstruct structures. For the list [1, 2, 3], a left fold can be used with a cons-like operation (prepending elements) and an empty list as the initial value. Starting from the left, the empty list is prepended with 1 to get [1]; then 2 is prepended to that, yielding [2, 1]; finally, 3 is prepended, resulting in [3, 2, 1]. This backwards building highlights how folds can invert order through iterative accumulation. Folds also compute the length of a list by incrementing an accumulator for each element. For [1, 2, 3], a left fold starts with an initial value of 0 and ignores each element while adding 1 to the accumulator: after the first element, the accumulator is 1; after the second, 2; after the third, 3. This abstraction treats the list as a counter, focusing on cardinality rather than content. Beyond numerics, folds handle non-numeric reductions like concatenating words into a sentence. For a list ["the ", "quick ", "brown"], a right fold with string concatenation and an initial empty string proceeds as "the " concatenated with ("quick " concatenated with ("brown" concatenated with "")), yielding "the quick brown". This builds the result associatively from right to left, illustrating fold's generality for sequential composition. An important edge case arises with empty lists, where the fold simply returns the initial accumulator value without processing any elements. For instance, folding an empty list with addition and initial 0 returns 0, or with concatenation and initial empty string returns the empty string, ensuring the operation is total and defined for all inputs.[1]

Practical Code Examples

To illustrate the utility of folds in practice, consider the following examples in generic pseudocode, which can be adapted to various functional programming contexts. These snippets highlight common applications while emphasizing the importance of the combining function and fold direction. A basic use of the left fold (foldl) is to compute the sum of a list of numbers, starting from an initial accumulator of 0 and applying addition sequentially from left to right. For the list [1, 2, 3], the expression foldl (+) 0 [1, 2, 3] evaluates to ((0 + 1) + 2) + 3 = 6.[22] For more complex aggregations like computing an average, two separate folds can be combined: one to sum the elements and another to count them (via incrementing an accumulator). In pseudocode: 
sum = foldl (+) 0 [1, 2, 3]
length = foldl (\acc _ -> acc + 1) 0 [1, 2, 3]
average = sum / length  // yields 2
This approach avoids side effects and reuses the fold pattern for both operations.[22] On large lists, a tree-like fold can balance the computation to mitigate deep recursion, such as for summing elements by pairing them into a binary structure before folding. A sketch in pseudocode pairs adjacent elements with the combining function (here, addition) and recurses: 
pairs (+) [1, 2, 3, 4]  // yields [+ 1 2, + 3 4]
fold_tree (+) 0 [[+ 1 2], [+ 3 4]]  // evaluates to ((1 + 2) + (3 + 4)) = 10
This structure ensures logarithmic depth for power-of-two sized lists, improving efficiency on massive inputs.[22] When the combining function is non-associative, such as subtraction, the choice of fold direction affects the result, potentially leading to errors if mismatched with intent. For instance, foldl (-) 0 [1, 2, 3] computes ((0 - 1) - 2) - 3 = -6, while foldr (-) 0 [1, 2, 3] computes 1 - (2 - (3 - 0)) = 2.[23] Folds also enable data validation patterns, such as verifying all elements in a list are positive by accumulating a logical conjunction (short-circuiting on the first negative). This is expressed as foldr (&&) True (map (> 0) [1, 2, -3, 4]), which returns False upon encountering -3.

Usage in Programming Languages

Functional Languages

In functional languages, folds are fundamental higher-order functions that enable declarative reduction of data structures, often integrated as built-in primitives in standard libraries. Haskell provides foldl, foldr, and foldl' in the Data.List module, where foldl and foldr perform left- and right-associative folds over lists, respectively, while foldl' is a strict variant of foldl to avoid space leaks from lazy accumulation.[24] Additionally, the Foldable typeclass, introduced in base 4.8 (2014), generalizes folding operations like foldMap—which maps elements to a monoid and combines them using the monoid's operation—across arbitrary foldable structures beyond lists.[25][11] Standard ML includes foldl and foldr in its List structure, defined in the Basis Library, where foldl applies the folding function left-to-right on the accumulator and foldr does so right-to-left, both returning the initial value for empty lists.[26] In Scheme, as standardized in R7RS (compatible with R6RS libraries), fold-left and fold-right are available in the (rnrs lists (6)) library, iterating over lists with an accumulator in left-to-right or right-to-left order, respectively, to support functional composition without explicit recursion.[27] Common Lisp offers the reduce function, which generalizes folding by applying a binary operation across a sequence, defaulting to left-associativity but configurable for right-to-left via the :from-end keyword, and handling edge cases like empty sequences by invoking the function with zero arguments if no initial value is provided.[28] Scala provides foldLeft and foldRight methods on collections like TraversableOnce, performing left- and right-associative folds, respectively, with an initial value and binary operator; these are commonly used for reductions on sequences, supporting both strict and parallel collections.[29] Idiomatic usage in these languages leverages folds for tasks like parsing streams or monadic computations; for instance, Haskell's Data.Foldable includes monadic variants such as foldrM, which sequences effects right-to-left in a monad, enabling safe accumulation in stateful or error-handling contexts.[11] A key strength in Haskell arises from its lazy evaluation model, which allows foldr to operate on infinite lists by deferring evaluation of the tail until demanded, as the fold builds a lazy spine mirroring the list structure—unlike foldl, which builds a growing thunk leading to non-termination.[30] This laziness supports efficient processing of potentially unbounded data, such as streams generated on-the-fly.[11]

Imperative and Multi-paradigm Languages

In imperative and multi-paradigm languages, fold operations are typically implemented as library functions that mimic left-fold semantics using iterative accumulation, often without native support for right-folds or lazy evaluation. These equivalents promote functional-style programming within mutable, eager execution environments, allowing developers to process collections without explicit loops in many cases. Unlike pure functional languages, these implementations emphasize performance through strict evaluation and integration with object-oriented features. Python provides functools.reduce, introduced in Python 2.3 in 2003, which performs a left-fold by applying a binary function cumulatively to an iterable and an optional initializer.[31] There is no built-in equivalent for right-fold; developers must reverse the iterable or implement custom logic to simulate it. For example, summing a list [1, 2, 3] yields 6: 
from functools import reduce

numbers = [1, 2, 3]
total = reduce(lambda x, y: x + y, numbers)
print(total)  # Output: 6
This function aligns with Python's multi-paradigm nature, enabling concise reductions on sequences like lists or generators, though it requires importing from the standard library in Python 3.[31] JavaScript's Array.prototype.reduce, added in ECMAScript 5 (ES5) in 2009, executes a reducer callback from left to right on array elements, accumulating a single value similar to a left-fold.[32] A companion method, reduceRight, introduced in the same standard, iterates from right to left, providing a direct equivalent to foldr for non-associative operations.[33] For instance, concatenating strings ["a", "b", "c"] from left to right produces "abc": 
const words = ["a", "b", "c"];
const result = words.reduce((acc, word) => acc + word, "");
console.log(result);  // Output: "abc"
In modern JavaScript, developers frequently combine reduce with async/await for asynchronous reductions, though this returns a Promise and requires manual awaiting; Iterator Helpers, included in ECMAScript 2025 (finalized June 2025), provide native support for reductions over async iterables to streamline such patterns.[34] In C#, the LINQ Enumerable.Aggregate method, introduced in .NET Framework 3.5 in 2007, applies an accumulator function across a sequence, supporting left-fold operations with optional seed and result selectors for flexibility in multi-paradigm scenarios.[35] Java offers a comparable reduce in the Stream API, added in Java 8 in 2014, which performs terminal reductions on streams with binary operators. Both integrate with object-oriented pipelines, as in this C# example computing a product: 
using [System](/page/System);
using System.Linq;

int[] numbers = { 1, 2, 3 };
int product = numbers.Aggregate(1, (acc, n) => acc * n);
Console.WriteLine(product);  // Output: 6
To simulate right-folds in these languages where not natively supported (e.g., Python's lack of foldr), programmers often use manual loops that process elements in reverse order, starting from the end of the collection and accumulating backwards.[33] This adaptation preserves the associativity needed for operations like tree construction but requires explicit indexing or reversal, increasing code verbosity compared to functional counterparts. A key challenge in these languages is the absence of laziness, leading to strict left-to-right evaluation by default, which can cause stack overflows for deeply recursive simulations or unnecessary computations on large datasets without built-in stream laziness.[36] This contrasts with functional languages' lazy evaluation, often necessitating hybrid approaches like generators in Python or streams in Java to approximate deferred execution.

Theoretical Aspects

Universality

The fold operation serves as a cornerstone for universality in functional programming, aligning with the Church-Turing thesis by encapsulating recursive computation over data structures in a way that generalizes the definition of effectively computable functions. As an iterator, fold reduces recursive data types to values through a combining function, enabling the expression of algorithms equivalent to those in Turing machines when paired with basic primitives. This generalization of recursion from primitive to higher-order forms underscores fold's role in modeling universal computation without explicit loops or mutable state.[1] Folds enable the expression of all total recursive functions on lists (e.g., primitive recursive functions via tupling, and non-primitive recursive like Ackermann's function using higher-order folds), but full Turing completeness, including partial or non-terminating computations, requires additional mechanisms like fixed-point combinators (e.g., the Y combinator) to simulate the untyped lambda calculus. For example, Church numerals—encodings of natural numbers in lambda calculus—can be realized via folds with tupling, as discussed in the literature on primitive recursion. Similarly, booleans are encoded as Church combinators, with fold enabling their manipulation over list representations. The expressive power extends to non-primitive recursive functions, such as Ackermann's function, which can be defined using higher-order folds in languages like Haskell.[1][1] Despite this capability, fold has limitations: it primarily supports catamorphisms for finite, algebraic data types, capturing only terminating structural recursion. Full general recursion, including non-terminating computations or mutual recursion, requires a fixed-point combinator (e.g., the Y combinator) to introduce self-reference beyond fold's strict pattern. In category theory, folds correspond to catamorphisms, the general notion of recursion over initial algebras, providing a uniform framework for structural induction and program correctness. The theoretical foundations of fold's universality for catamorphisms were established in the late 1980s, with Richard Bird's work on constructive functional programming proving that folds uniquely define recursive functions on initial algebras, providing a basis for program transformation and verification. Building on this, in the 2020s, paramorphisms (fold variants with access to original subterms) have been used in program synthesis for recursive functional programs.[1][37]

Relation to Other Higher-Order Functions

The map function applies a unary function to each element of a data structure, producing a new structure of the same length and shape without altering the overall size. In contrast, fold applies a binary combining function cumulatively to reduce the entire structure to a single scalar value, fundamentally changing the output type and dimensionality.[38][39] The filter function selects a subset of elements from the structure based on a boolean predicate, preserving the structure type but potentially reducing its size. Fold can emulate filter via a single-pass conditional cons in the combining function, such as foldr (\x xs -> if p x then x:xs else xs) [].[39] The scan function extends fold by computing partial accumulations, returning a structure containing all intermediate results—such as prefix sums—rather than just the final value, thus yielding an output similar in size to the input. This distinguishes scan as a non-reducing variant suitable for tracking progressive computations, whereas fold discards intermediates for efficiency.[40] Folds exhibit strong composability with map and filter, enabling pipelines for complex aggregations, such as reducing the result of a mapped and filtered structure to summarize transformed subsets. Fusion optimizations in functional compilers, including map-fold fusion, combine these operations into a single traversal to eliminate intermediate allocations, a technique pioneered in the 1990s through deforestation methods and integrated into production compilers like GHC during the 2000s.[38][41] The unfold function acts as the categorical dual and inverse to fold, starting from a seed value and a producer function to generate an expanding data structure, thereby reversing the reductive process.[42] Programmers select fold for tasks involving aggregation or reduction to a scalar, map for element-wise transformations that maintain structure, filter for conditional selection, and scan for sequences requiring visibility into partial results.[39]

References

  1. [PDF] A tutorial on the universality and expressiveness of fold
  2. [PDF] Can Programming Be Liberated from the von Neumann Style? A ...
  3. [PDF] Recursive Functions of Symbolic Expressions and Their ...
  4. [PDF] Solving Optimisation Problems 'ith Catamorphisms Richard S. Bird ...
  5. [PDF] When is a function a fold or an unfold? - University of Nottingham
  6. Chapter 4. Functional programming - Real World Haskell
  7. None
  8. Organizing functional code for parallel execution or, foldl and foldr ...
  9. Balanced trees inhabiting functional parallel programming
  10. Folding in Parallel - okmij.org
  11. https://hackage.haskell.org/package/monad-par
  12. Data.Foldable - Hackage - Haskell.org
  13. foldl1 and foldr1 - CSCI 3137: Haskell Programming
  14. [PDF] Intro to Haskell Notes: Part 7
  15. Haskell unit 6: The fold functions | Antoni Diller
  16. Data.List.NonEmpty - Hackage - Haskell.org
  17. [PDF] Parallel Sequences: Fold, Reduce and Scan - cs.Princeton
  18. [PDF] Optimizing Parallel Reduction in CUDA - NVIDIA
  19. [PDF] Lazy Evaluation in Haskell - Computer Science - Boston University
  20. How does Lazy Evaluation Work in Haskell? - Heinrich Apfelmus
  21. [PDF] Space leaks exploration in Haskell - Stanford Computer Science
  22. Overview | Parallel Collections - Scala Documentation
  23. Fold - HaskellWiki
  24. 4.3.5. Fold Left vs. Fold Right · Functional Programming in OCaml
  25. Data.List - Hackage - Haskell.org
  26. Data.Foldable - Hackage - Haskell.org
  27. The List structure - Standard ML Family GitHub Project
  28. CLHS: Function REDUCE - Common Lisp HyperSpec (TM)
  29. Foldr Foldl Foldl' - HaskellWiki - Haskell.org
  30. functools — Higher-order functions and operations on callable ...
  31. Array.prototype.reduce() - JavaScript - MDN Web Docs
  32. Array.prototype.reduceRight() - JavaScript - MDN Web Docs
  33. https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.aggregate
  34. Reduction (The Java™ Tutorials > Collections > Aggregate ...
  35. Recursive Program Synthesis using Paramorphisms
  36. [PDF] Map, filter, fold
  37. Higher-order Programming - Cornell: Computer Science
  38. reduceLeft, reduceRight, foldLeft, foldRight, scanLeft, and scanRight ...
  39. [PDF] Theory and Practice of Fusion
  40. [PDF] Fold and Unfold for Program Semantics
User Avatar
No comments yet.