# Exercises

## Streams

The next few exercises ask you to work with this type:

```
type 'a stream =
Cons of 'a * (unit -> 'a stream)
```

##### Exercise: pow2 [✭✭]

Define a value `pow2 : int stream`

whose elements are the powers
of two: `<1; 2; 4; 8; 16, ...>`

.

□

##### Exercise: more streams [✭✭, optional]

Define the following streams:

the even naturals

the lower-case alphabet on endless repeat: a, b, c, ..., z, a, b, ...

a stream of pseudorandom coin flips (e.g., booleans or a variant with

`Heads`

and`Tails`

constructors)

□

##### 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: hd tl [✭✭]

Recall these definitions:

```
(** [from n] is the stream [<n; n+1; n+2; ...>]. *)
let rec from n =
Cons (n, fun () -> from (n+1))
(** [nats] is the stream [<0; 1; 2; ...>]. *)
let nats = from 0
(** [hd s] is the head of [s] *)
let hd (Cons (h, _)) = h
(** [tl s] is the tail of [s] *)
let tl (Cons (_, tf)) = tf ()
```

Explain how each of the following is evaluated:

`hd nats`

`tl nats`

`hd (tl nats)`

`tl (tl nats)`

`hd (tl (tl nats))`

□

##### 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; ...>`

□

## Sieve Stream

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.

□

## e Stream

##### 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. \]

□

## Alternative Streams

##### Exercise: different stream rep [✭✭✭]

Consider this representation of streams:

```
type 'a stream = Cons of (unit -> 'a * 'a stream)
```

How would you code up `hd`

, `tl`

, `nats`

, and `map`

for it?
Explain how this representation is even lazier than our
original representation.

□

## 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 stream [✭✭✭]

Implement `map`

and `filter`

for the `'a lazystream`

type
provided in the section on laziness.

□

## Trees

##### Exercise: functorized BST [✭✭✭]

Our implementation of BSTs in lecture assumed that it was okay
to compare values using the built-in comparison operators `<`

, `=`

,
and `>`

. But what if the client of the `Set`

abstraction wanted to
use their own comparison operators? (e.g., to ignore case in strings,
or to have sets of records where only a single field of the record
was used for ordering.) Reimplement the `BstSet`

abstraction as a
functor parameterized on a structure that enables client-provided
comparison operator(s), much like the standard library `Set`

.

□

##### Exercise: efficient traversal [✭✭✭]

Suppose you wanted to convert a tree to a list. You'd have to put the values stored in the tree in some order. Here are three ways of doing that:

*preorder*: each node's value appears in the list before the values of its left then right subtrees.*inorder*: the values of the left subtree appear, then the value at the node, then the values of the right subtree.*postorder*: the values of a node's left then right subtrees appear, followed by the value at the node.

Here is code that implements those *traversals*, along with
some example applications:

```
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
let rec preorder = function
| Leaf -> []
| Node (l,v,r) -> [v] @ preorder l @ preorder r
let rec inorder = function
| Leaf -> []
| Node (l,v,r) -> inorder l @ [v] @ inorder r
let rec postorder = function
| Leaf -> []
| Node (l,v,r) -> postorder l @ postorder r @ [v]
let t =
Node(Node(Node(Leaf, 1, Leaf), 2, Node(Leaf, 3, Leaf)),
4,
Node(Node(Leaf, 5, Leaf), 6, Node(Leaf, 7, Leaf)))
(*
t is
4
/ \
2 6
/ \ / \
1 3 5 7
*)
let () = assert (preorder t = [4;2;1;3;6;5;7])
let () = assert (inorder t = [1;2;3;4;5;6;7])
let () = assert (postorder t = [1;3;2;5;7;6;4])
```

On unbalanced trees, the traversal functions above require quadratic
worst-case time (in the number of nodes), because of the `@`

operator.
Re-implement the functions without `@`

, and instead using `::`

, such
that they perform exactly one cons per `Node`

