Writing the program

You should start by downloading Lab2.hs, reading the code and making sure you understand the structure.

The instructions below are just suggestions on how you could solve the lab. If you have a better idea, by all means, do that instead! The only requirement is that you use a skew heap.

A priority queue

Your first task is to implement a priority queue. You should put your priority queue in a different module and not in Lab2.hs. You should use a skew heap as it’s the simplest to implement, but it’s up to you what functions your module exports.

Your heap must support updating, i.e. changing a value that’s already in the heap. To do this, you can delete the existing value and insert the changed value. So you will probably want a function that deletes a value from the heap, with a type such as:

delete :: Ord a => a -> SkewHeap a -> SkewHeap a

Do not worry about making this operation efficient — do it in the simplest possible way. It will probably take O(n) or O(n log n) time.

Hint: as with all other operations on skew heaps, you will probably define deletion using merging.

The order book

Next you will probably want to define two types, BuyBid and SellBid. The order book will consist of a priority queue of BuyBids and a priority queue of SellBids. Then you can define an Ord instance for BuyBid and SellBid so that the priority queues work appropriately.

Finishing the program

Finally, write the trade function that executes the bids. You will probably want a helper function of type OrderBook → [Bid] → IO which does all the work.

Hint: this part of the program should be fairly small. If you find yourself doing complicated stuff with the priority queues, consider if you can add some functionality to your priority queue module instead.

Step 2: making sure your program is correct

Testing

Write a file with input data to your program and check that it works. Then use the test program to make sure that your program works. If the test program finds input data for which your program gives the wrong output or throws an exception, then you must work out what has gone wrong.

Invariant and properties

It’s a good idea (but not strictly required in this lab) to write down the invariant for your priority queue. If you write a function invariant :: Ord a ⇒ SkewHeap a → Bool, you can add assertions to your code which check that the invariant holds. To use assertions in Haskell you call the assert function in the Control.Exception module — this checks that the assertion holds, but is switched off if you compile with -O.

You could also write QuickCheck properties for your priority queue.

Submission

Before you upload your code to Fire, make sure that it passes half an hour of tests running the test program (you don’t need to write your own tests — running the test program is enough). The code should also meet the following requirements:

  • Your priority queue should be in its own file, and should be generic over the type of elements.

  • Your code should be of reasonable quality. Make sure that it compiles without warnings, and is indented sensibly. Comment any code that you think needs explaining.

  • Documentation: make sure that each exported function is documented. Also write down the time complexity for each exported function. (You may assume that all comparisons take O(1) time.)