<![CDATA[
# Streams and Laziness
In this lab, we will dive into a couple implementations of
the infinite list data structure that we saw in lecture.
## Streams
In lecture we defined this type:
```
type 'a stream =
Cons of 'a * (unit -> 'a stream)
```
The next few exercises ask you to work with that type.
##### Exercise: pow2 [✭✭]
Define a value `pow2 : int stream` whose elements are the powers
of two: `<1; 2; 4; 8; 16, ...>`.
□
##### Exercise: nth [✭✭]
Define a function `nth : 'a stream -> int -> 'a`, such that
`nth s n` the element at zero-based position `n` in stream `s`.
For example, `nth pow2 0 = 1`, and `nth pow2 4 = 16`.
□
##### Exercise: filter [✭✭✭]
Define a function `filter : ('a -> bool) -> 'a stream -> 'a stream`,
such that `filter p s` is the sub-stream of `s` whose elements
satisfy the predicate `p`. For example, `filter (fun n -> n mod 2 = 0) nats`
would be the stream `<0; 2; 4; 6; 8; 10; ...>`. If there is no
element of `s` that satisfies `p`, then `filter p s` does not terminate.
□
##### Exercise: interleave [✭✭✭]
Define a function `interleave : 'a stream -> 'a stream -> 'a stream`,
such that `interleave <a1; a2; a3; ...> <b1; b2; b3; ...>`
is the stream `<a1; b1; a2; b2; a3; b3; ...>`. For example,
`interleave nats pow2` would be `<0; 1; 1; 2; 2; 4; 3; 8; ...>`
□
The *Sieve of Eratosthenes* is a way of computing the prime numbers.
* Start with the stream `<2; 3; 4; 5; 6; ...>`.
* Take 2 as prime. Delete all multiples of 2, since they cannot be prime.
That leaves `<3; 5; 7; 9; 11; ...>`.
* Take 3 as prime and delete its multiples.
That leaves `<5; 7; 11; 13; 17; ...>`.
* Take 5 as prime, etc.
##### Exercise: sift [✭✭✭]
Define a function `sift : int -> int stream -> int stream`,
such that `sift n s` removes all multiples of `n` from `s`.
*Hint: filter.*
□
##### Exercise: primes [✭✭✭]
Define a sequence `prime : int stream`,
containing all the prime numbers starting with 2.
□
##### Exercise: approximately e [✭✭✭✭]
The exponential function \\(e^x\\) can be computed by the following
infinite sum:
\\[
e^x = \\frac{x^0}{0!} + \\frac{x^1}{1!} + \\frac{x^2}{2!}
+ \\frac{x^3}{3!} + \\cdots + \\frac{x^k}{k!} + \\cdots
\\]
Define a function `e_terms : float -> float stream`. Element `k` of
the stream should be term `k` from the infinite sum. For
example, `e_terms 1.0` is the stream
`<1.0; 1.0; 0.5; 0.1666...; 0.041666...; ...>`. The easy way to
compute that involves a function that computes \\(f(k) = \\frac{x^k}{k!}\\).
Define a function `total : float stream -> float stream`, such that
`total <a; b; c; ...>` is a running total of the input elements, i.e.,
`<a; a+.b; a+.b+.c; ...>`.
Define a function `within : float -> float stream -> float`, such
that `within eps s` is the first element of `s` for which the
absolute difference between that element and the element before it
is strictly less than `eps`. If there is no such element, `within`
is permitted not to terminate (i.e., go into an "infinite loop").
As a precondition, the *tolerance* `eps` must be strictly positive.
For example, `within 0.1 <1.0; 2.0; 2.5; 2.75; 2.875; 2.9375; 2.96875; ...>`
is `2.9375`.
Finally, define a function `e : float -> float -> float` such that
`e x eps` is \\(e^x\\) computed to within a tolerance of `eps`,
which must be strictly positive. Note that there is an interesting
boundary case where `x=1.0` for the first two terms of the sum; you
could choose to drop the first term (which is always `1.0`) from the
stream before using `within`.
□
##### Exercise: better e [✭✭✭✭, advanced]
Although the idea for computing \\(e^x\\) above through the summation of
an infinite series is good, the exact algorithm suggested above could be
improved. For example, computing the 20th term in the sequence leads to
a very large numerator and denominator if \\(x\\) is large. Investigate
that behavior, comparing it to the built-in function `exp : float ->
float`. Find a better way to structure the computation to improve the
approximations you obtain. *Hint: what if when computing term \\(k\\)
you already had term \\(k-1\\)? Then you could just do a single
multiplication and division.*
Also, you could improve the test that `within` uses to determine
whether two values are close. A good one for determining whether
\\(a\\) and \\(b\\) are close might be:
\\[
\\frac{|a - b|}
{\\frac{|a| + |b|}{2} + 1}
<
\epsilon.
\\]
□
## Laziness
##### Exercise: lazy hello [✭]
Define a value of type `unit Lazy.t` (which is synonymous with
`unit lazy_t`), such that forcing that value with `Lazy.force`
causes `"Hello lazy world"` to be printed. If you force it again,
the string should not be printed.
□
##### Exercise: lazy and [✭✭]
Define a function `(&&&) : bool Lazy.t -> bool Lazy.t -> bool`.
It should behave like a short circuit Boolean AND. That is,
`lb1 &&& lb2` should first force `lb1`. If it is `false`,
the function should return `false`. Otherwise, it should
force `lb2` and return its value.
□
##### Exercise: lazy list [✭✭✭]
Implement an infinite list data abstraction using `Lazy.t`
instead of a thunk for the representation. Your structure
should match the following signature:
```
type 'a lazylist
val hd : 'a lazylist -> 'a
val tl : 'a lazylist -> 'a lazylist
val take : int -> 'a lazylist -> 'a list
val from : int -> int lazylist
val map : ('a -> 'b) -> 'a lazylist -> 'b lazylist
val filter : ('a -> bool) -> 'a lazylist -> 'a lazylist
```
The specifications of these functions were already provided
in lecture or in this lab.
*Hint: use the following representation type. Don't forget
to document an AF and RI.*
```
type 'a lazylist = Cons of 'a * 'a lazylist Lazy.t
```
Use your lazy lists to compute the Fibonacci sequence.
How does the speed compare to the stream implementation?
□
]]>