Personal tools

Data.Foldable.foldr

From HaskellWiki

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

Jump to: navigation, search
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

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
callback
or,
initialValue
if this is the first invocation.
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.

1.4 Return Value

The final value that results from the fold.

2 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]

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

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

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