By jaresty


2011-04-13 06:06:33 8 Comments

From the section called Nested Mappings

Exercise 2.40

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.

I wrote the following:

(define (prime-sum-pairs n)
  (filter (lambda (seq)
            (prime? (+ (car seq) (cadr seq))))
          (unique-pairs n)))

(define (enumerate-integers start end)
  (if (>= start end)
      (list end)
      (cons start (enumerate-integers (+ 1 start) end))))

(define (unique-pairs n)
  (flat-map (lambda (i) 
              (map (lambda (j) (list i j)) 
                   (enumerate-integers 1 (- i 1))))
            (enumerate-integers 2 n)))

(define (filter test-fn seq)
  (if (null? seq) null
      (if (test-fn (car seq)) 
          (cons (car seq)                    
                (filter test-fn (cdr seq)))
          (filter test-fn (cdr seq)))))


(define (accumulate op initial seq)
  (if (null? seq)
      initial
      (op (car seq)
          (accumulate op initial (cdr seq)))))

(define (flat-map f seq)
  (accumulate append
              null
              (map (lambda (x) (f x)) seq)))

(define (prime? n) (= (smallest-divisor n) n))
(define (divisible? n i) (= 0 (remainder n i)))
(define (square x) (* x x))
(define (smallest-divisor n)
  (define (rec i)
    (cond ((> n (square i)) n)
          ((divisible? n i) i)
          (else (rec (+ 1 i)))))
  (rec 2))

Can this be improved in any way?

1 comments

@antti.huima 2011-04-15 01:35:05

Your code

(define (enumerate-integers start end)
  (if (>= start end)
      (list end)
      (cons start (enumerate-integers (+ 1 start) end))))

(define (unique-pairs n)
  (flat-map (lambda (i) 
              (map (lambda (j) (list i j)) 
                   (enumerate-integers 1 (- i 1))))
            (enumerate-integers 2 n)))

looks fine to me. If you want to massage some details, you could rewrite enumerate-integers e.g. to:

(define (enumerate-integers start end)
  (if (> start end) '()
      (cons start (enumerate-integers (+ 1 start) end))))

which is cleaner because you don't have (list end) as a special case, and you can correctly produce an empty list of integers if start > end.

If you want to be even cleaner, you can do:

(define (enumerate-integers start end)
  (define (iter n)
    (if (> n end) '()
        (cons n (iter (+ n 1)))))
  (iter start))

This is a good pattern in case of more complex procedures.

Your flat-map is more complex than needed, your code:

(define (flat-map f seq)
  (accumulate append
              null
              (map (lambda (x) (f x)) seq)))

can be replaced with:

(define (flat-map f seq)
  (accumulate append
              null
              (map f seq)))

because (lambda (x) (f x)) is equal to f.

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] Generating all unique permutations of a string

0 Answered Questions

1 Answered Questions

[SOLVED] Producing a deep-reverse procedure

  • 2011-04-07 04:33:34
  • jaresty
  • 913 View
  • 0 Score
  • 1 Answer
  • Tags:   lisp scheme sicp

0 Answered Questions

Correctly count the number of pairs in an irregular list structure

  • 2011-05-20 03:01:13
  • jaresty
  • 568 View
  • 1 Score
  • 0 Answer
  • Tags:   lisp scheme sicp

1 Answered Questions

[SOLVED] Represent pairs of nonnegative integers using 2^a * 3^b

  • 2011-04-04 01:40:50
  • jaresty
  • 309 View
  • 2 Score
  • 1 Answer
  • Tags:   lisp scheme sicp

2 Answered Questions

[SOLVED] Design a procedure to reverse a list

0 Answered Questions

Representing a queue as a procedure with local state

  • 2011-05-20 07:06:19
  • jaresty
  • 174 View
  • 4 Score
  • 0 Answer
  • Tags:   lisp scheme sicp

2 Answered Questions

[SOLVED] Write a procedure stream-limit that finds

  • 2011-06-27 01:58:06
  • jaresty
  • 169 View
  • 7 Score
  • 2 Answer
  • Tags:   lisp scheme sicp

Sponsored Content