Exercises
Evaluation Order and Infinite Lists

The function list produces a list of some given elements.

Make a similar function stream that produces a stream of some given elements.

As an example, (stream 1 2 3 4 5) should produce the finite stream of 1, 2, 3, 4 and 5.

Make a stream of all factorial numbers: 1 2 6 24 120 ...

Please go for a recursive definition, in the same style as used for nat-nums and fib:

(define ones (cons-stream 1 ones))

(define nat-nums 
 (cons-stream 1 
  (add-streams ones nat-nums)))

(define fibs
  (cons-stream 0
    (cons-stream 1
      (add-streams (tail fibs) fibs))))

As part of the solution, you may need a multiplicative stream function similar to add-streams. For that purpose make a higher-order function, combine-streams, that combines two (infinite) streams with a binary function.

Here are all the necessary definitions you need to get started:

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define head car)

(define (tail stream) (force (cdr stream)))

(define empty-stream? null?)

(define the-empty-stream '())


(define (stream-section n stream)
  (cond ((= n 0) '())
        (else (cons (head stream)
              (stream-section 
                (- n 1)
               (tail stream))))))

(define (add-streams s1 s2)
 (let ((h1 (head s1))
       (h2 (head s2)))
   (cons-stream 
    (+ h1 h2)
    (add-streams (tail s1) (tail s2)))))


(define ones (cons-stream 1 ones))

(define nat-nums 
 (cons-stream 1 
  (add-streams ones nat-nums)))

We have seen a number of useful stream funtions, as counterparts to well-known list functions.

First, consider if/how to program a stream-append function, as a counterpart to append. Here is a possible recursive append function for lists:

  (define (my-append lst1 lst2)
    (cond ((null? lst1) lst2)
          (else (cons (car lst1) (my-append (cdr lst1) lst2)))))

How will your stream-append function work on infinite streams, such as nat-nums or fibs?

Now program a similar function, stream-merge, that merges two streams by simple alternation.

How will stream-merge function work on initinite streams? And on finite streams?

Can you use stream-merge to produce as stream of all integers (in some arbitrary order), based on two other streams with fixed starting points?

Here is all you need to get started:

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define head car)

(define (tail stream) (force (cdr stream)))

(define empty-stream? null?)

(define the-empty-stream '())

(define (stream-section n stream)
  (cond ((= n 0) '())
        (else (cons (head stream)
              (stream-section 
                (- n 1)
               (tail stream))))))

It is well-known that the square root function can be implemented by use of Newton's method. In case you need some background, you can consult this video.

If we need to find sqrt(x) based on an initial quess g, we can iteratively improve our guess by this simple function:

(define (improve-sqrt-guess guess x)
  (/ (+ guess (/ x guess)) 2))

Produce a stream of real numbers, starting with the initial guess 1.0, that will converge towards sqrt(x).

You may find the following stream variant of map useful:

  (define (map-stream f stream)
    (cond ((empty-stream? stream) the-empty-stream)
          (else (cons-stream (f (head stream)) (map-stream f (tail stream))))))

Here is all you need to get started:

(define (improve-sqrt-guess guess x)
 (/ (+ guess (/ x guess)) 2))

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define head car)

(define (tail stream) (force (cdr stream)))

(define empty-stream? null?)

(define the-empty-stream '())

(define (stream-section n stream)
  (cond ((= n 0) '())
        (else (cons (head stream)
              (stream-section 
                (- n 1)
               (tail stream))))))


(define (map-stream f stream)
  (cond ((empty-stream? stream) the-empty-stream)
        (else (cons-stream (f (head stream)) (map-stream f (tail stream))))))