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.

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.

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


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.

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.

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

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

type 'a t
val return : 'a -> 'a t
val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
end

(* TODO *)
end


Hint: let the types be your guide.

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.

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

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.

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.