SICP 2.40 & 2.41: Nested Mappings

From SICP section 2.2.3 Sequences as Conventional Interfaces

The next sub-section of SICP shows us how we can express nested loops using sequence operations. The first example given is the following problem:

Given a positive integer n, find all ordered pairs of distinct positive integers i and j, where 1 <= j < i <= n, such that (i + j) is prime.

In pseudocode, a solution using nested loops would be:

for i = 1 to n:
   for j = 1 to (i - 1):
       if isPrime( i + j ):
           print i, j, i + j

For n = 6, the output of the program above would be:

2, 1, 3
3, 2, 5
4, 1, 5
4, 3, 7
5, 2, 7
6, 1, 7
6, 5, 11

One way of looking at this is that the two nested loops generate a sequence of pairs, and the if statement applies a filter to each pair in the sequence.

In Scheme we can produce a sequence of pairs using nested mappings.

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

The flatmap procedure is defined to abstract the portion of the code above that accumulates with append.

(define (flatmap proc seq)
   (accumulate append null (map proc seq)))

Procedures are then defined to filter out prime sums and to create the pair sum output from each pair in the sequence.

(define (prime-sum? pair)
   (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
   (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

Combining all of these steps with the filter and enumerate-interval procedures from earlier in SICP section 2.2.3, we get the complete procedure.

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

Exercise 2.40 asks us to define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i j) with 1 <= j < i <= n. We are to use unique-pairs to simplify the definition of prime-sum-pairs given above.

Since we already have code embedded in prime-sum-pairs that generates the sequence of unique pairs that we need, this exercise basically amounts to an extract method refactoring of that piece of code.

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

The body of unique-pairs is a simple copy/paste from prime-sum-pairs. Replacing that portion of code in the original is just as easy.

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

We can test it with a known value to verify.

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

Exercise 2.41 asks us to write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

If we were solving this using loops, we'd just nest our loops three deep. This exercise teaches us that nested mappings can be extended the same way. Let's start by creating a procedure that just finds ordered triples of distinct positive integers. We'll base it on unique-pairs from the previous exercise.

(define (ordered-triples n)
   (flatmap (lambda (i)
      (flatmap (lambda (j)
         (map (lambda (k)
                (list i j k))
              (enumerate-interval 1 (- j 1))))
       (enumerate-interval 1 (- i 1))))
    (enumerate-interval 1 n)))

> (ordered-triples 5)
((3 2 1)
(4 2 1)
(4 3 1)
(4 3 2)
(5 2 1)
(5 3 1)
(5 3 2)
(5 4 1)
(5 4 2)
(5 4 3))

Next we can create a filtering procedure that checks to see if a triple sums to a given integer.

(define (triple-sum? triple s)
   (= s (accumulate + 0 triple)))

> (triple-sum? (list 1 2 3) 5)
#f
> (triple-sum? (list 1 2 3) 6)
#t

We also need a procedure to append the sum of the elements of a triple to the end of the triple so it's included in the output.

(define (make-triple-sum triple)
   (append triple (list (accumulate + 0 triple))))

> (make-triple-sum (list 1 2 3))
(1 2 3 6)

Finally, we can put it all together. Since filter takes only two arguments, a predicate and a sequence, we need to embed our predicate procedure triple-sum? in the final solution so that it can have access to the target sum variable s.

(define (ordered-triple-sum n s)
   (define (triple-sum? triple)
     (= s (accumulate + 0 triple)))
   (map make-triple-sum
        (filter triple-sum?
                (ordered-triples n))))

> (ordered-triple-sum 5 10)
((5 3 2 10) (5 4 1 10))
> (ordered-triple-sum 10 5)
()
> (ordered-triple-sum 10 6)
((3 2 1 6))
> (ordered-triple-sum 12 12)
((5 4 3 12)
(6 4 2 12)
(6 5 1 12)
(7 3 2 12)
(7 4 1 12)
(8 3 1 12)
(9 2 1 12))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.