How do foldl and foldr work, broken down in an example? ·

20 Dec 2023, 00:00

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 and foldr 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 do 0 -(4-3-2-1) and get 2 which is the right answer

(foldl - 0 '(4 3 2 1)) I do 0-(1-2-3-4) and get 8 but it should be -2.

(foldr - 0 '(1 2 3 4)) I do 0-(1-2-3-4) and get 8 again, but it should be -2.

(foldr - 0 '(4 3 2 1)) I do 0-(4-3-2-1) and get 2 which is the right answer.

What am I doing wrong?

1 Answer

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.

ncG1vNJzZmirpJawrLvVnqmfpJ%2Bse6S7zGiorp2jqbawutJoa2tpZGl9d4SOoaawZZSkeqe7y52jZpmemXqnu8udqWavn6e4bq7RqKKepl2ZvLi6jKKlZpmeYrK5rcypo54%3D

 Share!