Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.40

From Drewiki
Jump to: navigation, search

Problem

Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i, j) with <math>1 \le j < i \le n</math>. Use unique-pairs to simplify the definition of prime-sum-pairs given in the text.

Solution

Here are all of the definitions needed for the version of prime-sum-pairs given in the text:

(define nil (quote ()))
 
(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
 
(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))
 
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
 
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
 
(define (square x)
  (* x x))
 
(define (smallest-divisor n)
  (find-divisor n 2))
 
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
 
(define (divides? a b)
  (= (remainder b a) 0))
 
(define (prime? n)
  (= n (smallest-divisor n)))
 
(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))
 
(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
 
(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)))))

Here's a definition of unique-pairs that makes list pairs (instead of Scheme primitive pairs):

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

Test:

(unique-pairs 3)

Output:

((2 1) (3 1) (3 2))


And here's a simpler definition of prime-sum-pairs that uses unique-pairs:

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

Test:

(prime-sum-pairs 6)

Output:

((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

Personal tools