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?
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.
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.
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.
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
.
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