S. Alexander Jacobson wrote:
In imperative languages, updating an object in a graph is an O(1) operation. However, non-destructive update appears to be O(n) with the size of the graph. For example, suppose we were to implement an auction system like eBay:
[snip]
One alternative is to store pointers rather than values e.g.
data Bid = Bid BidId AuctionId UserId Price DateTime data Auction = Auction SellerId Title Description [BidId] data User = User UserId Name [AuctionId] [BidId]
But that makes graph traversal expensive as each edge traversal then costs O(log n). O(log n) may be okay for this app, but what if I was implementing Friendster/LinkedIn/Tribe/etc.?
Is there a better way to think about this?
If you use pointers, surely the update becomes destructive? Unless you keep track of multiple versions of the top level database... which would be quite an effort! With a non-destructive update, I think you're stuck with visiting all the parts of the structure which can see the part you're changing. For a destructive update, more like what you'd use in an imperative language, you could try
data Bid = Bid (IORef (BidId, Auction, User, Price, DateTime)) data Auction = Auction (IORef (Seller, Title, Description, [Bid])) data User = User (IORef (UserId, Name, [Auction], [Bid]))
to get the edge traversal down to O(1). Regards, Tom