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

Explain how each of the following stream expressions 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 : 'a stream -> 'a, tl : 'a stream -> 'a stream, nats : int stream, and map : ('a -> 'b) -> 'a stream -> 'b stream 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.

□

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: 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.

Curry-Howard

Exercise: propositions as types [✭✭]

For each of the following propositions, write its corresponding type in OCaml.

• true -> p
• p /\ (q /\ r)
• (p \/ q) \/ r
• false -> p

Exercise: programs as proofs [✭✭✭]

For each of the following propositions, determine its corresponding type in OCaml, then write an OCaml let definition to give a program of that type. Your program proves that the type is inhabited, which means there is a value of that type. It also proves the proposition holds.

• p /\ q -> q /\ p
• p \/ q -> q \/ p

Exercise: evaluation as simplification [✭✭✭]

Consider the following OCaml program:

let f x = snd ((fun x -> x,x) (fst x))

• What is the type of that program?
• What is the proposition corresponding to that type?
• How would f (1,2) evaluate in the small-step semantics?
• What simplified implementation of f does that evaluation suggest? (or perhaps there are several, though one is probably the simplest?)
• Does your simplified f still have the same type as the original? (It should.)

Your simplified f and the original f are both proofs of the same proposition, but evaluation has helped you to produce a simpler proof.