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

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.

## 4 comments:

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.

Berkeley's Organizing For America,

Thank you! I really appreciate the feedback.

There's also append-map

http://api.call-cc.org/doc/srfi-1/append-map

There is a big difference between the Pseudo-code given early involving the nesting of the

forand the functionnal implementation described after: the space complexity is not the same.For example the

enumerate-intervalprocedure 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.

Post a Comment