Lab 9 Lazy Streams

Purpose: See what happens if we evaluate things in a different order

Warmup

Make sure you’re using Advanced Student Lanugage. It might also help to go to the "Choose Language," click "Show Details," and make sure "Show sharing in values" is un-checked.

Streams look a bit like lists at first:

(require racket/stream)

; A [StreamOf X] is one of

; - empty-stream

; - (stream-cons X [StreamOf X])

; But there's some critical information

; missing from this data definition...

(define a-b-c-stream

(stream-cons 'a (stream-cons 'b (stream-cons 'c empty-stream))))

(check-expect (stream-first a-b-c-stream) 'a)

(check-expect (stream-first (stream-rest a-b-c-stream)) 'b)

There’s also an easier way to make streams, which works like list:

(define a-b-c-stream (stream 'a 'b 'c))

We can even turn streams into lists:

(check-expect (stream->list a-b-c-stream) '(a b c))

Of course, not all streams can be converted to lists:

(define minefield

(stream 1 2 3 4 5 (/ 6 0) 7))

; Don't run through the minefield

; (stream->list minefield)

(check-expect (stream-first minefield) 1)

We can look at elements of the stream without computing everything. In fact, we won’t actually compute any element until it’s requested.

(check-expect (stream-ref minefield 4) 5)

(check-expect (stream-ref minefield 6) 7)

; But don't ask for the 6th element!

(check-error (stream-ref minefield 5) "/: division by zero")

Exercise 1 Although list and cons are functions, stream and stream-cons are keywords like cond. Why is this?

Exercise 2 Design the function stream-repeat, which builds a stream that repeats the same value several times.

(check-expect (stream->list (stream-repeat 'a 4)) '(a a a a))

Exercise 3 Design the function stream-take, which builds a list from the first few elements from a stream.

(check-expect (stream-take (stream 'a 'b 'c 'd) 3) '(a b c))

There are some more analogous operations, which we’ll see later.

What is it good for?

Exercise 4 Figure out what this stream is. You can use your stream-take function to see the first few elements. How many elements does it have in total?

These streams are quite repetitive because ach use of stream-cons adds in something that already appeared in the original stream. Maybe we can make one that doesn’t repeat?

Exercise 5 Define a new stream, all-natural, that contains all the natural numbers in order. Remember what constructor makes a stream? How does the "rest" of all-natural relate to all-natural itself?

Exercise 6 Use stream-filter to make all-evens, a list of even natural numbers from all-natural.

Exercise 7 Use stream-map and all-natural to define all-evens-v2.

Exercise 8 Design a stream-sum function, which takes two streams and makes a stream with the sums of their respective elements.

(check-expect (stream-ref (stream-sum all-natural all-evens) 1) 3)

Exercise 9 Use stream-sum and all-natural to define all-evens-v3.

Exercise 10 Define a stream of the Fibonacci numbers. The first Fibonacci number is 0, and the second is 1. After that, each Fibonacci number is the sum of the previous number and the previous-previous number.

A stream of primes

Exercise 11 Design a function sieve that does that to a stream (you might want a divisible? helper function based on remainder.) Include this test case:

(define primes (sieve (stream-tail all-natural 2)))

(check-expect (stream-ref primes 50) 233)

Note: the implementation you come up with will probably be nice and elegant, but kinda slow. If you’re interested in a fast stream-based implementation, take a look at the short paper "The Genuine Sieve of Eratosthenes" by Melissa O’Neill.

Exercise 12 Finally, for the amusement value, design a function prime? which determines whether a number is prime by looking it up in the stream primes. You need to take advantage of the fact that it’s in ascending order!

A stream of successes

Now we’ll use the "stream of successes" technique described by Philip Wadler for solving backtracking problems without doing backtracking. Streams do the backtracking for you! Backtracking is used to solve problems where it’s possible to get stuck partway through and realize you made a mistake a while back. Here we’ll try it a couple simply problems involving building lists of numbers, for simplicity’s sake.

Exercise 13 Finish designing stream-replace-successes. (If you get stuck, the stream-append function might help you.)

We’re going to build "paths" through a "maze" of numbers, but we build the solutions "backwards" because it’s easier to add things to the beginning of a list.

Each problem will be represented by a "pool," which is a list of all possible numbers we can use in a path, and an "is-okay?" function, which says whether a particular number can be added to the front of a particular list.

(define (number-maze-is-okay? new others)

(cond

[(empty? others) (= new 0)]

[else

(or (= 2 (- new (first others)))

(= 7 (- (first others) new)))]))

(define number-maze-pool '(0 2 4 6 8 10 12 -7 -5 -12 -10 -8 -17))

So each step in a path is allowed to go up 2 or down 7, or in our backwards view, the previous location must be 2 less than the new one OR 7 more than the new one.

Where can we get when we start from 0? One solution of length 2 with the above problem is '(2 0).

Exercise 14 What is the other solution of length 2?

Exercise 15 What are three solutions of length 3?

Now think about how to use stream-replace-successes. What kind of argument do you want to give it? (Hint: make sure it agrees with the signature!)

Exercise 16 Design valid-subsequence-one-step, which takes a pool, an is-okay function, and a stream of possible paths through the maze, and turns the crank one step (i.e., it finds all paths that are one step further along than the given ones).

Exercise 17 Almost there! Design a function valid-subsequence which is like your previous function, but instead of taking a stream of current possibilities, it takes a target length, and recursively finds all the solutions of that length. In our number maze, you should find that there are 5 solutions of length 6, but only 1 solution of length 7.

Done already?

Exercise 18 stream-fold is available, but it isn’t very useful. Why not? Can you explain, just based on its contract, why it can never work on infinite streams?

Exercise 19 Look back at the "turtle" lab (#3). Every program there had to end when it ran out of instructions in its "world," but now we can make a world that never runs out of instructions. Remake this big-bang program to use a stream of commands instead of a list of commands.

; Move once, turn, move twice, turn, and so on

; Natural -> [StreamOf ACommand]

(define (inf-spiral/h len)

(stream-cons 'turn-right

(stream-append (stream-repeat 'move len)

(inf-spiral/h (add1 len)))))

; [StreamOf ACommand]

(define inf-spiral (inf-spiral/h 1))

Exercise 20 Try using the stream-of-successes technique on your old "missionaries and cannibals" homework.

Exercise 21 stream-cons is a syntactic form, not a function, but Racket gives programmers the power to write their own syntactic forms. Use define-syntax-rule to write your own implementation of stream-cons, called my-stream-cons. Define associated my-stream-first and my-stream-rest functions. You may find delay and force useful. Be sure to (require racket/base).