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?
To recap, with foldr , the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl , the function argument takes a default value, the first element of the list, and returns a new default value.
foldr takes two arguments: A combining function and an identity value. It then returns a function that takes a list and returns an accumulated value.
From HaskellWiki. 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]
The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
The easiest way to understand foldr is to rewrite the list you're folding over without the sugar.
[1,2,3,4,5] => 1:(2:(3:(4:(5:[]))))
now what foldr f x
does is that it replaces each :
with f
in infix form and []
with x
and evaluates the result.
For example:
sum [1,2,3] = foldr (+) 0 [1,2,3] [1,2,3] === 1:(2:(3:[]))
so
sum [1,2,3] === 1+(2+(3+0)) = 6
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With