Progress Report

Well, it's been a couple of weeks since the last one...

As of tomorrow's meeting we'll have covered all the exercises up to and including 2.72, completing section 2.3 of the book. That means we've covered a grand total of 118 exercises.

I've been doing pretty well at catching up though. I've just finished writing up exercise 2.39, which means that I've written up 85 exercises in total, and a whopping 22 in the last week. So I'm now 72% of the way to being caught up with the ever-moving target.

If I'm really lucky I'll get caught up just in time to fall behind as I go away on holiday...

SICP Exercise 2.39: Folding Reverse

Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38:

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

In both cases we start with the empty list, but, as we discussed in exercise 2.38 we process the elements in different orders: fold-left processes the elements in the list from first to last, while fold-right processes the elements in the list from last to first.

We're starting with the fold-right case first, so we're going to process the elements from last to first. This means that at any particular step in the process we're going to want to combine the results of reversing the later elements in sequence with the current element we're processing. For example, when we finally process the first element of the sequence we want to combine it with the results of reversing the remainder of the sequence. So the current element (x in the lambda expression) needs to go onto the tail of the results of reversing the later elements in the sequence. We know that we can't use cons to append a single item onto the end of a list... But we can use append to combine two lists. If we take the current element of the sequence and turn it into a single-item list then we can append that onto the end of the results of reversing the later elements in the sequence as follows:

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

And just to check that works:

> (reverse (list 1 2 3 4 5))
'(5 4 3 2 1)

The fold-left case is a bit easier. We're processing the elements from first to last, so we can simply cons each element onto the accumulated result sequence in turn. We cons the first element of sequence onto an empty list, giving a single item list. Then we cons the second element of sequence onto that, giving us a list of the first two items from sequence, but in reverse order. And we repeat that throughout the list to give us the reverse list:

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

And again we check it works:

> (reverse (list 1 2 3 4 5))
'(5 4 3 2 1)

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.