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