## Queues
In the [code associated with the lecture on modules][mod-code], there is
an interface for queues and two implementations of queues. With that code,
complete the following exercises in utop:
[mod-code]: code.ml
**Exercise:** Create a `ListQueue` that contains the integers 1, 2, and 3 in that
order.
**Exercise:** Read the implementation of `ListQueue.enqueue`. Explain in your
own words why its efficiency is linear time in the length of the queue.
**Exercise:** Use the following code to create `ListQueue`'s of exponentially
increasing length: 10, 100, 1000, etc. How big of a queue can you create before
there is a noticeable delay? How big until there's a delay of at least 15 seconds?
(Note: you can abort utop computations with Ctrl-C.)
```
(* Creates a ListQueue filled with [n] elements. *)
let fill_queue n =
let rec loop n q =
if n=0 then q
else loop (n-1) (ListQueue.enqueue n q) in
loop n ListQueue.empty
```
**Exercise:** Repeat the above three exercises with `TwoListQueue`,
whose `enqueue` operation is constant time. You will need to modify
`fill_queue` to use `TwoListQueue` instead of `ListQueue`.
**Exercise:** Appreciate how `ListQueue` is simple and (hopefully)
obviously correct. Appreciate how `TwoListQueue` is more complicated
and less obviously correct. Reflect on what Donald Knuth (Turing Award
winner, 1974) said in his [award lecture][knuth]:
> [P]rogrammers have spent far too much time worrying about efficiency in the
> wrong places and at the wrong times; premature optimization is the root of
> all evil (or at least most of it) in programming.
[knuth]: http://dl.acm.org/citation.cfm?id=361612
## Arithmetic
In lecture, you saw that module types provide a mechanism for *encapsulation*:
if a module has a type, then anything not declared in module type is hidden from
the external world.
OCaml has very flexible mechanisms for combining module types and controlling
hiding. In this lab, we explore some of them. We will use the running example
of a module type that encapsulates numbers that you can do basic arithmetic
with.
**Exercise:** In your working file for the recitation, define a module type
called `Arith` containing
- a type `t`
- a value called `zero`
- a value called `one`
- a function `(+) : t -> t -> t`
- a function `(*) : t -> t -> t`
- a function `(~-) : t -> t` (note that `~-` is how ocaml writes unary
negation).
**Exercise:** In your working file for the recitation, define a module called
`Ints` that implements the `Arith` module type:
```
module Ints : Arith = struct
...
end
```
**Exercise:** In your working file for the recitation, define a module called
`Floats` that also implements the `Arith` signature. Include an additional
function called `(/)` for dividing two floats.
For the following exercise, we will introduce a convenient OCaml syntax.
Recall that you can `open` a module to bring all of the definitions into scope,
and also that you can write `let open M in e` to evaluate `e` with all of the
definitions of `M` in scope (this is sometimes called a "local open" because
M is opened in `e` but not outside of the scope of the `let` statement).
There is a more compact syntax for a local open: `M.(e)` evaluates `e` in an
environment with all of the definitions of `M` available. For example, the
following are equivalent (extra spaces added to line things up):
```
List. length (List.reverse (List.map List.concat [[[1;2];[3]]]));;
List.(length ( reverse ( map concat [[[1;2];[3]]])));;
```
**Exercise:** Which of the following expressions are valid? Keep in mind that
when type checking expressions, **the compiler only looks at the *module type* of
the module, and not the module itself**.
- `Ints.(one + one)`
- `Ints.(1 + 1)`
- `Floats.(one + one)`
- `Floats.(one +. one)`
- `Floats.(1 + 1)`
- `Floats.(1. + 1.)`
- `Floats.(1. +. 1.)`
- `Ints.(1. +. 1.)`
- `Floats.(zero / one)`
Check your answers in the top level, and ensure that you can explain why each
works or doesn't work.
## Working with abstract types
You may have noticed that you can't do much with your `Ints` module. You can
compute one plus one, for example, but you can't even see the answer!
```
utop# Ints.(one + one);;
- : Ints.t =
```
The problem is that the type `Ints.t` is *abstract*: the module type doesn't
tell use that `Ints.t` is `int`. This is actually a good thing in many cases:
code outside of `Ints` can't rely on the internal implementation details of
`Ints`, and so we are free to change it. Also, as we'll see in the next lecture,
we can write generic code that works with both `Ints` and `Floats` and with
any other implementation of `Arith` (fractions, polynomials, functions,
infinite-precision real numbers...the possibilities are endless).
However, the `Arith` interface only has functions that return `t`, so once you
have a value of type `t`, all you can do is create other values of type `t`.
When designing an interface with an abstract type, you will almost certainly
want at least one function that returns something other than that type.
When debugging, you usually want to be able to print things. An easy way to do
this is to provide a `to_string` function, so that you can print the strings
while debugging.
**Exercise:** Add a `to_string` function to the `Arith` interface. Notice that
your code doesn't compile anymore. Fix it.
Now you can write
```
utop# Ints.(to_string (one + one));;
- : string = "2"
```
**Exercise (\*):** There is a slicker way to provide printing functions for
abstract types using the `Format` module, and it provides nice integration with
utop. If you're interested, [do this exercise](printing.html). To whet your
appetite:
```
utop# #install_printer Polynomial.format;;
utop# Polynomial.(one + x + (one + one) * x * x);;
- : Polynomial.t = 2x^2 + x + 1
```
**Exercise:** It is sometimes sensible to provide a conversion from your
abstract type to or from some "lowest common denominator" type. Which of the
following functions would make sense as part of the `Arith` interface? Add the
sensible ones.
- `to_int : t -> int`
- `of_int : int -> t`
- `to_float : t -> float`
- `of_float : float -> t`
Think about the impact of adding these functions on other modules you might want
to implement in the future.
## Adding type information with type constraints
Sometimes you actually want to expose the type in an implementation of a
module. You might like to say "the module `Ints` implements `Arith` and the
type `t` is `int`," and allow external users of the `Ints` module to use the
fact that `Ints.t` is `int`.
Luckily, OCaml lets you say exactly this. If `T` is a module type containing an
abstract type `t`, then `T with type t = int` is a new module type that is the
same as `T`, except that `t` is declared as `int`.
**Exercise:** At the top level, define the following module type:
```
utop# module type ArithWithInt = Arith with type t = int;;
```
Compare the resulting module type with the `Arith` module type.
**Exercise:** Change the module type of `Ints` to expose the implementation of
`Ints.t`:
```
module Ints : Arith with type t = int = struct
...
end
```
**Exercise:** With your new implementation, which of these expressions are
valid? Test your answers.
- `Ints.(one + one)`
- `Ints.(1 + 1)`
- `Ints.(1. +. 1.)`
There is a slightly different way to express type constraints, which uses `with
type t := ...` instead of `with type t = ...` (the difference is the `:=`
instead of `=`). Instead of defining type t, the `:=` syntax removes `t` and
replaces it everywhere. It is occasionally useful, for example to resolve
errors where a type is defined multiple times.
**Exercise:** At the toplevel, compare the signatures `Arith with type t = int`
and `Arith with type t := int`.
## Including (extending) module types
Another way that you may want to refine a module signature is by adding more
functionality to it. For example, you added a `(/)` operator to the `Floats`
interface, but since `Floats` is declared with type `Arith`, the `(/)` function
is not visible:
```
utop# Floats.(one / one);;
Error: This expression has type t but an expression was expected of type int
```
This error is caused by the fact that `Floats.(/)` is not visible, so the
toplevel is interpreting `(/)` as a plain old integer division:
```
utop# Floats.(/);;
Error: Unbound value Floats./
utop# Floats.(+);;
- : Floats.t -> Floats.t -> Floats.t =
```
What you would like is to say "`Floats` has module type `Arith` but also adds
some other functions".
Luckily, OCaml lets you do this by extending module signatures. If `T` is a
module type, then inside a module signature `S`, you can use `include T` to
include all of the declarations in `T` in the current module signature. Since
`S` contains all of the definitions of `T` and then some, we say that `S`
extends `T`. In fact, `include` in OCaml is very similar to `extends` in Java.
**Exercise:** with the following module type definitions, what values must be
defined by a module of type T'?
```
module type T = sig
val x : int
end
module type T' = sig
include T
val y : int
end
```
You don't need to give the extended signature a name: with the module types `T`
and `T'` just defined, the following are equivalent:
```
module X : T' = struct
...
end
```
```
module X : sig
include T
val y : int
end = struct
...
end
```
**Exercise:** Modify your implementation of `Floats` so that the `(/)` operator
is visible.
## Exposing everything in a module
Occasionally you just want to make everything public so that hiding doesn't
get in your way while you're debugging. We will discuss an elegant way to do
this in the next lab, but an unstylish way to do it is by simply leaving off
the module type annotation.
For example, instead of writing
```
module Floats : sig
include Arith
val (/) : t -> t -> t
end = struct
...
end
```
You could simply leave off everything between the `:` and the `=`:
```
module Floats = struct
...
end
```
The compiler will generate a new type signature for this module that includes
everything defined in the `Floats` module. You can think of this as a kind of
type inference: you've left off the module type annotation for the module, and
the compiler figures one out for you, just like you can leave the type
annotation off of a variable and the compiler will generate one for you.
**Exercise:** what is the module type of the following module: `module X = struct let x = 0 let f y = [y] end`?
The downside to leaving off the module type annotation is that you will no
longer get an error if you accidentally change one of the names or types of the
function, nor will you get an error if the module type `Arith` changes. For
example, when you added the `to_string` function above, you would not have had
a reminder to add the `to_string` function to the `Floats` module.
If the module and the module type diverge, then code that is expecting to work
with any `Arith` implementation may not work with `Floats`.
In addition, since you're not hiding anything, you lose the benefits of
encapsulation. In the next recitation, we'll see how to get the best of both
worlds.
## Dictionaries
A *dictionary* maps *keys* to *values*. They typically support at least a
lookup operation that allows you to find the value with a corresponding key, an
insert operation that lets you create a new dictionary with an extra key
included. In addition, the user needs to be able to start with an empty
dictionary.
We might encapsulate this in a `Dictionary` module type as follows:
```
module type Dictionary = sig
type ('k, 'v) t
(** The empty dictionary *)
val empty : ('k, 'v) t
(** insert k v d produces a new Dictionary.t with the same mappings as d and
also a mapping from k to v. If k was already mapped in d, the old mapping
is replaced. *)
val insert : 'k -> 'v -> ('k,'v) t -> ('k,'v) t
(** lookup k d returns the value associated with k in d. It raises an
exception if there is no binding. *)
val lookup : 'k -> ('k,'v) t -> 'v
end
```
Note how the type `Dictionary.t` is parameterized on two types, `'k` and `'v`,
which are written in parentheses and separated by commas. Although `('k,'v)`
might look like a pair of values, it is not: it is a syntax for writing
multiple type variables.
### Association lists
One simple implementation of a dictionary is an *association list*, which is a
list of pairs of keys and values. For example, here is an association list
that maps some well-known names to an approximation of their numeric value:
```
[("pi", 3.14); ("e", 2.718); ("phi", 1.618)]
```
**Exercise:** write a module `AssocList` that implements the `Dictionary` interface
using `type ('k,'v) t = ('k * 'v) list`. Note that the `List` module contains
some convenient functions for working with association lists.
**Exercise:** write a module `BSTDict` that implements the `Dictionary`
interface using the `bstree` type that you defined in the last lab.