Lably
Skip to content

Fold (higher-order function)

Family of higher-order functions

  • 20 min read
  • 4 chapters

Related on Lably

Through Analysis, Recursion and Function (computer programming)

LabSentiment AnalysisLab · Class 10–11Sentiment Analysis On TextLab · Class 6–12AI & Python Builds (Medha AI)Lab · Class 6–12Data Visualization Lab

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

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:

<span id="mwTQ"></span><span class="w" id="mwTg"> </span><span class="n" id="mwTw">map</span><span class="w" id="mwUA"> </span><span class="n" id="mwUQ">f</span><span class="w" id="mwUg"> </span><span class="ow" id="mwUw">=</span><span class="w" id="mwVA"> </span><span class="n" id="mwVQ">foldr</span><span class="w" id="mwVg"> </span><span class="p" id="mwVw">((</span><span class="kt" id="mwWA">:</span><span class="p" id="mwWQ">)</span><span class="w" id="mwWg"> </span><span class="o" id="mwWw">.</span><span class="w" id="mwXA"> </span><span class="n" id="mwXQ">f</span><span class="p" id="mwXg">)</span><span class="w" id="mwXw"> </span><span class="kt" id="mwYA">[]</span>

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.

Sign in to keep reading

3 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard