Like most of the folks here, I'm learning Haskell, so I figured an interesting exercise would be to build a matching engine that I could use to build a financial exchange. I'm wondering primarily if I used monad transformers here idiomatically, but all other feedback is appreciated as well.
In some cases I felt like using the monad was overkill and maybe I should have just carried the state or log of trades along in the arguments to the various functions, for clarity. Also, this would have to be embedded into other monads and then eventually of course an IO monad in order to be able to receive orders from the network, check people's accounts, etc.
It seems like using the (MonadX) => constraint was the right way to go so that my function signatures only needed to mention the specific monad I needed rather than the entire stack of transformers, but I'm not sure.
Order.hs:
module Order where
import Numeric.Natural
-- | 'Side' defines if an order is a buy or sell
data Side = Buy | Sell deriving (Eq, Show)
-- | 'Order' represents the core details of a given order
data Order = Order { side :: Side, price :: Natural, quantity :: Natural, timestamp :: Natural } deriving Show
-- | 'OrderId' is a reference used externally to refer to a certain order, which may have changed
type OrderId = Int
-- | 'Eq' for 'Order' doesn't care if the quantities are different
instance Eq Order where
(==) x y = (side x == side y) && (price x == price y) && (timestamp x == timestamp y)
-- | 'Ord' for 'Order' is a price-time ordering, which inverts the price ordering if it is a Buy
-- | so that the best bid and ask are always 'least'. For orders of the same price, the earliest
-- | one is better.
instance Ord Order where
compare x y
| x == y = EQ
| side x /= side y = error "Can't compare orders of different sides"
| priceCompare == EQ = compare (timestamp x) (timestamp y)
| otherwise = priceCompare
where
priceModifier = case side x of
Buy -> flip
Sell -> id
priceCompare = priceModifier compare (price x) (price y)
-- | 'matchCompare' returns True if the two orders can trade against each other. I.e. they are 'matched'
matchCompare :: Order -> Order -> Bool
matchCompare x y
| side x == side y = False
| otherwise = let buyOrder = if side x == Buy then x else y
sellOrder = if side x == Sell then x else y
in price buyOrder >= price sellOrder
OrderBook.hs:
{-# LANGUAGE FlexibleContexts #-}
module OrderBook where
import Data.PSQueue
import Order
import Control.Monad.State
import Control.Monad.Writer
import Numeric.Natural
-- | 'OrderBook' is the representation of the OrderBook
data OrderBook = OrderBook { bids :: PSQ OrderId Order, asks :: PSQ OrderId Order } deriving Show
-- | 'Trade' records the details of a given trade. We're assuming the Orders are stored somewhere by OrderId somewhere
data Trade = Trade { aggressiveOrderId :: OrderId, passiveOrderId :: OrderId, size :: Natural, price :: Natural } deriving (Show, Eq)
emptyBook :: OrderBook
emptyBook = OrderBook empty empty
-- | 'processOrders' is the core that takes orders, matches them, spits out trades and keeps
-- | track of the orderbook.
processOrders :: (MonadState OrderBook m, MonadWriter [Trade] m) -- ^ We keep track of the orderbook and spit out the list of trades
=> [(OrderId, Order)] -- ^ list of orders to put into the book
-> m () -- ^ no return value, interesting info is in the monads
processOrders [] = return ()
processOrders ((orderId, order):orders) = do
matchResult <- matchOrder (orderId, order)
case matchResult of
Just newOrder -> processOrders ((orderId, newOrder):orders)
Nothing -> processOrders orders
where
-- | 'matchOrder' will create one trade for a given aggressive order (not yet in the book), and spit out what is left of that order
matchOrder :: (MonadState OrderBook m, MonadWriter [Trade] m) -- ^ We keep track of the orderbook and spit out the list of trades
=> (OrderId, Order) -- ^ The aggressive order
-> m (Maybe Order) -- ^ Whatever is left of the aggressive order
matchOrder (aggressiveOrderId, aggressiveOrder) =
getMatchingPassive >>= \maybeMatchingPassive ->
case maybeMatchingPassive of
Just (passiveOrderId, passiveOrder) ->
-- a trade happened. Add it to the trade log, update the passive order in the book
-- and return whatever is left over of the aggressive order
let
tradeSize = min (quantity aggressiveOrder) (quantity passiveOrder)
tradePrice = Order.price passiveOrder
newAggressiveOrder = aggressiveOrder { quantity = quantity aggressiveOrder - tradeSize }
newPassiveOrder = passiveOrder { quantity = quantity passiveOrder - tradeSize }
trade = Trade aggressiveOrderId passiveOrderId tradeSize tradePrice
in do
tell [trade]
updateOrder (passiveOrderId, newPassiveOrder)
return $ clearOrder newAggressiveOrder
Nothing -> do
-- no trade happened, so just put the aggressive order into the book.
insertOrder (aggressiveOrderId, aggressiveOrder)
return Nothing
where
-- | 'getMatchingPassive' grabs the matching passive order from the other side of the book
-- | if one exists.
getMatchingPassive :: (MonadState OrderBook m) -- ^ We need to get the book from the state monad
=> m (Maybe (OrderId, Order)) -- ^ But the maybe this returns isn't used in monadic fashion
getMatchingPassive =
get >>= \book ->
let
passiveSide = case side aggressiveOrder of
Buy -> asks book
Sell -> bids book
in
case findMin passiveSide of
Just (passiveOrderId :-> passiveOrder) ->
if matchCompare passiveOrder aggressiveOrder
then return $ Just (passiveOrderId, passiveOrder)
else return Nothing
Nothing ->
return Nothing
-- | 'insertOrder' puts an order into the book, but doesn't worry about matching. We must be sure it doesn't match
-- | when we call this... otherwise, problems.
insertOrder :: (MonadState OrderBook m) -- ^ Keep track of the orderbook
=> (OrderId, Order) -- ^ The order to insert
-> m () -- ^ The resulting book is in the monad, hence no return value
insertOrder (orderId, order) =
get >>= \book -> case side order of
Buy -> put $ book { bids = insert orderId order (bids book) }
Sell -> put $ book { asks = insert orderId order (asks book) }
-- | 'updateOrder' modifies the passive order in the book once a piece has been taken out of it
-- | buy an aggressive order
updateOrder :: (MonadState OrderBook m) -- ^ Keeping track of the OrderBook
=> (OrderId, Order) -- ^ The modified order with id
-> m () -- ^ no return value, everything interesting is in the State
updateOrder (orderId, order) =
get >>= \book -> case side order of
Buy -> put $ book { bids = update (const $ clearOrder order) orderId (bids book) }
Sell -> put $ book { asks = update (const $ clearOrder order) orderId (asks book) }
-- | 'clearOrder' turns an order with zero size into 'Nothing'
clearOrder :: Order -> Maybe Order
clearOrder order
| quantity order == 0 = Nothing
| otherwise = Just order
