# Data.Foldable.foldr

### From HaskellWiki

(Difference between revisions)

(MDN style documentation: initial commit) |
m |
||

Line 5: | Line 5: | ||

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

− | See also [[Data.Foldable.foldl]] for a left-to-right fold. | + | 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 == | == Syntax == |

## Revision as of 06:14, 14 November 2017

The**function applies a function against an accumulator and each value of a**

foldr

Foldable

foldr

Foldable

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

## Contents |

## 1 Syntax

### 1.1 Type Signature

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

### 1.2 Invocation

foldr callback initialValue structure

### 1.3 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 or,callbackif this is the first invocation.initialValue

- The value returned in the last invocation of

initialValue :: b

- the value to use as the second argument of the first call of . Ifcallbackis called with an empty structure forfoldr, then it will simply returnstructure.initialValue

structure :: t a

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

### 1.4 Return Value

The final value that results from the fold.

## 2 Description

foldr

callback

previousValue

initialValue

currentValue

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

would be equivalent to:

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

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

previousValue

foldr

callback

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

[]

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

and achieved the same result.

Given an empty structurefoldr

initialValue

## 3 Examples

### 3.1 Sum all elements in a list

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

### 3.2 Reverse a list

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

### 3.3 flatten a Set [a] to a Set a

Set [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]"

## 4 See Also

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