# 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 [&#10029;] 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. &square; ##### Exercise: rep ok [&#10029;&#10029;] 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.* &square; ##### Exercise: test with rep ok [&#10029;&#10029;&#10029;] 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.* &square; ##### Exercise: int set rep [&#10029;&#10029;&#10029;] 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. &square; ##### Exercise: interval arithmetic [&#10029;&#10029;&#10029;&#10029;] 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 &square;