Data.Foldable.foldr
The foldr
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.
- The value returned in the last invocation of
initialValue :: b
- the value to use as the second argument of the first call of
callback
. Iffoldr
is called with an empty structure forstructure
, then it will simply returninitialValue
.
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
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