Concept:
Fold_function
Headline
A higher-order function for processing a data structure
Illustration
Language:Haskell's foldr function for lists is defined like as follows:
-- The higher-order function foldr for lists
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
That is, foldr, applied to a binary operator f, a value z, and a list, returns z for the empty list, and it recurses on the tail of a non-empty list such that the recursive result is combined with the head by means of f. For instance:
Prelude> foldr (+) 0 [1,2,3,4,5]
15
The "r" in "foldr" hints at the right-associative bias of the function:
foldr (+) 0 [1,2,3,4,5] = 1 + (2 + (3 + (4 + (5 + 0))))
That is, parenthesization associates to the right. There is also a foldl function:
-- The higher-order function foldl for lists
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Left-associative fold can be expressed in terms of right-associative fold:
foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
The opposite direction is feasible too with some limitations regarding infinite lists and laziness. This is not further discussed here. There is yet other fold functions for lists, which we do not discuss here. Conceptually, fold functions are not limited to lists; they make sense for algebraic data types in general. List-like folds can be generalized to foldable types.
Relationhips
- The application of a fold function is a catamorphism.
- Fold is the dual of unfold; see the unfold function.
- A fold function is also illustrated for Maybe types.
Citation
(http://en.wikipedia.org/wiki/Fold_(higher-order_function), 18 May 2013)
In functional programming, fold – also known variously as reduce, accumulate, aggregate, compress, or inject – refers to a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its constituent parts, building up a return value. 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.
Ralf Lämmel
edited this article at
Wed, 17 Jun 2020 12:39:01 +0200
User contributions
User edits
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.