## 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 = <abstr> ``` 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 = <fun> ``` 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.