SICP Goodness - Stream (6)

Infinite Streams

4 minute read

Do you think Computer Science equals building websites and mobile apps?

Are you feeling that you are doing repetitive and not so intelligent work?

Are you feeling a bit sick about reading manuals and copy-pasting code and keep poking around until it works all day long?

Do you want to understand the soul of Computer Science?

If yes, read SICP!!!

Let’s do some exercises.

Exercise 3.53: Without running the program, describe the elements of the stream defined by 

(define s (cons-stream 1 (add-streams s s)))

This is an easy one. Let me illustrate the answer below.

;; The stream starts with 1
1 . . . ...

;; The rest of the stream is by adding it to itself
  1 . . . ...
1 . . . . ...
  1 . . . ...
  
;; Now we know the second value in the stream is 2
  1 2 . . ...
1 2 . . . ...
  1 2 . . ...

;; Now we know the third value is 4
  1 2 4 . ...
1 2 4 . . ...
  1 2 4 . ...
  
;; The stream is 1 2 4 8 16 32 ...

Exercise 3.54: Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n+1 factorial:

(define factorials 
  (cons-stream 1 (mul-streams ⟨??⟩ ⟨??⟩)))

The anwser is also not hard to find.

(define (mul-streams s1 s2)
  (stream-map * s1 s2))

(define factorials
  (cons-stream 1 (mul-streams factorials (stream-cdr integers))))

The answer can be illustrated as follows.

;; the final stream is
1! 2! 3! 4! 5! . . . 

;; which can be rewritten as
1 1!x2 2!x3 3!x4 4!x5 . . .

;; note that the cdr of the stream can be viewed as the multiplication of two streams
1! 2! 3! 4! 5! ... ;; this is the final stream itself
2  3  4  5  6  ... ;; this is the integer stream starting from 2

Exercise 3.55: Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S0, S0+S1, S0+S1+S2, … For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, …

Got the hang of this game? OK, the answer:

(define (partial-sum s)
  (cons-stream (stream-car s)
               (add-streams (stream-cdr s)
                            (partial-sum s))))

Let’s also illustrate this:

;; S      = S0    S1      S2           S3            ...
;; Result = S0    S0+S1   S0+S1+S2     S0+S1+S2+S3   ...

Squeeze your eyes and you should see the pattern.

Exercise 3.56: A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.

  • S begins with 1.
  • The elements of (scale-stream S 2) are also elements of S.
  • The same is true for (scale-stream S 3) and (scale-stream S 5).

These are all the elements of S. Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:

(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream 
                   s1car 
                   (merge (stream-cdr s1) 
                          s2)))
                 ((> s1car s2car)
                  (cons-stream 
                   s2car 
                   (merge s1 
                          (stream-cdr s2))))
                 (else
                  (cons-stream 
                   s1car
                   (merge 
                    (stream-cdr s1)
                    (stream-cdr s2)))))))))

Then the required stream may be constructed with merge, as follows:

(define S (cons-stream 1 (merge ⟨??⟩ ⟨??⟩)))

Fill in the missing expressions in the places marked ⟨??⟩ above.

This exercise looks daunting, but it is the easiest one. I include this one mainly for the introduction of the merge function.

(define S (cons-stream 1 (merge (merge (scale-stream S 2) (scale-stream S 3)) (scale-stream S 5))))

By now, I could not understand fully how all these would eventually work out. I mean the laziness combined with recursion. We are at a point that by simply writing down the correct formula is not enough to know if the program will make sense and run.

comments powered by Disqus