6

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?

sds
  • 58,617
  • 29
  • 161
  • 278
kmgauthier
  • 85
  • 1
  • 2
  • 5
  • You may find discussion on this page also useful: http://stackoverflow.com/questions/39018163/expanded-form-of-fold-in-racket – rnso Feb 10 '17 at 06:04

2 Answers2

23

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.

soegaard
  • 30,661
  • 4
  • 57
  • 106
  • Note that `(- 1 3) = -2`, so `(foldr - 0 '(1 2 3 4))` should evaluate to -2 and not 2. Same with `foldl`, 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))))`. – assefamaru Feb 09 '17 at 19:36
  • @AlexanderMaru Thanks! I have fixed the mistakes. – soegaard Feb 09 '17 at 21:39
  • @soegaard really cool demonstration of `foldl`; I've never seen it using the expanded `cons` form like you've done here <3 – Mulan Feb 10 '17 at 19:01
  • Love this kind of examples. Thank you! – ihojmanb Jun 12 '20 at 02:11
  • 1
    This 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! – Prometheus Jun 20 '20 at 14:20
1

You can illustrate what is going on in fold, if you create a procedure, which does the same like cons but reverses the arguments. I have called it snoc in the following example.

(define fldl
  (lambda (proc a lst)
    (if (pair? lst)
      (fldl proc
            (proc (car lst)
                  a)
            (cdr lst))
      a)))

(define fldr
  (lambda (proc a lst)
    (if (pair? lst)
      (proc (car lst)
            (fldr proc
                  a
                  (cdr lst)))
      a)))

(define lst (list 1 2 3 4))

(fldl + 0 lst)      ;; => 10
(fldl * 1 lst)      ;; => 24
(fldl cons '() lst) ;; => (4 3 2 1)

(fldr + 0 lst)      ;; => 10
(fldr * 1 lst)      ;; => 24
(fldr cons '() lst) ;; => (1 2 3 4)

(define snoc (lambda (a b) (cons b a)))

(fldl snoc '() lst) ;; => ((((() . 1) . 2) . 3) . 4)
(fldr snoc '() lst) ;; => ((((() . 4) . 3) . 2) . 1)
ceving
  • 21,900
  • 13
  • 104
  • 178