SICP Exercise 2.40: Unique Pairs

Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1 ≤ j < i ≤ n. Use unique-pairs to simplify the definition of prime-sum-pairs given above.

In the section on "Nested mappings" the authors show us how to build this sequence of pairs using accumulate:

(accumulate append
            nil
            (map (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))

They then introduce flatmap to simplify the process of mapping and accumulating with append and use this to produce their definition of prime-sum-pairs:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))))

The highlighted section above shows the portion of the procedure that builds the sequence of pairs, and this is pretty much exactly what we want for our unique-pairs procedure:

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
                            (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

Note that this procedure does some unnecessary work though. There are no pairs of integers such that 1 ≤ j < i ≤ n where i=1. The smallest i we can successfully generate any such pairs for is 2 - there's only one such pair: (1,2). So there's no point in starting the sequence passed to flatmap at 1 - we can start it at 2 instead without changing the outcome:

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
                            (enumerate-interval 1 (- i 1))))
           (enumerate-interval 2 n)))

Let's give it a spin:

> (unique-pairs 3)
'((2 1) (3 1) (3 2))
'> (unique-pairs 4)
((2 1) (3 1) (3 2) (4 1) (4 2) (4 3))
'> (unique-pairs 5)
((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4))

Finally we can replace the old code to generate unique pairs in prime-sum-pairs with an appropriate call to unique-pairs:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum? (unique-pairs n))))

...and then test it works:

> (prime-sum-pairs 3)
'((2 1 3) (3 2 5))
> (prime-sum-pairs 4)
'((2 1 3) (3 2 5) (4 1 5) (4 3 7))
> (prime-sum-pairs 5)
'((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7))

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)