View source for Data.Foldable.foldr

The <strong><hask>foldr</hask></strong> function applies a function against an accumulator and each value of a <hask>Foldable</hask> structure from right to left, folding it to a single value. <hask>foldr</hask> is a method of the <hask>Foldable</hask> typeclass:
<pre>
foldr (++) [] [[0, 1], [2, 3], [4, 5]] 
-- returns [0, 1, 2, 3, 4, 5]
</pre>

See also [[Data.Foldable.foldl]] for a left-to-right fold. <hask>Data.Foldable.foldr</hask> is a generic version of [[Data.List.foldr]]

== Syntax ==
=== Type Signature ===

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

=== Invocation ===

<pre>
foldr callback initialValue structure
</pre>

=== Parameters ===

<pre>callback :: (a -> b -> b)</pre>
:Function to execute on each value in the array, this function takes two arguments:

:<pre>currentValue :: a</pre>
::The current element being processed in the structure.

:<pre>previousValue :: b</pre>
::The value returned in the last invocation of <hask>callback</hask> or, <hask>initialValue</hask> if this is the first invocation.

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

<pre>structure :: t a</pre>
:a structure which will be iterated through from right to left.

=== Return Value ===

The final value that results from the fold.

== Description ==

<hask>foldr</hask> 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 <hask>callback</hask>, <hask>previousValue</hask> will be <hask>initialValue</hask>, <hask>currentValue</hask> will be the last element of the structure. For example:
<pre>
foldr (+) 4 [0, 1, 2, 3]
</pre>
would be equivalent to:
<pre>
0 + (1 + (2 + (3 + 4)))
</pre>
or more generally:
<pre>
foldr cb iv [x1, x2, ..., xn]
</pre>
is equivalent to:
<pre>
x1 `cb` (x2 `cb` ... (xn `cb` iv)...)
</pre>
with the initial call to callback being the deepest nested in parenthesis.

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

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

In this case, the <hask>[]</hask> is ignored, we could have written:

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

and achieved the same result.

Given an empty structure <hask>foldr</hask> will return <hask>initialValue</hask>

== Examples ==

=== Sum all elements in a list ===

<pre>
list = [1..100]
foldr (+) 0 list -- returns 5050
</pre>

=== Reverse a list ===

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

=== flatten a <hask>Set [a]</hask> to a <hask>Set a</hask> ===

<pre>
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]"
</pre>

== See Also ==

* [[Data.Foldable]] a typeclass for structures which can be folded
* [[Data.Foldable.foldl]] similar to <hask>foldr</hask> but starts from the left instead of the right
* [[Data.Foldable.foldr']] a strict version of <hask>foldr</hask>
* [[Data.List.foldr]] a list specific version of <hask>foldr</hask>

[[Category:Reference]]