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