# Exercises

##### Exercise: spec game [✭✭✭]

Pair up with another programmer and play the specification game with them. Take turns being the specifier and the devious programmer. Here are some suggested functions you could use:

`num_vowels : string -> int`

`is_sorted : 'a list -> bool`

`sort : 'a list -> 'a list`

`max : 'a list -> 'a`

`is_prime : int -> bool`

`is_palindrome : string -> bool`

`second_largest : int list -> int`

`depth : 'a tree -> int`

□

##### Exercise: poly spec [✭✭✭]

Let's create a *data abstraction* (a module that represents some kind
of data) for single-variable integer polynomials of the form
\[c_n x^n + \ldots + c_1 x + c_0.\] Let's assume that the polynomials
are *dense*, meaning that they contain very few coefficients that are zero.
Here is an incomplete interface for polynomials:

```
(** [Poly] represents immutable polynomials with integer coefficients. *)
module type Poly = sig
(** [t] is the type of polynomials *)
type t
(** [eval x p] is [p] evaluated at [x].
Example: if [p] represents $3x^3 + x^2 + x$, then
[eval 10 p] is [3110]. *)
val eval : int -> t -> int
end
```

(The use of `$`

above comes from LaTeX, in which mathematical formulas are
surrounded by dollar signs. Similarly, `^`

represents exponentiation
in LaTeX.)

Finish the design of `Poly`

by adding more operations to the interface.
Consider what operations would be useful to a client of the abstraction:

- How would they create polynomials?
- How would they combine polynomials to get new polynomials?
- How would they query a polynomial to find out what it represents?

Write specification comments for the operations that you invent. Keep in mind the spec game as you write them: could a devious programmer subvert your intentions?

□

##### Exercise: poly impl [✭✭✭]

Implement your specification of `Poly`

. As part of your implementation,
you will need to choose a representation type `t`

. *Hint: recalling
that our polynomials are dense might guide you in choosing a
representation type that makes for an easier implementation.*

□

##### Exercise: int set rep [✭✭✭]

Consider this interface for integer sets.
Suppose that you wanted the `to_list`

implementation to
run in constant time, perhaps at the expense of other
operations being less efficient. Implement the interface in a file
named `intset.ml`

. First choose a representation type,
then document its abstraction function and representation
invariant. Inside the implementation, define a `rep_ok`

function. Insert applications of it in the appropriate
places of your implementation to guarantee that all
input and output values satisfy the representation invariant.

□

##### Exercise: interval arithmetic [✭✭✭✭]

Specify and implement a data abstraction for interval arithmetic.
Be sure to include the abstraction function, representation invariant,
and `rep_ok`

. Also implement a `to_string`

function, or a `format`

function
as seen in the notes on functors.

##### Exercise: association list maps [✭✭✭]

Consider the `MyMap`

signature in maps.ml. Create **two**
implementations of it, both with the representation type ```
('k * 'v)
list
```

. The functions in the interface should mostly be trivially
implementable with the association list functions in the standard
library `List`

module. Your first implementation should prohibit any key
from appearing twice in the list; and your second should allow it. Start
each implementation by documenting the AF and RI for `t`

, and only after
you do that, implement the functions.

##### Exercise: function maps [✭✭✭✭]

Implement the `MyMap`

signature using the representation type `'k -> 'v`

.
That is, a map is represented as an OCaml function from keys to values.
Your solution will make heavy use of higher-order functions.

## A Buggy Queue

Download `buggy_queues.ml`

, which efficiently implements queues
with two lists—**but with a couple bugs deliberately injected**.

##### Exercise: AF and RI [✭]

The `TwoListQueue`

module documents an abstraction function
and a representation invariant, but they are not clearly identified
as such. Modify the comments to explicitly identify the abstraction
function and representation invariant.

□

##### Exercise: rep ok [✭✭]

Write a `rep_ok`

function for `TwoListQueue`

. Its type should be ```
t
-> t
```

. It should raise an exception whenever the representation
invariant does not hold. Modify the other functions exposed by the
`Queue`

signature to (i) check that `rep_ok`

holds for any queues passed
in, and (ii) check that `rep_ok`

also holds for any queues passed out.
*Hint: you will need to add nine applications of rep_ok.*

□

##### Exercise: test with rep ok [✭✭✭]

There are two bugs we deliberately injected into `TwoListQueue`

. Both
are places where we failed to apply `norm`

to ensure that a queue is in
normal form. Figure out where those are by testing each operation of
`TwoListQueue`

in the toplevel to see where your `rep_ok`

raises an
exception. Fix each bug by adding an application of `norm`

.

*Hint: to find one of the bugs, you will need to build a queue of
length at least 2.*

□