# Data.Foldable.foldr

### From HaskellWiki

Revision as of 06:14, 14 November 2017 by PilotInPyjamas (Talk | contribs)

The structure from right to left, folding it to a single value. is a method of the typeclass:
is a generic version of Data.List.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 , will be , will be the last element of the structure. For example:
may ignore , in which case, due to lazy evaluation, will terminate early without calling for every element. This is useful for operations on infinite lists. Here is a contrived example demonstrating this:
is ignored, we could have written:
will return
### 3.3 flatten a

**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