SICP Exercise 2.38

Question

The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

What are the values of

(fold-right / 1 (list 1 2 3))
(fold-left  / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left  list nil (list 1 2 3))

Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Answer

Let’s look at the output of these four statements.

3/2
1/6
(1 (2 (3 ())))
(((() 1) 2) 3)

Clearly, fold-left and fold-right are not equivalent in their functionality. (fold-right / 1 (list 1 2 3)), for example, seems to return \(\frac{3}{\frac{2}{1}}\) or \(\frac{3}{2}\), whereas fold-left returns \(\frac{1}{\frac{2}{3}}\) or \(\frac{1}{6}\).

This makes logical sense, since the order in which operators are performed matters in the case of division. \(\frac{a}{b}\) is not the same thing as \(\frac{b}{a}\), so it makes a difference whether you roll the equation up from the left or from the right.

But there are other arithmetical operations for which the order does not matter. These operations are called commutative, and it is precisely this property which needs to be given for fold-left and fold-right to produce equivalent results.

Addition and multiplication are commutative, subtraction and division are not. The following small program should demonstrate this:

; commutative
(equal? (fold-right + 1 (list 1 2 3))
        (fold-left  + 1 (list 1 2 3)))
(equal? (fold-right * 1 (list 1 2 3))
        (fold-left  * 1 (list 1 2 3)))

; non-commutative
(equal? (fold-right - 1 (list 1 2 3))
        (fold-left  - 1 (list 1 2 3)))
(equal? (fold-right / 1 (list 1 2 3))
        (fold-left  / 1 (list 1 2 3)))

Results:

#t
#t
#f
#f