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))