foldr package:base

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)...)

A variant of foldr that has no base case, and thus may only be applied to non-empty structures. This function is non-total and will raise a runtime exception if the structure happens to be empty.

Examples

Basic usage:

>>> foldr1 (+) [1..4]
10

>>> foldr1 (+) []
Exception: Prelude.foldr1: empty list

>>> foldr1 (+) Nothing
*** Exception: foldr1: empty structure

>>> foldr1 (-) [1..4]
-2

>>> foldr1 (&&) [True, False, True, True]
False

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

>>> foldr1 (+) [1..]
* Hangs forever *

foldr' is a variant of foldr that performs strict reduction from right to left, i.e. starting with the right-most element. The input structure must be finite, otherwise foldr' runs out of space (diverges). If you want a strict right fold in constant space, you need a structure that supports faster than O(n) access to the right-most element, such as Seq from the containers package. This method does not run in constant space for structures such as lists that don't support efficient right-to-left iteration and so require O(n) space to perform right-to-left reduction. Use of this method with such a structure is a hint that the chosen structure may be a poor fit for the task at hand. If the order in which the elements are combined is not important, use foldl' instead.

Right-to-left monadic fold over the elements of a structure. Given a structure t with elements (a, b, c, ..., x, y), the result of a fold with an operator function f is equivalent to:

foldrM f z t = do
yy <- f y z
xx <- f x yy
...
bb <- f b cc
aa <- f a bb
return aa -- Just @return z@ when the structure is empty

For a Monad m, given two functions f1 :: a -> m b and f2 :: b -> m c, their Kleisli composition (f1 >=> f2) :: a -> m c is defined by:

(f1 >=> f2) a = f1 a >>= f2

Another way of thinking about foldrM is that it amounts to an application to z of a Kleisli composition:

foldrM f z t = f y >=> f x >=> ... >=> f b >=> f a $ z

The monadic effects of foldrM are sequenced from right to left, and e.g. folds of infinite lists will diverge. If at some step the bind operator (>>=) short-circuits (as with, e.g., mzero in a MonadPlus), the evaluated effects will be from a tail of the element sequence. If you want to evaluate the monadic effects in left-to-right order, or perhaps be able to short-circuit after an initial sequence of elements, you'll need to use foldlM instead. If the monadic effects don't short-circuit, the outermost application of f is to the leftmost element a, so that, ignoring effects, the result looks like a right fold:

a `f` (b `f` (c `f` (... (x `f` (y `f` z))))).

Examples

Basic usage:

>>> let f i acc = do { print i ; return $ i : acc }

>>> foldrM f [] [0..3]
3
2
1
0
[0,1,2,3]

A variant of foldrMap1 where the rightmost element maps to itself.

A variant of foldrMap1' where the rightmost element maps to itself.

Monadic fold over the elements of a non-empty structure, associating to the right, i.e. from right to left.

Right-associative fold of a structure, lazy in the accumulator. In case of NonEmpty lists, foldrMap1, when given a function f, a binary operator g, and a list, reduces the list using g from right to left applying f to the rightmost element:

foldrMap1 f g (x1 :| [x2, ..., xn1, xn]) == x1 `g` (x2 `g` ... (xn1 `g` (f xn))...)

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

foldrMap1 f g = foldrMap1 f g . toNonEmpty

foldrMap1' is a variant of foldrMap1 that performs strict reduction from right to left, i.e. starting with the right-most element. The input structure must be finite, otherwise foldrMap1' runs out of space (diverges). If you want a strict right fold in constant space, you need a structure that supports faster than <math> access to the right-most element. This method does not run in constant space for structures such as NonEmpty lists that don't support efficient right-to-left iteration and so require <math> space to perform right-to-left reduction. Use of this method with such a structure is a hint that the chosen structure may be a poor fit for the task at hand. If the order in which the elements are combined is not important, use foldlMap1' instead.

Map variant of foldrM1.

A right fold over the elements with no starting value

A right fold over the elements

A strict right fold over the elements

foldr' is a variant of foldr that begins list reduction from the last element and evaluates the accumulator strictly as it unwinds the stack back to the beginning of the list. The input list must be finite, otherwise foldr' runs out of space (diverges). Note that if the function that combines the accumulated value with each element is strict in the accumulator, other than a possible improvement in the constant factor, you get the same <math> space cost as with just foldr. If you want a strict right fold in constant space, you need a structure that supports faster than <math> access to the right-most element, such as Seq from the containers package. Use of this function is a hint that the [] structure may be a poor fit for the task at hand. If the order in which the elements are combined is not important, use foldl' instead.

>>> foldr' (+) [1..4]  -- Use foldl' instead!
10

>>> foldr' (&&) [True, False, True, True] -- Use foldr instead!
False

>>> foldr' (||) [False, False, True, True] -- Use foldr instead!
True

foldr1 is a variant of foldr that has no starting value argument, and thus must be applied to non-empty lists. Note that unlike foldr, the accumulated value must be of the same type as the list elements.

>>> foldr1 (+) [1..4]
10

>>> foldr1 (+) []
*** Exception: Prelude.foldr1: empty list

>>> foldr1 (-) [1..4]
-2

>>> foldr1 (&&) [True, False, True, True]
False

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

>>> force $ foldr1 (+) [1..]
*** Exception: stack overflow

The unfoldr function is a `dual' to foldr: while foldr reduces a list to a summary value, unfoldr builds a list from a seed value. The function takes the element and returns Nothing if it is done producing the list or returns Just (a,b), in which case, a is a prepended to the list and b is used as the next element in a recursive call. For example,

iterate f == unfoldr (\x -> Just (x, f x))

In some cases, unfoldr can undo a foldr operation:

unfoldr f' (foldr f z xs) == xs

if the following holds:

f' (f x y) = Just (x,y)
f' z       = Nothing

Laziness

>>> take 1 (unfoldr (\x -> Just (x, undefined)) 'a')
"a"

Examples

>>> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]

>>> take 10 $ unfoldr (\(x, y) -> Just (x, (y, x + y))) (0, 1)
[0,1,1,2,3,5,8,13,21,54]

Combines the elements of a structure in a right associative manner. Given a hypothetical function toEitherList :: p a b -> [Either a b] yielding a list of all elements of a structure in order, the following would hold:

bifoldr f g z ≡ foldr (either f g) z . toEitherList

Examples

Basic usage:

> bifoldr (+) (*) 3 (5, 7)
26 -- 5 + (7 * 3)

> bifoldr (+) (*) 3 (7, 5)
22 -- 7 + (5 * 3)

> bifoldr (+) (*) 3 (Right 5)
15 -- 5 * 3

> bifoldr (+) (*) 3 (Left 5)
8 -- 5 + 3

As bifoldr, but strict in the result of the reduction functions at each step.

A variant of bifoldr that has no base case, and thus may only be applied to non-empty structures.

Examples

Basic usage:

>>> bifoldr1 (+) (5, 7)
12

>>> bifoldr1 (+) (Right 7)
7

>>> bifoldr1 (+) (Left 5)
5

> bifoldr1 (+) (BiList [1, 2] [3, 4])
10 -- 1 + (2 + (3 + 4))

>>> bifoldr1 (+) (BiList [1, 2] [])
3

On empty structures, this function throws an exception:

>>> bifoldr1 (+) (BiList [] [])
*** Exception: bifoldr1: empty structure
...

Right associative monadic bifold over a structure.

The unfoldr function is analogous to Data.List's unfoldr operation.