sicp-ex-3.67



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


3pmtea

The table can still be divided into 3 parts:

;;

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) t))))

(define (pairs s t)
  (define (top ts tt)
    (cons-stream
     (list (stream-car ts) (stream-car tt))
     (interleave
      (stream-map (lambda (x) (list (stream-car ts) x))
                  (stream-cdr tt))
      (pairs (stream-cdr ts) (stream-cdr tt)))))

  (define (below bs bt)
    (cons-stream
     (list (stream-car bs) (stream-car bt))
     (interleave
      (stream-map (lambda (x) (list (stream-car bt) x))
                  (stream-cdr bs))
      (pairs (stream-cdr bs) (stream-cdr bt)))))
  (interleave (top s t)
              (below (stream-cdr s) t)))


(define (all-pairs s t)
        (cons-stream 
                (list (stream-car s) (stream-car t))
                (interleave
                        (interleave
                                (stream-map (lambda (x) (list (stream-car s) x))
                                                        (stream-cdr t))
                                (all-pairs (stream-cdr s) (stream-cdr t)))
                        (stream-map (lambda (x) (list x (stream-car t)))
                                                (stream-cdr s)))))

@genovia I took a look at your answer and I think it would repeat pairs, I found the pair (1,3) repeated at least.

Here's my solution, I think it should work, it is similar to @meteorgan answer.

(define (pairs s t)
        (cons-stream 
                (list (stream-car s) (stream-car t))
                (interleave
                        (interleave
                                (stream-map (lambda (x) (list (stream-car s) x))
                                                        (stream-cdr t))
                                (stream-map (lambda (x) (list x (stream-car s)))
                                                        (stream-cdr t)))
                        (pairs (stream-cdr s) (stream-cdr t)))))


Use the same logic as the table diagram in the book: the stream now consists of *four* parts, not three, the upper-left corner, the top row, a new "left column", and the lower-right block

 (define (all-pairs s t) 
   (cons-stream 
    (list (stream-car s) (stream-car t)) ;; upper-left corner 
    (interleave 
     (interleave 
      (stream-map (lambda (x) (list (stream-car s) x)) 
                  (stream-cdr t)) ;; top row 
      (stream-map (lambda (x) (list x (stream-car t))) 
                  (stream-cdr s))) ;; left column 
     (all-pairs (stream-cdr s) (stream-cdr t))))) ;; lower-right block 
  
 (define (partial-stream->list stream n) 
   (define (rec str i) 
     (if (= i n) 
         () 
         (cons (stream-car str) 
               (rec (stream-cdr str) (1+ i))))) 
   (rec stream 0)) 
 ;; utility function to return list of first n items 
  
 (partial-stream->list (all-pairs integers integers) 10) 
 ;; ((1 1) (1 2) (2 2) (2 1) (2 3) (1 3) (3 3) (3 1) (3 2) (1 4)) 

My answer is similar to 3pmtea's answer. What do you guys think of it?

I'm also curious to know, I don't see any reason to make it so complicated. The start of the stream is (1,1), after that an interleaving of (1,x) and ((2,1) and interleaving of (2,x) and ((3,1) and interleaving of (3,x) etc ...

Won't such a stream contain all pairs?

Just by examining output of solution given by 3pmtea, it looks correct.