<< Previous exercise (3.68) | Index | Next exercise (3.70) >>

meteorgan + adams

I've made a small cleanup to meteorgan's code.  Cons is much more appropriate than append. -- adams

(define (triples s t u)
        (cons-stream (list 
                                        (stream-car s)
                                        (stream-car t) 
                                        (stream-car u))
                                        (stream-map (lambda (x) (cons (stream-car s) x))
                                                               (stream-cdr (pairs t u)))
                                        (triples (stream-cdr s)
                                                     (stream-cdr t)
                                                     (stream-cdr u)))))
(define (phythagorean-numbers)
        (define (square x) (* x x))
        (define numbers (triples integers integers integers))
        (stream-filter (lambda (x) 
                                                (= (square (caddr x)) 
                                                (+ (square (car x)) (square (cadr x)))))


The above solution requires many redundant computations of (pairs t u). Here's an alternative implementation that only computes (pairs t u) once. We construct the triples by consing all elements of s up to the corresponding first element in (pairs t u). For the case that t is not the integers, we compute (pairs integers integers) in order to keep track of how many elements of s "fit".

 (define first-of-integer-pair 
   (stream-map car (pairs integers integers))) 
 (define (triples s t u) 
   (let ((pairs-tu (pairs t u))) ;; compute pairs only *once* 
     (define (rec si i ptu top-i) 
        (cons (stream-car si) (stream-car ptu)) 
        (if (= i (stream-car top-i)) 
            (rec s 1 (stream-cdr ptu) (stream-cdr top-i)) 
            ;; restart s cycle with next ptu 
            (rec (stream-cdr si) (1+ i) ptu top-i)))) 
     (rec s 1 pairs-tu first-of-integer-pair))) 
 ;; example: pythagorean triples 
 (define triples-integers 
   (triples integers integers integers)) 
 (define (pythagorean? a b c) 
   (= (square c) 
      (+ (square a) (square b)))) 
 (define pythagorean-triples 
    (lambda (triple) 
      (apply pythagorean? triple)) 
 (stream-ref pythagorean-triples 0) ; (3 4 5) 
 (stream-ref pythagorean-triples 1) ; (6 8 10) 
 (stream-ref pythagorean-triples 2) ; (5 12 13) 
 (stream-ref pythagorean-triples 3) ; (9 12 15) 
 (stream-ref pythagorean-triples 4) ; (8 15 17) 

Note even with the above optimization of computing (pairs t u) only once, finding pythagorean triples is very slow: (8 15 17) is the 163813th item in the triples-integers stream.

Note also that it may be possible to skip computing first-of-integer-pair entirely, by inverting the result from exercise 3.66: z = (n-m+1/2) 2^m - 2, solving for m in terms of z; this would reduce complexity by a factor of 2


 (define (triples s t u) 
     (define p (pairs s t)) 
     (define (iter p now-u) 
         (let ((car-now-u (stream-car now-u)) 
               (car-p (stream-car p))) 
             (if (<= car-now-u (car car-p)) 
                     (cons car-now-u car-p) 
                     (iter p (stream-cdr now-u))) 
                 (iter (stream-cdr p) u)))) 
     (iter p u)) 
 (define pythagorean-triples 
         (lambda (triple) 
             (let ((t (map square triple))) 
                 (= (+ (car t) (cadr t)) (caddr t)))) 
         (triples integers integers integers))) 

In this way, you can only count the number calculated by xdavidliu, and then the memory overflows