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