foldr

Right-associative fold of a structure, lazy in the accumulator. In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Note that since the head of the resulting expression is produced by an application of the operator to the first element of the list, given an operator lazy in its right argument, foldr can produce a terminating expression from an unbounded list. For a general Foldable structure this should be semantically identical to,

foldr f z = foldr f z . toList

Examples

Basic usage:

>>> foldr (||) False [False, True, False]
True

>>> foldr (||) False []
False

>>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
"foodcba"

Infinite structures

⚠️ Applying foldr to infinite structures usually doesn't terminate. It may still terminate under one of the following conditions:

• the folding function is short-circuiting
• the folding function is lazy on its second argument

Short-circuiting

(||) short-circuits on True values, so the following terminates because there is a True value finitely far from the left side:

>>> foldr (||) False (True : repeat False)
True

But the following doesn't terminate:

>>> foldr (||) False (repeat False ++ [True])
* Hangs forever *

Laziness in the second argument

Applying foldr to infinite structures terminates when the operator is lazy in its second argument (the initial accumulator is never used in this case, and so could be left undefined, but [] is more clear):

>>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
[1,4,7,10,13]

foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a ByteString, reduces the ByteString using the binary operator, from right to left.

foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a packed string, reduces the packed string using the binary operator, from right to left.

foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a ShortByteString, reduces the ShortByteString using the binary operator, from right to left.

O(n) foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a Text, reduces the Text using the binary operator, from right to left. If the binary operator is strict in its second argument, use foldr' instead. foldr is lazy like foldr for lists: evaluation actually traverses the Text from left to right, only as far as it needs to. For example, head can be defined with O(1) complexity using foldr:

head :: Text -> Char
head = foldr const (error "head empty")

Searches from left to right with short-circuiting behavior can also be defined using foldr (e.g., any, all, find, elem).

foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a stream, reduces the stream using the binary operator, from right to left. Properties

foldr f z0 . stream = foldr f z0

O(n) foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a Text, reduces the Text using the binary operator, from right to left. foldr is lazy like foldr for lists: evaluation actually traverses the Text from left to right, only as far as it needs to. For example, head can be defined with O(1) complexity using foldr:

head :: Text -> Char
head = foldr const (error "head empty")

Fold the values in the map using the given right-associative binary operator, such that foldr f z == foldr f z . elems. For example,

elems map = foldr (:) [] map

let f a len = len + (length a)
foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

Fold the elements in the set using the given right-associative binary operator, such that foldr f z == foldr f z . toAscList. For example,

toAscList set = foldr (:) [] set

Fold the values in the map using the given right-associative binary operator, such that foldr f z == foldr f z . elems. For example,

elems map = foldr (:) [] map

let f a len = len + (length a)
foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

Fold the elements in the set using the given right-associative binary operator, such that foldr f z == foldr f z . toAscList. For example,

toAscList set = foldr (:) [] set

Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

Reduce this set by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

Traverse a bytestring (right biased).

Traverse a bytestring (right biased).

Traverse a bytestring (right biased).

Fold the values in the map using the given right-associative binary operator, such that foldr f z == foldr f z . elems. For example,

elems map = foldr (:) [] map

let f a len = len + (length a)
foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

Fold the elements in the set using the given right-associative binary operator, such that foldr f z == foldr f z . toAscList. For example,

toAscList set = foldr (:) [] set

foldr f z xs is the right-fold of f over xs. <math>(length (toList xs)). foldr obeys the law:

foldr f z xs = foldr f z (toList xs)

Right fold over all key-value pairs in the headers map. Example:

ghci> :set -XOverloadedStrings
ghci> import Data.Monoid
ghci> let hdrs = H.fromList [("Accept", "text/plain"), ("Accept", "text/html")]
ghci> let f _ val (cntr, acc) = (cntr+1, val <> ";" <> acc)
ghci> H.foldr f (0, "") hdrs
(2,"text/plain;text/html;")

Right-associative fold of a structure. In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Note that, since the head of the resulting expression is produced by an application of the operator to the first element of the list, foldr can produce a terminating expression from an infinite list. For a general Foldable structure this should be semantically identical to,

foldr f z = foldr f z . toList