# Abstraction Functions and Representation Invariants
Look at [`queues.ml`](queues.ml), which efficiently implements queues
with two lists. It's mostly the same implementation that we provided in
the code accompanying the lecture on modules, but we've deliberately
added a couple bugs to it.
##### 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.*
□
##### Exercise: int set rep [✭✭✭]
Consider [this interface for integer sets](intset.mli).
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][int-arith].
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.
[int-arith]: http://web.mit.edu/hyperbook/Patrikalakis-Maekawa-Cho/node45.html
□