in the tree. Thus the
worst-case execution time will be linear. You will need to add an
additional accumulator argument to each function, much like with tail
recursion. (But your implementations won't actually be tail recursive.)

□

##### Exercise: RB draw complete [✭✭]

Draw the perfect binary tree on the values 1, 2, ..., 15.
Color the nodes in three different ways such that (i) each
way is a red-black tree (i.e., satisfies the red-black invariants),
and (ii) the three ways create trees with black heights of
2, 3, and 4, respectively. The *black height* of a tree
is the maximum number of black nodes along any path from its
root to a leaf.

□

##### Exercise: RB draw insert [✭✭]

Draw the red-black tree that results from inserting the characters D A T A S T R U C T U R E into an empty tree. Carry out the insertion algorithm yourself by hand, then check your work with the implementation provided in lecture.

□

##### Exercise: standard library set [✭✭, optional]

Read the source code of the standard library `Set`

module.
Find the representation invariant for the balanced trees that it uses.
Which kind of tree does it most resemble: 2-3, AVL, or red-black?

□

## Mutable fields and refs

##### Exercise: mutable fields [✭]

Define an OCaml record type to represent student names and GPAs. It
should be possible to mutate the value of a student's GPA.
Write an expression defining a student with name `"Alice"`

and GPA
`3.7`

. Then write an expression to mutate Alice's GPA to `4.0`

.

□

##### Exercise: refs [✭]

Give OCaml expressions that have the following types. Use utop to check your answers.

`bool ref`

`int list ref`

`int ref list`

□

##### Exercise: inc fun [✭]

Define a reference to a function as follows:

```
# let inc = ref (fun x -> x+1);;
```

Write code that uses `inc`

to produce the value `3110`

.

□

##### Exercise: addition assignment [✭✭]

The C language and many languages derived from it, such as Java, has an
*addition assignment* operator written `a += b`

and meaning
`a = a + b`

. Implement such an operator in OCaml; its type should be
`int ref -> int -> unit`

. Here's some code to get you started:

```
let (+:=) x y = ...
```

And here's an example usage:

```
# let x = ref 0;;
# x +:= 3110;;
# !x
- : int = 3110
```

□

##### Exercise: physical equality [✭✭]

Define `x`

, `y`

, and `z`

as follows:

```
let x = ref 0
let y = x
let z = ref 0
```

Predict the value of the following series of expressions:

```
# x == y;;
# x == z;;
# x = y;;
# x = z;;
# x := 1;
# x = y;;
# x = z;;
```

Check your answers in utop.

□

## Arrays

For the next couple exercises, let's use the following type:

```
(* AF: the float array [| x1; ...; xn |] represents the
* vector (x1, ..., xn)
* RI: the array is non-empty *)
type vector = float array
```

##### Exercise: norm [✭✭]

The Euclidean norm of an \(n\)-dimensional vector \(x = (x_1, \ldots, x_n)\) is written \(|x|\) and is defined to be

Write a function `norm : vector -> float`

that computes the
Euclidean norm of a vector. Your function should not mutate
the input array. *Hint: although your first instinct is
likely to reach for a loop, instead try to use Array.map
and Array.fold_left or Array.fold_right.*

□

Every vector can be *normalized* by dividing each component by
\(|x|\); this yields a vector with norm 1:

\[\left(\frac{x_1}{|x|}, \ldots, \frac{x_n}{|x|}\right)\]

##### Exercise: normalize [✭✭]

Write a function `normalize : vector -> unit`

that normalizes a vector "in place"
by mutating the input array. Here's a sample usage:

```
# let a = [|1.; 1.|];;
val a : float array = [|1.; 1.|]
# normalize a;;
- : unit = ()
# a;;
- : float array = [|0.7071...; 0.7071...|]
```

*Hint: Array.iteri.*

□

##### Exercise: normalize loop [✭✭]

Modify your implementation of `normalize`

to use one of the looping expressions.

□

##### Exercise: norm loop [✭✭]

Modify your implementation of `norm`

to use one of the looping expressions.
Here is pseudocode for what you should do:

```
initialize norm to 0.0
loop through array
add to norm the square of the current array component
return sqrt of norm
```

□

##### Exercise: init matrix [✭✭✭]

The array module contains two functions for creating an array: `make`

and `init`

. `make`

creates an array and fills it with a default value,
while `init`

creates an array and uses a provided function to fill it
in. The library also contains a function `make_matrix`

for creating a
two-dimensional array, but it does not contain an analogous
`init_matrix`

to create a matrix using a function for initialization.
Write a function ```
init_matrix : int -> int -> (int -> int -> 'a) -> 'a
array array
```

such that `init_matrix n o f`

creates and returns an `n`

by
`o`

matrix `m`

with `m.(i).(j) = f i j`

for all `i`

and `j`

in bounds.
See the documentation for `make_matrix`

for more information on the
representation of matrices as arrays.

□

## Challenge: Doubly-linked lists

##### Exercise: doubly linked list [✭✭✭✭]

Here is an OCaml file with types and functions for
mutable *doubly-linked lists*.
Complete the implementations in that file. Test your code.

*Hint: draw pictures! Reasoning about mutable data structures is typically
easier if you draw a picture.*

□

## Promises and Lwt

##### Exercise: promise and resolve [✭✭]

Download the completed implementation of `Promise`

.
Use it to do the following: create a integer promise and resolver,
bind a function on the promise to print the contents of the promise,
then resolve the promise. Only after the promise is resolved should
the printing occur.

□

##### Exercise: promise and resolve lwt [✭✭]

Repeat the **promise and resolve** exercise, but
use the Lwt library instead of our own Promise library.
Make sure to use Lwt's I/O functions (e.g., `Lwt_io.printf`

).

