Data Structures
DIT961 VT-2018
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.
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:
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.
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.
Finally, write the trade function that executes the bids. You will probably want a helper function of type
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.
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.
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.
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:
