Monday, May 30, 2011

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
(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?
(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)
(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)
> (triple-sum? (list 1 2 3) 6)

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


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


Berkeley's Organizing For America said...

I really enjoy reading this blog. It really help to clarify some of the strategy for solving Nested Mapping problem in SICP. Great post, Bill.

Bill the Lizard said...

Berkeley's Organizing For America,

Thank you! I really appreciate the feedback.

Anonymous said...

There's also append-map

Pierre De Pascale said...

There is a big difference between the Pseudo-code given early involving the nesting of the for and the functionnal implementation described after: the space complexity is not the same.

For example the enumerate-interval procedure first builds the list of integers. If the interval is large, it may not be efficient.

This is one of the drawback of a functional solution involving map, accumulate, filter...

If you go the route of list-comprehension as described in SRFI-42. you don't have this space problem.

Jonathan Milgrom said...

I've been going through SICP and your blog has been a great resource, thanks! I noticed there may be a mistake in the text, which you've copied over here. The call to flatmap in prime-sum-pairs maps a list of integers to a list of (list i j), which then gets filtered through the predicate prime-sum?. The problem is prime-sum? is expecting a pair to be constructed with (cons i j), not (list i j), and so it adds (+ (car pair) (cdr pair)) when it should be performing (+ (car pair) (car (cdr pair))).

Do you agree? I can't find any documentation of this mistake anywhere.

Jonathan Milgrom said...

Nevermind! whoops, I see that its cadr (not cdr) now