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?
I've always thought http://foldr.com to be a fun illustration. See the Lambda the Ultimate post.
foldr
begins at the right-hand end of the list and combines each list entry with the accumulator value using the function you give it. The result is the final value of the accumulator after "folding" in all the list elements. Its type is:and from this you can see that the list element (of type
a
) is the first argument to the given function, and the accumulator (of typeb
) is the second.For your first example:
So the answer you got was 53.
The second example:
So the result is 12.
Edit: I meant to add, that's for finite lists.
foldr
can also work on infinite lists but it's best to get your head around the finite case first, I think.I think that implementing map, foldl and foldr in a simple fashion helps explain how they work. Worked examples also aid in our understanding.
An easy way to understand
foldr
is this: It replaces every list constructor with an application of the function provided. Your first example would translate to:10 - (11 - 54)
from:
10 : (11 : [])
A good piece of advice that I got from the Haskell Wikibook might be of some use here:
Think about
foldr
's very definition:So for example
foldr (-) 54 [10,11]
must equal(-) 10 (foldr (-) 54 [11])
, i.e. expanding again, equal(-) 10 ((-) 11 54)
. So the inner operation is11 - 54
, that is, -43; and the outer operation is10 - (-43)
, that is,10 + 43
, therefore53
as you observe. Go through similar steps for your second case, and again you'll see how the result forms!The easiest way to understand foldr is to rewrite the list you're folding over without the sugar.
now what
foldr f x
does is that it replaces each:
withf
in infix form and[]
withx
and evaluates the result.For example:
so