SICP 2.38 & 2.39: Folding Left and Right

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.38 informs us that another name for the accumulate procedure we've been using is fold-right, because it combines the elements of a sequence starting on the left and moving to the right. There's also a fold-left procedure that combines elements working in the opposite direction.

; fold-right is another name for accumulate
(define (fold-right op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (fold-right op initial (cdr sequence)))))

; fold-left is given in exercise 2.38
(define (fold-left op initial sequence)
   (define (iter result rest)
     (if (null? rest)
         result
         (iter (op result (car rest))
               (cdr rest))))
   (iter initial sequence))

We're given a few expressions that illustrate how these two procedures behave differently.

> (fold-right / 1 (list 1 2 3))
1 1/2
> (fold-left / 1 (list 1 2 3))
1/6
> (fold-right list null (list 1 2 3))
(1 (2 (3 ())))
> (fold-left list null (list 1 2 3))
(((() 1) 2) 3)

We're asked what property the op parameter needs to satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

The property that will guarantee that fold-right and fold-left will produce the same values for any sequence is commutativity. You may remember the commutative property of both addition and multiplication from algebra. It's the law that says that:

A + B = B + A

and

A x B = B x A

Subtraction and division are not commutative operations. The AND and OR operations in Boolean algebra are commutative.


Exercise 2.39 asks us to complete the following definitions of reverse (from exercise 2.18) in terms of fold-right and fold-left:

(define (reverse sequence)
   (fold-right (lambda (x y) <??>) null sequence))

(define (reverse sequence)
   (fold-left (lambda (x y) <??>) null sequence))

Since we only need to define the operator used in each implementation, the key to this exercise lies in how the operator is applied in each folding procedure. Pay close attention to the order of the arguments of the op procedure.

In fold-right the operator is applied to the car of the sequence and the result of a recursive call to fold-right. Just as we did in exercise 2.18, we can reverse the sequence using fold-right by appending the car of the sequence to the reverse of its cdr.

(define (reverse sequence)
   (fold-right (lambda (x y) (append y (list x))) null sequence))

In fold-left the operator is applied to the result sequence and the car of the unused elements in the initial sequence. Since the result sequence starts with an initial value of null, and we're starting at the end of the sequence and working backwards anyway, we can just cons each element to the end of the result.

(define (reverse sequence)
   (fold-left (lambda (x y) (cons y x)) null sequence))

As expected, we get the same test results for either of the two reverse implementations above.

> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.