In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order function
Higher-order function
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
Analysis is the process of breaking a complex topic or substance into smaller parts to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle , though analysis as a formal concept is a relatively recent development.The word is...
a recursive data structure and recombine through use of a given combining operation the results of recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy
Hierarchy
A hierarchy is an arrangement of items in which the items are represented as being "above," "below," or "at the same level as" one another...
, 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
Corecursion
In computer science, corecursion is a type of operation that is dual to recursion. Corecursion and codata allow total languages to work with infinite data structures such as streams. Corecursion is often used in conjunction with lazy evaluation. Corecursion can produce both finite and infinite data...
to decide how to progressively construct a corecursive data structure, whereas a fold recursively breaks that structure down, replacing it with results of applying combining function at each node on its terminal
Terminal and nonterminal symbols
In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules that constitute a formal grammar...
In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...
Anamorphosis is a distorted projection or perspective requiring the viewer to use special devices or occupy a specific vantage point to reconstitute the image...
of unfolds).
Folds as structural transformations
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 languages from two primitives: any list is either an empty list, commonly called nil ([]), or is cons tructed by prepending an element in front of another list, creating what is called a consnode
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
( Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), resulting from application of a cons function, written down as (:) (colon) in Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
. One can view a fold on lists say, as substituting the nil at the end of the list with a specific value, and each cons with a specific other function. Hence, one gets a diagram which looks something like this:
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 left and right fold of a list visually. They also highlight the fact that foldr (:) [] is the identity function on lists (a shallow copy in Lisp
Lisp
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with interdentals , though there are actually several kinds of 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
Map (higher-order function)
In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. They are examples of both catamorphisms and anamorphisms...
in terms of foldr, by composing the function to act on the elements with cons, as:
In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones...
.
This way of looking at things provides a simple route to designing fold-like functions on other algebraic data 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
Catamorphism
In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...
.
Folds on lists
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.
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
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
'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
Additive identity
In mathematics the additive identity of a set which is equipped with the operation of addition is an element which, when added to any element x in the set, yields x...
) 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.
Linear vs. tree-like folds
The use of initial value is necessary when the combining function f is asymmetrical in its types, i.e. when the type of its result is different from the type of 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 has to 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 symmetrical in its types and the result type is the same as the list elements' type, the parentheses may be placed in arbitrary fashion thus creating a 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
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
of a list, tree-like folds are whole-list oriented and operate in a consistent manner across groups of nodes.
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
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 "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.
Linear folds
Using Haskell as an example, foldl and foldr can be formulated in a few equations.
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 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
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] = x
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 f 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, and/or not immediately (example below).
Folds for non-empty lists
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))
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
, 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) undefined ). 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
Infinite loop
An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over...
.
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 the combining function to inspect the list's elements from the left; and conversely, while foldl recurses "on the left" it allows for the combining function to inspect the list's elements from the right, if it so chooses (e.g. last foldl (\a b->b) undefined ).
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 technique, foldr f z xs foldl (\k x-> k . f x) id xs z ).
Another technical point to be aware of in the case of left folds using lazy evaluation is that 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.
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
interpreter, we can show the structural transformation which fold functions perform by constructing a string as follows:
Prelude> putStrLn $ 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)))))))))))))
Prelude> putStrLn $ 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)
Prelude> putStrLn $ foldt (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))
Prelude> putStrLn $ 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 primes production by unbounded sieve of Eratosthenes in Haskell:
primes = 2 : 3 : ([5,7..] `minus` foldi (\(x:xs) ys -> x : union xs ys) []
*p, p*p+2*p..] | p <- tail primes])
where the function union operates on ordered lists in a local manner to efficiently produce their set union, and minus their set difference.
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
could be easily defined using tree-like folding as
mergesort xs = foldt merge [] ] | x <- xs]
with the function merge a duplicates-preserving variant of union.
Folds in various languages
The programming language C# version 3.0 was released on 19 November 2007 as part of .NET Framework 3.5. It includes new features inspired by functional programming languages such as Haskell and ML, and is driven largely by the introduction of the Language Integrated Query pattern to the Common...
An Extension method is a new language feature of C# starting with the 3.0 specification, as well as Visual Basic.NET starting with 9.0 and Oxygene with 2.0. Extension methods enable you to "add" methods to existing types without creating a new derived type, recompiling, or otherwise modifying...
ienum is an IEnumerable Similarly in all .NET languages
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
std::accumulate(begin, end, initval, func)
std::accumulate(rbegin, rend, initval, func)
in header begin, end, rbegin, rend are iterators func can be a function pointer
Function pointer
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...
Clojure |closure]]") is a recent dialect of the Lisp programming language created by Rich Hickey. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming....
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
(reduce funclist :initial-value initval)
(reduce funclist :from-end t :initial-value initval)
The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
haXe is a versatile open-source high-level multiplatform programming language described on its website as a "universal language".It can produce:* Flash applications and games* Multi-platform client-side web applications* Apache CGI web applications...
The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
Maple is a general-purpose commercial computer algebra system. It was first developed in 1980 by the Symbolic Computation Group at the University of Waterloo in Waterloo, Ontario, Canada....
Oz is a multiparadigm programming language, developed in the Programming Systems Lab at Université catholique de Louvain, for programming language education. It has a canonical textbook: Concepts, Techniques, and Models of Computer Programming....
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
array_reduce(array, func, initval)
array_reduce(array, func)
When initval is not supplied, NULL is used, so this is not a true foldl1. Prior to PHP 5.3, initval can only be integer. "func" is a callback.
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
3.x
functools.reduce(func, list, initval)
functools.reduce(func, list)
In module functools.
For reference functools.reduce: import functools
For reference reduce: from functools import reduce
R is a programming language and software environment for statistical computing and graphics. The R language is widely used among statisticians for developing statistical software, and R is widely used for statistical software development and data analysis....
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.
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
In Ruby 1.8.7+, can also pass a symbol representing a function instead of a block. enum is an Enumeration If enum is array use reverse instead reverse_each
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
aCollection inject: aValue into: aBlock
aCollection reduce: aBlock
ANSI Smalltalk doesn't define #reduce: but many implementations do.
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
In computer science, polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface. The concept of parametric polymorphism applies to both data types and functions...
In computer science, a fixed-point combinator is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that x = f. For example, 0 and 1 are fixed points of the function f = x2, because 0 = 02 and 1 = 12...
using fold, proving that iterations can be reduced to folds: fix f = foldr (\_ -> f) undefined (repeat undefined)
See also
In computer science, an aggregate function is a function where the values of multiple rows are grouped together as input on certain criteria to form a single value of more significant meaning or measurement such as a set, a bag or a list....
In mathematics, an iterated binary operation is an extension of a binary operation on a set S to a function on finite sequences of elements of S through repeated application. Common examples include the extension of the addition operation to the summation operation, and the extension of the...
In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. They are examples of both catamorphisms and anamorphisms...
In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....
.gif)
