How do foldl and foldr work, broken down in an example?
Let's look at: (foldr - 0 '(1 2 3 4))
.
Here the literal '(1 2 3 4)
constructs a list whose elements are the numbers 1, 2, 3, and, 4. Let's make the construction of the list explicit:
(cons 1 (cons 2 (cons 3 (cons 4 empty))))
One can think of foldr
as a function that replaces cons
with a function f
and empty with a value v
.
Therefore
(foldr f 0 (cons 1 (cons 2 (cons 3 (cons 4 empty)))))
becomes
(f 1 (f 2 (f 3 (f 4 v)))))
If the function f is -
and the value v
is 0, you will get:
(- 1 (- 2 (- 3 (- 4 0)))))
And we can calculate the result:
(- 1 (- 2 (- 3 (- 4 0))))
= (- 1 (- 2 (- 3 4)))
= (- 1 (- 2 -1))
= (- 1 3)
= -2
Note that (foldr cons empty a-list)
produces a copy of a-list
.
The function foldl
on the other hand uses the values from the other side:
> (foldl cons empty '(1 2 3 4))
'(4 3 2 1)
In other words:
(foldl f v '(1 2 3 4))
becomes
(f 4 (f 3 (f 2 (f 1 v)))).
If f
is the function -
and the value is 0, then we get:
(- 4 (- 3 (- 2 (- 1 0))))
= (- 4 (- 3 (- 2 1)))
= (- 4 (- 3 1))
= (- 4 2)
= 2
Note that (foldl cons empty a-list)
produces the reverse of a-list
.
kmgauthier
Updated on June 04, 2022Comments
-
kmgauthier almost 2 years
Okay, I am new with scheme/racket/lisp. I am practicing creating my own functions, syntax, and recursion, so I want to make my own
foldl
andfoldr
functions that do exactly what the predefined versions do. I can't do it because I just don't understand how these functions work. I have seen similar questions on here but I still don't get it. Some examples broken down would help! Here is my (incorrect) process:(foldl - 0 '(1 2 3 4))
I do0 -(4-3-2-1)
and get 2 which is the right answer(foldl - 0 '(4 3 2 1))
I do0-(1-2-3-4)
and get 8 but it should be -2.(foldr - 0 '(1 2 3 4))
I do0-(1-2-3-4)
and get 8 again, but it should be -2.(foldr - 0 '(4 3 2 1))
I do0-(4-3-2-1)
and get 2 which is the right answer.What am I doing wrong?
-
assefamaru about 7 yearsNote that
(- 1 3) = -2
, so(foldr - 0 '(1 2 3 4))
should evaluate to -2 and not 2. Same withfoldl
, it should be 2 and not -2.(foldl f v '(1 2 3 4))
should become(f 4 (f 3 (f 2 (f 1 v))))
. -
soegaard about 7 years@AlexanderMaru Thanks! I have fixed the mistakes.
-
Mulan about 7 years@soegaard really cool demonstration of
foldl
; I've never seen it using the expandedcons
form like you've done here <3 -
ihojmanb almost 4 yearsLove this kind of examples. Thank you!
-
Prometheus almost 4 yearsThis is the best and most simplest explanation to foldr. I've researched this topic for a while now and i couldn't figure it out what foldr is doing. Your explanation is so on point! Thank you!