Assignment 2, CSC490, Spring 2009

1 More warmup exercises

• Design a datatype for family trees: a family tree is either Unknown, representing an ancestor lost in the mists of time, or else Person. a Person has a name, a year of birth, and a mother and a father. The mother and father are both family trees.

• Write down several examples of family trees.

• Develop the size function that takes a family tree and returns the number of Person nodes in the tree.

• Develop the transform function that takes a function from strings to strings and a family tree and returns the new family tree which differs from the original only in that the given function is applied to each name in the tree.

• Develop the oldest method that takes a family tree and returns the person with the earliest year of birth. It should signal an error if called with an entirely empty tree. (The simplest solution to this requires a helper function that takes an additional argument.)

• Develop the sameShape function that takes two family trees and returns true only if they have the same shape. That is, Unknown matches Unknown, and Person matches Person when the mother & father fields also satisfy sameShape.

• Develop the collapse function. This function collapses a Family Tree into a single value. To do this, our function must accept the following arguments:

  • an unknownVal, to be used as the result of collapsing a tree that is the value Unknown.

  • a combine function, used for Person values, that takes the name and birth year of the current Person along with the collapsed values of the mother and father trees and produces a value.

  • a family tree

  The collapse function must use these functions to collapse the family tree into a single value.

2 Representing a Simple Market

We’re going to begin to build the faintest skeleton of a market. In this market there’s just one equity to trade, and the "world" consists of bids and offers. All of these have limits. The goal here is to match up bidders and offerers so that they can effect transactions. That is, our program is making the market. Furthermore, we’re going to pocket the difference between the bid and offer prices (In practice, I believe the SEC frowns on this.)

• Develop a representation for orders. An order is either a limit offer, where a party offers a number of shares at a particular price per share, or a limit bid, where a part offers to buy a number of shares at a particular price per share. All share numbers are non-negative integers. All prices are in cents. Parties may be represented by strings.

• Develop at least three examples of orders.

• Develop the function canTrade, that accepts two orders, and returns true only when these two orders "match", in the sense that one of them is offering shares for a price less than the other is bidding.

• Develop a representation for a split; that is, half a transaction. A split has a party, a number of shares (positive indicates shares gained by the party), and an amount of money (positive indicates money gained by the party)

• Declare the NoTransactionPossible exception.

• Develop the function matchOrders, that takes two orders and returns two splits and an optional "leftover" order if the orders match, and signals the NoTransactionPossible exception otherwise. So, if I’m offering to buy 100 shares at a high price and you’re offering to sell 150 shares at a low price, then there will be two splits – one for each of us – and a leftover transaction where you’re offering to sell 50 shares at the same low low price.

• Develop the function runMarket, that takes a list of orders and produces a list of splits and a list of unfilled orders. The splits must all be legal in the sense that no party winds up buying more or less than he or she wanted, or getting a price that they didn’t offer or bid. Also, there may not be any pairs left in the list of unfilled orders that could be combined into a transaction.

3 Handin instructions

Any assignment that requires you to develop your own representations causes problems for automatic testing; that is, my code can’t test yours unless it knows how to represent its test data.

We’re going to try to solve by having *two* due dates for this assignment; the first one for the data representations, and the second one for the whole thing. After the first due date, I’m going to give you my data definitions, and your second submission will have to work with these data definitions.

Put your code and tests (for the first part, just your examples of data) in a single ML file, and hand it in using the DrScheme handin plugin.