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


_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell

Reply via email to