Weighting function

It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56 , if we define a way to say that one pair of integers is ''less than'' another. One way to do this is to define a ''weighting function'' W(i, j) and stipulate that (i₁, j₁) is less than (i₂, j₂) if W(i₁, j₁) ≤ W(i₂, j₂) . Write a procedure merge-weighted that is like merge , except that it takes an additional argument weight , which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream. Using merge-weighted , generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs , ordered according to weight. Use your procedure to generate

a. the stream of all pairs of positive integers (i, j) with i ≤ j ordered according to the sum i + j .

b. the stream of all pairs of positive integers (i, j) with i ≤ j , where neither i nor j is divisible by 2 , 3 , or 5 , and the pairs are ordered according to the sum 2i + 3j + 5ij .


There are no comments yet.

Authentication required

You must log in to post a comment.

Login
(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc . list-of-stream)
    (if (null? (car list-of-stream))
        '()
        (cons-stream
            (apply proc 
                   (map (lambda (s)
                            (stream-car s))
                        list-of-stream))
            (apply stream-map 
                   (cons proc (map (lambda (s)
                                       (stream-cdr s))
                                   list-of-stream))))))


(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define ones (cons-stream 1 ones))

(define integers (cons-stream 1 (add-streams ones integers)))

(define nat-stream-1 (weighted-pairs integers integers +))

(check-equal? (stream-ref nat-stream-1 0) '(1 . 1))
(check-equal? (stream-ref nat-stream-1 1) '(1 . 2))
(check-equal? (stream-ref nat-stream-1 2) '(1 . 3))
(check-equal? (stream-ref nat-stream-1 3) '(2 . 2))
(check-equal? (stream-ref nat-stream-1 4) '(1 . 4))
(check-equal? (stream-ref nat-stream-1 5) '(2 . 3))

(define nat-stream-2
  (weighted-pairs integers integers
                  (lambda (i j) (+ (* 2 i) (* 3 j) (* 5 i j)))))

(check-equal? (stream-ref nat-stream-2 0) '(1 . 1))
(check-equal? (stream-ref nat-stream-2 1) '(1 . 2))
(check-equal? (stream-ref nat-stream-2 2) '(1 . 3))
(check-equal? (stream-ref nat-stream-2 3) '(2 . 2))
(check-equal? (stream-ref nat-stream-2 4) '(1 . 4))
(check-equal? (stream-ref nat-stream-2 5) '(1 . 5))