# Homework 8: Fun with streams

**Due: 2020-12-07 at 23:59**

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.

- Write the function
`(stream-remove-all x s)`

which returns a stream with all occurrences of`x`

removed from the stream`s`

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

(1 . 1) | (1 . 2) | (1 . 3) | (1 . 4) | (1 . 5) | (1 . 6) | (1 . 7) | … |

(2 . 1) | (2 . 2) | (2 . 3) | (2 . 4) | (2 . 5) | (2 . 6) | (2 . 7) | … |

(3 . 1) | (3 . 2) | (3 . 3) | (3 . 4) | (3 . 5) | (3 . 6) | (3 . 7) | … |

(4 . 1) | (4 . 2) | (4 . 3) | (4 . 4) | (4 . 5) | (4 . 6) | (4 . 7) | … |

(5 . 1) | (5 . 2) | (5 . 3) | (5 . 4) | (5 . 5) | (5 . 6) | (5 . 7) | … |

(6 . 1) | (6 . 2) | (6 . 3) | (6 . 4) | (6 . 5) | (6 . 6) | (6 . 7) | … |

(7 . 1) | (7 . 2) | (7 . 3) | (7 . 4) | (7 . 5) | (7 . 6) | (7 . 7) | … |

⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ |

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.

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

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

- 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}$
- 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 `a`

s in a row, then we will pass through just a single `b`

and no `a`

.

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

. 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`grune`

s 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.