Data.Foldable.foldr

The foldr function applies a function against an accumulator and each value of a Foldable structure from right to left, folding it to a single value. foldr is a method of the Foldable typeclass:

foldr (++) [] [[0, 1], [2, 3], [4, 5]] 
-- returns [0, 1, 2, 3, 4, 5]

See also Data.Foldable.foldl for a left-to-right fold. Data.Foldable.foldr is a generic version of Data.List.foldr

Syntax

Type Signature

class Foldable t where
    foldr :: (a -> b -> b) -> b -> t a -> b

Invocation

foldr callback initialValue structure

Parameters

callback :: (a -> b -> b)

Function to execute on each value in the array, this function takes two arguments:

currentValue :: a

The current element being processed in the structure.

previousValue :: b

The value returned in the last invocation of callback or, initialValue if this is the first invocation.

initialValue :: b

the value to use as the second argument of the first call of callback. If foldr is called with an empty structure for structure, then it will simply return initialValue.

structure :: t a

a structure which will be iterated through from right to left.

Return Value

The final value that results from the fold.

Description

foldr will execute the callback function once for each element in the structure. The result will be passed to the next invocation of the callback. For the initial call to callback, previousValue will be initialValue, currentValue will be the last element of the structure. For example:

foldr (+) 4 [0, 1, 2, 3]
-- alternatively written without syntactic sugar for lists:
foldr (+) 4 (0 : (1 : (2 : (3 : []))))

would be equivalent to:

0 + (1 + (2 + (3 + 4)))

Note how foldr essentially replaces the (:) constructor with some other function (in this case (+)). Or more generally:

foldr cb iv [x1, x2, ..., xn]

is equivalent to:

x1 `cb` (x2 `cb` ... (xn `cb` iv)...)

with the initial call to callback being the deepest nested in parenthesis.

For certain values, callback may ignore previousValue, in which case, due to lazy evaluation, foldr will terminate early without calling callback for every element. This is useful for operations on infinite lists. Here is a contrived example demonstrating this:

foldr go [] [1..] where
    go curr prev
        | curr > 10 = []
        | otherwise = (curr : prev)
-- returns [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

In this case, the [] is ignored, we could have written:

foldr go [1,5, 6, 7] [1..] where
    go curr prev
        | curr > 10 = []
        | otherwise = (curr : prev)

and achieved the same result.

Given an empty structure foldr will return initialValue

Examples

Sum all elements in a list

list = [1..100]
foldr (+) 0 list -- returns 5050

Reverse a list

list = [1..10]
foldr (\x xs -> xs ++ [x]) [] list

flatten a Set [a] to a Set a

import qualified Data.Set as S

mySet = S.fromList [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
size mySet -- returns 4
show mySet -- returns "fromList [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]"

flatSet = foldr (\curr prev -> S.union (S.fromList curr) prev) S.empty mySet
size flatSet -- returns 12
show flatSet -- returns "fromList [1,2,3,4,5,6,7,8,9,10,11,12]"

See Also

• Data.Foldable a typeclass for structures which can be folded
• Data.Foldable.foldl similar to foldr but starts from the left instead of the right
• Data.Foldable.foldr' a strict version of foldr
• Data.List.foldr a list specific version of foldr