Homework 8: Fun with streams

In this homework we will be working with streams. A stream is a data structure made possible by a new version of cons called stream-cons, which does not evaluate its arguments. Thus a stream consists of a head element, which can be accessed using the stream-first procedure and a tail which can be accessed via the stream-rest procedure.

The elements of the stream are not evaluated until the stream-first and stream-rest procedures force them.

You can think of streams as infinite lists which are manipulated with stream-cons, stream-first, and stream-rest in much the same way as finite list are manipulated with cons, first, and rest.

The Racket documentation describes the various stream procedures you can use.

Here are a few examples.

#lang racket

(require racket/stream)

(define (stream-add s t)
  (cond [(stream-empty? s) empty-stream]
        [(stream-empty? t) empty-stream]
        [else (stream-cons (+ (stream-first s) (stream-first t))
                           (stream-add (stream-rest s) (stream-rest t)))]))

(define (integers-from n)
  (stream-cons n (integers-from (add1 n))))
(define ints (integers-from 0))
(define evens (stream-map (λ (n) (* 2 n)) ints))
(define ones (stream-cons 1 ones))
(define odds (stream-add ones evens))

(stream->list (stream-take ones 10))
(stream->list (stream-take odds 20))

For each exercise, write the function and a test suite and add the test suite to the all-tests test suite. You might want to write the tests first. If you’ve forgotten how to write tests, consult homework 1.

Preliminaries

Click on the assignment link and choose the same team as the previous assignment.

Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instruction and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style from the first homework.

Be sure to ask any questions on Piazza.

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should contain the following files

• hw8.rkt
• keyboard.rkt
• tests.rkt