□

##### Exercise: promise and resolve lwt [✭✭]

Repeat the **promise and resolve** exercise, but
use the Lwt library instead of our own Promise library.
Make sure to use Lwt's I/O functions (e.g., `Lwt_io.printf`

).

□

##### Exercise: timing challenge 1 [✭✭]

Here is a function that produces a time delay. We can use it to simulate an I/O call that takes a long time to complete.

```
(** [delay s] is a promise that resolves after about [s] seconds. *)
let delay (sec : float) : unit Lwt.t =
Lwt_unix.sleep sec
```

Write a function `delay_then_print : unit -> unit Lwt.t`

that delays for three seconds then prints `"done"`

.

□

##### Exercise: timing challenge 2 [✭✭✭]

What happens when `timing2 ()`

is run? How long does it take to run?
Make a prediction, then run the code to find out.

```
open Lwt.Infix
let timing2 () =
let _t1 = delay 1. >>= fun () -> Lwt_io.printl "1" in
let _t2 = delay 10. >>= fun () -> Lwt_io.printl "2" in
let _t3 = delay 20. >>= fun () -> Lwt_io.printl "3" in
Lwt_io.printl "all done"
```

□

##### Exercise: timing challenge 3 [✭✭✭]

What happens when `timing3 ()`

is run? How long does it take to run?
Make a prediction, then run the code to find out.

```
open Lwt.Infix
let timing3 () =
delay 1. >>= fun () ->
Lwt_io.printl "1" >>= fun () ->
delay 10. >>= fun () ->
Lwt_io.printl "2" >>= fun () ->
delay 20. >>= fun () ->
Lwt_io.printl "3" >>= fun () ->
Lwt_io.printl "all done"
```

□

##### Exercise: timing challenge 4 [✭✭✭]

What happens when `timing4 ()`

is run? How long does it take to run?
Make a prediction, then run the code to find out.

```
open Lwt.Infix
let timing4 () =
let t1 = delay 1. >>= fun () -> Lwt_io.printl "1" in
let t2 = delay 10. >>= fun () -> Lwt_io.printl "2" in
let t3 = delay 20. >>= fun () -> Lwt_io.printl "3" in
Lwt.join [t1; t2; t3] >>= fun () ->
Lwt_io.printl "all done"
```

□

##### Exercise: file monitor [✭✭✭✭]

Write an Lwt program that monitors the contents of a file named "log". Specifically, your program should open the file, continually read a line from the file, and as each line becomes available, print the line to stdout. When you reach the end of the file (EOF), your program should terminate cleanly without any exceptions.

Here is starter code:

```
open Lwt.Infix
open Lwt_io
open Lwt_unix
(** [log ()] is a promise for an [input_channel] that reads from
the file named "log". *)
let log () : input_channel Lwt.t =
openfile "log" [O_RDONLY] 0 >>= fun fd ->
Lwt.return (of_fd input fd)
(** [loop ic] reads one line from [ic], prints it to stdout,
then calls itself recursively. It is an infinite loop. *)
let rec loop (ic : input_channel) =
failwith "TODO"
(* hint: use [Lwt_io.read_line] and [Lwt_io.printlf] *)
(** [monitor ()] monitors the file named "log". *)
let monitor () : unit Lwt.t =
log () >>= loop
(** [handler] is a helper function for [main]. If its input is
[End_of_file], it handles cleanly exiting the program by
returning the unit promise. Any other input is re-raised
with [Lwt.fail]. *)
let handler : exn -> unit Lwt.t =
failwith "TODO"
let main () : unit Lwt.t =
Lwt.catch monitor handler
let _ = Lwt_main.run (main ())
```

Complete `loop`

and `handler`

. You might find the Lwt manual
to be useful.

To compile your code, put it in a file named `monitor.ml`

and run

```
$ ocamlbuild -use-ocamlfind -pkg lwt.unix -tag thread monitor.byte
```

To simulate a file to which lines are being added over time, open a new terminal window and enter the following commands:

```
$ mkfifo log
$ cat >log
```

Now anything you type into the terminal window (after pressing return)
will be added to the file named `log`

. That will enable you to interactively
test your program.

□

## Monads

##### Exercise: add opt [✭✭]

Here are the definitions for the maybe monad:

