# Difference between revisions of "Data.Foldable.foldr"

(→See Also) |
(Use unsugared-list in example) |
||

Line 47: | Line 47: | ||

<pre> |
<pre> |
||

foldr (+) 4 [0, 1, 2, 3] |
foldr (+) 4 [0, 1, 2, 3] |
||

+ | -- alternatively written without syntactic sugar for lists: |
||

+ | foldr (+) 4 (0 : (1 : (2 : (3 : [])))) |
||

</pre> |
</pre> |
||

would be equivalent to: |
would be equivalent to: |
||

Line 52: | Line 54: | ||

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

</pre> |
</pre> |
||

⚫ | |||

+ | Note how <hask>foldr</hask> essentially replaces the <hask>(:)</hask> constructor with some other function (in this case <hask>(+)</hask>). |
||

⚫ | |||

<pre> |
<pre> |
||

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

## Revision as of 12:58, 15 November 2017

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

## Contents

## 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`

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