As we know, SOCOG's effort at allocating the Olympic tickets has been rather
less than perfect. You're going to demonstrate that you're more capable than
they are, by writing a few Haskell functions to do just that job.
The ultimate aim is to write an allocateTickets function, which
will be given a list of people, the events they want to see, and how important
their order is considered to be -- that is, the priority of their order.
As well as this, allocateTickets will be given information about
how many tickets are available, and for which events.
On the basis of this information, allocateTickets will then give
out tickets -- starting with the highest priority orders. Once tickets for an
event run out, the rest of the (less important) people who want tickets for that
event are just out of luck -- they miss out.
Once its run through all the orders, allocateTickets will return
a list of the tickets that have been sold, as well as information about how many
tickets are still available for each event.
We've defined some types to
make it clear what each piece of data is for. These are fully described here.
As a starting point, we've provided a Haskell file with all the types and
module skeleton in it here.
Feel free to use all, part, or none of that file.
Our ultimate aim is to write the allocateTickets function, which will have
the type signature:
allocateTickets :: TicketDB -> [Request] -> ( [IssuedTicket], TicketDB )
the TicketDB input tells us about the tickets available
initially, and the [Request] gives us a list of the orders that we
wish to process. The function is to return a list of the tickets that have been
issued, and the modified TicketDB -- that is, with the issued
tickets removed from the TicketDB.
Ticket will be issued to Requests with higher
Priority first -- see the getHighestRequest
function to find out how this is worked out.
Helper functions - ticketAvailable, removeTicket,
and getHighestRequest
Since allocateTickets is a pretty complicated function to do,
you don't want to tackle it all in one go. In later assignments, you'll be
expected to work out how to break up a big task into smaller ones on your own,
but this time we're going to give you some help:
(Note that we will be testing these three functions
(ticketAvailable, removeTicket, and
getHighestRequest) separately, so you need to write them,
following the spec, even if you don't end up using them in
allocateTickets).
To make the job easier, we'll probably want a function to check if there is a
ticket available for a particular event:
ticketAvailable :: TicketDB -> Event -> Bool
Given a TicketDB and an Event, this function is to
return True if there is at least one ticket available for the event.
If the Event is not mentioned at all in the
TicketDB, then there has been an order for a non-existent
Event. In this case, the function should display an error message
exactly like this:
ticketAvailable - unknown Event
(Hugs will add 'Program error: ' to the front of this... thats OK!)
So far so good. But this still doesn't actually take the ticket out of the
TicketDB -- it just checks if there is one. So we'll want another
ticket:
removeTicket :: TicketDB -> Event -> TicketDB
Given a TicketDB and an Event, this function will
reduce the number of tickets available for that Event by one, and
return the modified TicketDB. If an Event becomes sold
out as a result of this function, you should not remove it from
the TicketDB - leave it in the TicketDB, listed with 0
tickets available.
If the Event is not mentioned at all in the
TicketDB, then the TicketDB should be returned
unchanged.
On the other hand, if the tickets for the Event have all been sold, we should
return a different error:
removeTicket - event is sold out
Since we aren't guaranteed that the [Request] given to
allocateTickets is in any particular order, we'll also need a function to get
the highest priority request out of a [Request]:
getHighestRequest :: [Request] -> ( Request, [Request] )
Given a [Request], this function is to return a tuple containing
the Request with the highest Priority, and the
[Request] with that (highest priority) one removed.
When there are multiple Request s with the same
Priority, then the Person whose name comes first in
the alphabet should be returned.
Note that you can use > < >= <= and == to compare
String s in Haskell.
If the [Request] is empty, then your program should display the
following error message:
getHighestRequest - [Request] is empty
Hint: You may want to write the following functions
to make getHighestRequest easier:
lookupHighestRequest
Given a [Request], returns the Request with highest
Priority.
removeRequest
Given a [Request] and a particular Request in that
list, returns the list with that particular Request removed.
If you choose to follow this hint and write removeRequest and
lookupHighestRequest, you'll have to work out the type signatures
for yourself; the word descriptions above should give a pretty big hint :-)
