Exercise index of this lecture   Alphabetic index   Course home   

Exercises and solutions
Evaluation Order and Infinite Lists


4.1   Finite streams * 

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.

Solution

(define (stream . element-list)
  (if (null? element-list)
      the-empty-stream
      (cons-stream (car element-list)
                   (apply stream (cdr element-list)))))

; Here is all necessary stream stuff:

(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 (combine-streams bin-fn s1 s2)
 (let ((h1 (head s1))
       (h2 (head s2)))
   (cons-stream 
    (bin-fn h1 h2)
    (combine-streams bin-fn (tail s1) (tail s2)))))

(define (constant-stream c)
  (cons-stream c (constant-stream c)))


4.2   A stream of factorial numbers ** 

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

Solution

; Works in Racket, with #lang racket.

(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 (combine-streams bin-fn s1 s2)
 (let ((h1 (head s1))
       (h2 (head s2)))
   (cons-stream 
    (bin-fn h1 h2)
    (combine-streams bin-fn (tail s1) (tail s2)))))

(define ones (cons-stream 1 ones))

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

(define facts
  (cons-stream 1 
              (combine-streams * (tail nat-nums) facts)))

(stream-section 10 facts)


4.3   Stream appending and stream merging ** 

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

Solution

(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 (merge-streams s1 s2)
 (cond ((empty-stream? s1) s2)
       ((empty-stream? s2) s1)
       (else (let ((h1 (head s1))
                   (h2 (head s2)))
               (cons-stream h1 
                            (cons-stream h2 (merge-streams (tail s1) (tail s2))))))))

; Inspiration: Jens Axel Soegaard.
(define (append-streams s1 s2)
  (cond
    ((empty-stream? s1) s2) 
    ((empty-stream? s2) s1)
    (else 
      (cons-stream (head s1) 
                   (append-streams (tail s1) s2)))))



; An integers stream:

(define (integers-with-lower-limit n)
 (cons-stream n 
  (integers-with-lower-limit (+ n 1))))

(define (integers-with-upper-limit n)
 (cons-stream n 
  (integers-with-upper-limit (- n 1))))

(define integers
  (cons-stream 0
    (merge-streams (integers-with-lower-limit 1)
                   (integers-with-upper-limit -1))))


4.4   A stream that converges to the square root a number ** 

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

Solution

Here is a possible solution:

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

(define (sqrt-stream x)
  (cons-stream
    1.0
    (map-stream (lambda (g) (improve-sqrt-guess g x))
                (sqrt-stream x))))

; An alternative definition of sqrt-stream, using the higher-order functions flip and curry2
(define (sqrt-stream-alternative x)
  (cons-stream 1 (map-stream ((curry2 (flip improve-sqrt-guess)) x) (sqrt-stream-alternative x))))

(define (curry2 f)
    (lambda(x)
      (lambda(y)
        (f x y))))

(define (flip f)
    (lambda (x y)
      (f y x)))

; Below we reproduce some of the basic stream functions, on which sqrt-stream depends.

(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))))))





Generated: Friday August 13, 2021, 14:52:01