1
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.