sicp-ex-3.69

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))
                (interleave
                        (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)))))
                                numbers))

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 
        (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 
   (stream-filter 
    (lambda (triple) 
      (apply pythagorean? triple)) 
    triples-integers)) 
  
 (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-stream 
                     (cons car-now-u car-p) 
                     (iter p (stream-cdr now-u))) 
                 (iter (stream-cdr p) u)))) 
     (iter p u)) 
  
 (define pythagorean-triples 
     (stream-filter 
         (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

Slight improvement on meteorgan's solution:

 (define (triples s t u) 
   (cons-stream 
     (list (stream-car s) (stream-car t) (stream-car u)) 
     (interleave 
       (stream-map (lambda (x) (cons (stream-car s) x)) 
                   (pairs (stream-cdr t) (stream-cdr u))) 
       (triples (stream-cdr s) (stream-cdr t) (stream-cdr u))))) 
  
 (define (sq x) (* x x)) 
  
 (display-stream 
   (stream-filter 
     (lambda (x) 
       (= (+ (sq (list-ref x 0)) (sq (list-ref x 1))) 
          (sq (list-ref x 2)))) 
     (triples integers integers integers))) 

Computing pairs on the cdrs of t and u avoids redundant entries.