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.

SICP Exercise 2.37: Matrix Manipulation

Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) as sequences of vectors (the rows of the matrix). For example, the matrix

⎡ 1 2 3 4 ⎤
⎢ 4 5 6 6 ⎥
⎣ 6 7 8 9 ⎦

is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

(dot-product v w)       returns the sum Σiviwi
(matrix-*-vector m v)   returns the vector t, where ti = Σjmijvj
(matrix-*-matrix m n)   returns the matrix p, where pij = Σkmiknkj
(transpose m)           returns the matrix n, where nij = mji

We can define the dot product as

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in exercise 2.36.)

(define (matrix-*-vector m v)
  (map <??> m))
(define (transpose mat)
  (accumulate-n <??> <??> mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map <??> m)))

The formal definition of matrix-*-vector given above effectively indicates that the generated vector should contain the results of calculating the dot products of each of the rows in m and the vector v. Now as the matrix m is represented as a sequence of sequences, with each sub-sequence representing the corresponding row in the matrix, mapping across the matrix will perform an operation on each row of the sequence. So all we need to do is provide a procedure that calculates the dot product of the row and v and we have our implementation:

(define (matrix-*-vector m v)
  (map (lambda (x) (dot-product x v)) m))

The procedure transpose needs to transform the matrix so that the rows become columns and vice versa. In other words, we need to take the first item from each row in turn and put them together, in order, into a sequence, then we take the second item from each row in turn and put them into a sequence, and so on, and put these resulting sequences together to form our transformed matrix.

Now we know that the procedure accumulate-n applies accumulate to the sequence containing the first items from each sequence in a sequence of sequences, and then cons the result onto the sequence produced by applying accumulate-n to the sequence of sequences produced by taking the tails of each of the original sequences. It just so happens that the sequence passed to accumulate in this process is the sequence we want, so all we need to do is to pass an appropriate operator and base case to accumulate-n so that it effectively turns the application of accumulate into an identity function. In this case the operator cons and the base case nil will achieve the desired effect:

(define (transpose mat)
  (accumulate-n cons nil mat))

Finally onto matrix-*-matrix. Matrix multiplication takes an a×b matrix, m, and a b×c matrix, n, and produces a new a×c matrix, p, where the value p_ij is calculated as the dot product of the i^th row of m and the j^th column of n. Handily the template we're given for matrix-*-matrix transforms the matrix n so that its rows become columns and vice versa. This means that each sub-sequence of cols will have the same length as each sub-sequence of m, and we can generate each row of the resulting matrix by taking the corresponding sub-sequence from m and applying matrix-*-vector to the matrix cols and that sub-sequence of m:

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x) (matrix-*-vector cols x))
         m)))

Okay, let's see these matrix operations in action:

> (define v (list 1 2 3))
> (define m1 (list (list 1 2 3) (list 4 5 6)))
> (define m2 (list (list 1 2) (list 3 4) (list 5 6)))
> (matrix-*-vector m1 v)
'(14 32)
> (transpose m1)
'((1 4) (2 5) (3 6))
> (matrix-*-matrix m1 m2)
'((22 28) (49 64))