It may also a .gitignore file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the main branch. (You’re free to make other branches, if you desire, but make sure main contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

Part 1. Streams

You may wish to test your implementations on the infinite stream

(define test-stream
  (stream-cons 'x (stream-cons 'y (stream-cons 'z test-stream))))

You can use stream-take and stream->list to compare initial portions of the streams to lists.

1. Write the function (stream-remove-all x s) which returns a stream with all occurrences of x removed from the stream s.
2. Write the function (stream-replace x y s) which returns a stream with all occurrences of x in the stream s replaced with y.

Part 2. Mathematical Streams

A good way to produce streams of numbers is to write a function which produces the next number in the stream given the current number. That is the technique used above in integers-from: A call to (integers-from n) does a stream-cons of n onto a recursive call to integers-from passing it the next number (add1 n).

Here is a challenge. Consider the following grid of pairs of numbers.

Note that we can create (a . b) with (cons a b). Of course, it is easy to make the first row of this grid as a stream, but if we try to print the grid row-by-row we will never finish with the first row. A better approach is to enumerate the elements diagonally. The first diagonal (right-to-left) contains only (1 . 1) The next diagonal contains (1 . 2) and (2 . 1) The next (1 . 3), (2 . 2), and (3 . 1), and so forth.

We can define this stream of pairs pretty easily, the same way we define our stream of integers.

(define (pairs-from p)
  (stream-cons p (pairs-from (next-pair p))))

(define all-pairs (pairs-from (cons 1 1)))

Of course, there’s a missing piece here which you’ll write in the next exercise.

3. Write procedure (next-pair p) that takes one of the pairs for this enumeration and returns the next pair. If p is the last pair for the current diagonal, move on to the next diagonal.
   • (next-pair (cons 1 1)) returns '(1 . 2)
   • (next-pair (cons 4 3)) returns '(5 . 2)
   • (next-pair (cons 6 1)) returns '(1 . 7)
4. 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 ham and notice the following facts about it.
   • ham begins with 1;
   • the elements of (stream-map (λ (n) (* 2 n)) ham) are all elements of ham;
   • the elements of (stream-map (λ (n) (* 3 n)) ham) are all elements of ham; and
   • the elements of (stream-map (λ (n) (* 5 n)) ham) are all elements of ham.

   Write the procedure (stream-merge s1 s2) which combines two ascending streams of numbers into a single stream, eliminating repetitions.

   Construct the stream ham. Here are the first 40 elements of ham.

   > (stream->list (stream-take ham 40))
   '(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50
     54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144)
   

Make sure you write tests for these.

Part 3. Power series

Streams can be used to model the power series that define important mathematical functions. Among these are the following that compute the exponential, sine and cosine functions. $\begin{aligned} e^x &= 1+x+\frac{x^2}{2}+\frac{x^3}{3\cdot2}+\frac{x^4}{4\cdot3\cdot2}+\cdots\\ \sin x &= x - \frac{x^3}{3\cdot 2} + \frac{x^5}{5\cdot4\cdot3\cdot2} - \cdots\\ \cos x &= 1 - \frac{x^2}{2} + \frac{x^4}{4\cdot3\cdot2} - \cdots\\ \end{aligned}$

If we create streams for the coefficients $\begin{aligned} \texttt{e-coeffs} &= (1/0!\quad 1/1!\quad 1/2!\quad 1/3!\quad 1/4!\quad 1/5!\quad 1/6!\quad \dots)\\ \texttt{sin-coeffs} &= ( 0\quad 1/1!\quad 0\quad -1/3!\quad 0\quad 1/5!\quad 0\quad \dots)\\ \texttt{cos-coeffs} &= ( 1\quad 0\quad -1/2!\quad 0\quad 1/4!\quad 0\quad -1/6!\quad \dots)\\ \end{aligned}$ and computes the powers of x as a stream, $(\texttt{powers}\ x) = (1\quad x^2\quad x^3\quad x^4\quad \dots)$ then we can calculate the partial sums for the power series. A partial sum for a sequence is the sum of the first $n$ terms of the sequence. For the sequence $a\ b\ c\ d\ \dots$, the partial sums are $a$, $a+b$, $a+b+c$, $a+b+c+d$, and so on.

We can write a procedure to make the stream of partial sums of the stream s.

(define (stream-add s t)
  (cond [(stream-empty? s) empty-stream]
        [(stream-empty? t) empty-stream]
        [else
         (stream-cons (+ (stream-first s)
                         (stream-first t))
                      (stream-add (stream-rest s)
                                  (stream-rest t)))]))

(define (partial-sums s)
  (cond [(stream-empty? s) empty-stream]
        [else
         (letrec ([sums (stream-add s (stream-cons 0 sums))])
           sums)]))

At this point, (partial-sums (stream-mul (powers x) sin-coeffs)) gives increasingly good approximations to $\sin(x)$ and the others act similarly.

To define these streams, start by building the stream of factorials. Implement stream-mul similarly to stream-add above.

To define the stream of factorials, fact-stream, notice that if we multiple fact-stream by (integers-from 1) we get the following.

  fact-stream       = 1    1    2*1    3*2*1    4*3*2*1  ...
* (integers-from 1) = 1    2      3        4          5  ...
------------------------------------------------------------
                      1  2*1  3*2*1  4*3*2*1  5*4*3*2*1  ...

That last line is just (stream-rest fact-stream). Consequently, we can define fact-stream recursively as

(define fact-stream
  (stream-cons 1 (stream-mul fact-stream (integers-from 1))))

At this point, we can build the power series. The e-coeffs stream can be built as

(define e-coeffs
  (stream-map (λ (n) (/ 1.0 n)) fact-stream))

and a stream of partial sums for the approximation of $e^x$ as

(define (e-approx x)
  (partial-sums (stream-mul (powers x) e-coeffs)))

For example, (stream->list (stream-take (e-approx 1) 5)) gives

'(1 2.0 2.5 2.6666666666666665 2.708333333333333)

And now for your task.

5. Produce the streams $\begin{aligned} \texttt{sin-coeffs} &= ( 0\quad 1/1!\quad 0\quad -1/3!\quad 0\quad 1/5!\quad 0\quad \dots)\\ \texttt{cos-coeffs} &= ( 1\quad 0\quad -1/2!\quad 0\quad 1/4!\quad 0\quad -1/6!\quad \dots)\\ \end{aligned}$
6. Define sin-approx and cos-approx similarly to e-approx.

Part 4. Filtering

The file keyboard.rkt has the procedure (keyboard-stream) which returns a stream of whatever s-expressions you type. There is also an (output-stream s) procedure that takes a stream and outputs it one element at a time. Together these set up a communication channel.

(output-stream (keyboard-stream))

This echoes whatever you type, and continues until you click on the eof box at the right. We will use this in the next set of exercises having to do with Grune’s Problem.

There is a famous problem due to Grune that is important in data communications. Consider a stream of characters, which we will model by typing single characters followed by a carriage-return in response to (keyboard-stream)’s prompts. Most characters we will be allowed to pass through unaltered. But if we ever receive two as in a row, then we will pass through just a single b and no a.

7. Write the filter grune-a-b that works as described above. For example,

   > (output-stream (grune-a-b (keyboard-stream))) 
   ? a 
   ? b 
   a 
   b 
   ? c 
   c 
   ? d 
   d 
   ? a 
   ? a 
   b 
   ? a 
   ? b 
   a 
   b 
   ? a 
   ? a 
   b 
   ? <click eof> 
   

   You can test using lists as your input stream and stream->list to convert the result to a list. For example, the above sequence of input can be tested by checking that

   (stream->list (grune-a-b '(a b c d a a a b a a)))
   

   returns

   '(a b c d b a b b)
   

   Similarly, the input stream '(a a a) should produce the output stream '(b a).

8. Now write a similar function, but abstract the a and b. Write a procedure (grune a b) which takes two arguments and produces a filter similar to grune-a-b but with the first argument taking the role of a and the second taking the role of b.

   (grune 'x 'y) needs to return a procedure, similar to grune-a-b which works as a stream filter replacing two successive x by a single y. Here is a transcript of grune in action.

   > (output-stream ((grune 'x 'y) (keyboard-stream))) 
   ? a 
   a 
   ? b 
   b 
   ? c 
   c 
   ? d 
   d 
   ? x 
   ? y 
   x 
   y 
   ? a 
   a 
   ? b 
   b 
   ? x 
   ? x 
   y 
   ? x 
   ? x 
   y 
   ? a 
   a 
   ? b 
   b 
   ? <click eof> 
   

   Notice that ((grune 'a 'b) s) has the same functionality as (grune-a-b s). Grune’s problem becomes interesting when we consider pipelining several Grune operations. If you did the last exercise correctly, you should be able to chain several grunes together.

   > (output-stream ((grune 'c 'd) ((grune 'b 'c) ((grune 'a 'b) (keyboard-stream)))))
   ? a 
   ? b 
   a 
   ? c 
   b 
   ? d 
   c 
   d 
   ? e 
   e 
   ? f 
   f 
   ? g 
   g 
   ? a
   ? a 
   ? a 
   ? a 
   ? a 
   ? a 
   ? a 
   ? a 
   d 
   ? a 
   ? a 
   ? a 
   ? a 
   ? x 
   c 
   x 
   ? y 
   y 
   ? z 
   z 
   ? x 
   x 
   ? y 
   y 
   ? z 
   z 
   ? <click eof> 
   

   If you want, you can replace your definition of grune-a-b with

   (define grune-a-b (grune 'a 'b))
   

Congratulations, you have completed all of the homework for CS 275! You’ve learned an awful lot of new material this semester, including an entirely new way to think about programming. Even if you never again find yourself writing Racket code, this knowledge of functional programming will serve you well.