Can anybody explain how does foldr
work?
Take these examples:
Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0
I am confused about these executions. Any suggestions?
Can anybody explain how does foldr
work?
Take these examples:
Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0
I am confused about these executions. Any suggestions?
Ok, lets look at the arguments:
return value:
It first applies the function to the last element in the list and the empty list result. It then reapplies the function with this result and the previous element, and so forth until it takes some current result and the first element of the list to return the final result.
Fold "folds" a list around an initial result using a function that takes an element and some previous folding result. It repeats this for each element. So, foldr does this starting at the end off the list, or the right side of it.
folr f emptyresult [1,2,3,4]
turns intof(1, f(2, f(3, f(4, emptyresult) ) ) )
. Now just follow parenthesis in evaluation and that's it.One important thing to notice is that the supplied function
f
must handle its own return value as its second argument which implies both must have the same type.Source: my post where I look at it from an imperative uncurried javascript perspective if you think it might help.
It helps to understand the distinction between
foldr
andfoldl
. Why isfoldr
called "fold right"?Initially I thought it was because it consumed elements from right to left. Yet both
foldr
andfoldl
consume the list from left to right.foldl
evaluates from left to right (left-associative)foldr
evaluates from right to left (right-associative)We can make this distinction clear with an example that uses an operator for which associativity matters. We could use a human example, such as the operator, "eats":
The semantics of this
foldl
is: A human eats some shark, and then the same human who has eaten shark then eats some fish, etc. The eater is the accumulator.Contrast this with:
The semantics of this
foldr
is: A human eats a shark which has already eaten a fish, which has already eaten some algae. The food is the accumulator.Both
foldl
andfoldr
"peel off" eaters from left to right, so that's not the reason we refer to foldl as "left fold". Instead, the order of evaluation matters.foldr
means fold from the right, sofoldr (-) 0 [1, 2, 3]
produces(1 - (2 - (3 - 0)))
. In comparisonfoldl
produces(((0 - 1) - 2) - 3)
.When the operators are not commutative
foldl
andfoldr
will get different results.In your case, the first example expands to
(10 - (11 - 54))
which gives 53.