# 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))
```

xdavidliu

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

Sphinxsky

```

(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