Description
This laboratory assignment asks you to solve some programming puzzles that involve streams. As discussed in the lectures, a stream is an ordered sequence of elements, implemented using a function closure. Although a stream may have an ‘‘infinite’’ number of elements, only a finite number of those elements are ever computed, and they are computed only as they are needed.
1. Theory.
In the lectures, a stream was implemented as an Ocaml tuple ((this, state), next) where this is the first element of the stream, and state is an object that is used to compute the remaining elements of the stream. The function next takes this and state as its arguments, and uses them to compute another Ocaml tuple (this′, state′) that is part of a new stream.
The function makeStream makes a new stream. The function first returns the first element of a stream it’s given. It’s analogous to hd for lists. The function rest returns a new stream that is like a stream it’s given, but without its first element. It’s analogous to tl for lists.
let makeStream this state next =
((this, state), next) ;;
let first ((this, state), next) =
this ;;
let rest ((this, state), next) =
(next this state, next) ;;
Note that OCaml functions can use pattern matching in their parameter lists, just as match–with does.
2. Examples.
For example, we can use makeStream to construct an infinite stream of factorials. Its first element is 1 and its state is 1. The state records the largest factorial computed by the stream so far.
let factorials =
makeStream 1 1 (fun this state -> (this ∗ state, state + 1)) ;;
We can then use first and rest on the stream factorials to obtain its members (the arrow ‘⇒’ means returns). Streams are immutable, so the stream factorials remains unchanged.
first factorials
⇒
1 first (rest factorials)
⇒
1 first (rest (rest factorials))
⇒
2 first (rest (rest (rest factorials)))
⇒
6 first (rest (rest (rest (rest factorials))))
⇒
24 ⋮
We can also define a function take that returns the first count elements of a stream, but as a list. It uses first and rest in the same way as above.
let rec take count stream =
match count
with 0 -> [] |
_ -> first stream :: take (count − 1) (rest stream) ;;
As a result, take 10 factorials returns [1; 1; 2; 6; 24; 120; 720; 5040; 40320; 362880], a list of the first ten factorials. It’s more interesting, however, to write functions that take streams as arguments and return new streams as values. Such functions effectively operate on infinitely large data structures, but in finite space and time.
3. Implementation.
For this laboratory assignment, you must write OCaml code for the following.
- odds
Make a stream of odd integers: 1, 3, 5, 7 … Let the name odds be bound to this stream. Hint: call makeStream and use let.
- trim count stream
Define a function trim that returns a new stream like stream, but without its first count elements. For example, trim 5 odds must return a stream like odds, but without its first five elements, so it contains 11, 13, 15, 17 … Hint: write a recursion that uses rest.
- scale factor stream
Define a function scale that returns a new stream of integers that is like stream, but in which each integer is multiplied by factor. The function scale must run in O(1) time. For example, scale 2 odds must return a stream containing 2, 6, 10, 14 … Hint: use makeStream, and have the new stream’s state be a stream computed from stream.
- sum left right
Define a function sum that takes two streams of integers left and right as its arguments. The function sum must return a new stream whose nth element is obtained by adding the nth elements of left and right, where n ≥ 1. The function sum must run in O(1) time. For example, if ones is a stream containing 1, 1, 1, 1 …, then sum ones odds must return a stream containing 2, 4, 6, 8 … Hint: use makeStream, and have the new stream’s state be a 2-tuple of streams, one computed from left, and the other computed from right.
Some things you need to know for this laboratory assignment have not yet been discussed in lectures. This is because our labs meet at the beginning of the week. In a perfect world (this isn’t one) the labs would meet at the end of the week, after everything had been explained. If you don’t know how to do parts of this assignment, don’t worry. Wait for the next lecture.
4. Deliverables.
The file tests6.ml contains some tests, worth 30 points. Insert your code into this file and then run it with OCaml. When you think your code is correct, submit the file with your code in it. It must be submitted to Canvas by 11:55 PM on Tuesday, October 26, 2021. If you do not know how and where to submit your work, then please ask your lab TA’s.
