Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 243
kmgauthier Avatar asked Feb 09 '17 18:02

kmgauthier


People also ask

What is the difference between Foldl and foldr?

Difference Between foldl and foldr 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.

What does the foldr function do?

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.

How does foldr work in Haskell?

Haskell : foldr. Description: it takes the second argument and the last item of the list and applies the function, then it takes the penultimate item from the end and the result, and so on. See scanr for intermediate results.


1 Answers

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.

like image 194
soegaard Avatar answered Sep 18 '22 23:09

soegaard