```
module type Monad = sig
type 'a t
val return : 'a -> 'a t
val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
end
module Maybe : Monad =
struct
type 'a t = 'a option
let return x = Some x
let (>>=) m f =
match m with
| Some x -> f x
| None -> None
end
let add : int Maybe.t -> int Maybe.t -> int Maybe.t =
failwith "TODO"
```

Implement `add`

. If either of the inputs is `None`

, then the output
should be `None`

. Otherwise, if the inputs are `Some a`

and `Some b`

then the output should be `Some (a+b)`

. The definition of `add`

must be located outside of `Maybe`

, as shown above, which means
that your solution may not use the constructors `None`

or `Some`

in its code.

□

##### Exercise: fmap and join [✭✭]

Here is an extended signature for monads that adds two new operations:

```
module type ExtMonad = sig
type 'a t
val return : 'a -> 'a t
val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
val (>>|) : 'a t -> ('a -> 'b) -> 'b t
val join : 'a t t -> 'a t
end
```

Just as the infix operator `>>=`

is known as `bind`

, the infix
operator `>>|`

is known as `fmap`

. The two operators differ only in the
return type of their function argument.

Using the box metaphor, `>>|`

takes a boxed value, and a function that only
knows how to work on unboxed values, extracts the value from the box,
runs the function on it, and boxes up that output as its own return value.

Also using the box metaphor, `join`

takes a value that is wrapped in two boxes and
removes one of the boxes.

It's possible to implement `>>|`

and `join`

directly with pattern matching
(as we already implemented `>>=`

). It's also possible to implement them
without pattern matching.

For this exercise, do the former: implement `>>|`

and `join`

as part of the
`Maybe`

monad, and do not use `>>=`

or `return`

in the body of `>>|`

or `join`

.

□

##### Exercise: fmap and join again [✭✭]

Solve the previous exercise again. This time, you must use `>>=`

and `return`

to implement `>>|`

and `join`

, and you may not use `Some`

or `None`

in the body
of `>>|`

and `join`

.

□

##### Exercise: bind from fmap+join [✭✭✭]

The previous exercise demonstrates that `>>|`

and `join`

can be implemented
entirely in terms of `>>=`

(and `return`

), without needing to know anything
about the representation type `'a t`

of the monad.

It's actually possible to go the other direction. That is, `>>=`

can be implemented using just `>>|`

and `join`

, without needing to know
anything about the representation type `'a t`

.

Prove that this is so by completing the following code:

```
module type FmapJoinMonad = sig
type 'a t
val (>>|) : 'a t -> ('a -> 'b) -> 'b t
val join : 'a t t -> 'a t
val return : 'a -> 'a t
end
module type BindMonad = sig
type 'a t
val return : 'a -> 'a t
val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
end
module MakeMonad (M : FmapJoinMonad) : BindMonad = struct
(* TODO *)
end
```

*Hint: let the types be your guide.*

□

## The List Monad

We've seen three examples of monads already; let's examine a fourth, the
*list monad*. The "something more" that it does is to upgrade functions
to work on lists instead of just single values. (Note, there is no
notion of concurrency intended here. It's not that the list monad runs
functions concurrently on every element of a list. The Lwt monad does,
however, provide that kind of functionality.)

For example, suppose you have these functions:

```
let inc x = x + 1
let pm x = [x; -x]
```

Then the list monad could be used to apply those functions to every element of a list and return the result as a list. For example,

`[1; 2; 3] >>| inc`

is`[2; 3; 4]`

.`[1; 2; 3] >>= pm`

is`[1; -1; 2; -2; 3; -3]`

.`[1; 2; 3] >>= pm >>| inc`

is`[2; 0; 3; -1; 4; -2]`

.

One way to think about this is that the list monad operators take a list of inputs to a function, run the function on all those inputs, and give you back the combined list of outputs.

##### Exercise: list monad [✭✭✭]

Complete the following definition of the list monad:

```
module type ExtMonad = sig
type 'a t
val return : 'a -> 'a t
val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
val (>>|) : 'a t -> ('a -> 'b) -> 'b t
val join : 'a t t -> 'a t
end
module ListMonad : ExtMonad = struct
type 'a t = 'a list
(* TODO *)
end
```

*Hints:* Leave `>>=`

for last. Let the types be your guide. There are
two very useful list library functions that can help you.

□

## Monad Laws

##### Exercise: trivial monad laws [✭✭✭]

Here is the world's most trivial monad. All it does is wrap a value inside of a constructor.

```
module Trivial : Monad = struct
type 'a t = Wrap of 'a
let return x = Wrap x
let (>>=) (Wrap x) f = f x
end
```

Prove that the three monad laws, as formulated using `>>=`

and `return`

, hold for the trivial monad.