SICP Exercise 2.38: MapReduce

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.

What the authors omit to point out in this exercise is that fold-left is also known as reduce. Not particularly relevant, but reduce, in combination with map, inspired a pretty nifty distributed processing framework that you may have heard of.

Okay, let's spin up the interpreter:

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

So what property does op have to satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence?

Well fold-left and fold-right process the elements in opposite directions. Both start with the initial value. I.e. fold-left starts by applying op to the initial value and the first element, takes the result of this and applies op to this value and the second element and so on. However, fold-right starts by applying op to the initial value and the last element, takes the result of this and applies op to this value and the second-last element and so on.

This means that op must return the same result regardless of which order the operators are applied to them. In other words, op must be commutative.