[Haskell] updating graphs non-destructively

[S. Alexander Jacobson]

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:

  --Data structures
  data Bid = Bid BidId Auction User Price DateTime
  data Auction = Auction Seller Title Description [Bid]
  data User = User UserId Name [Auction] [Bid]

  --Top level database
  type Auctions = FiniteMap AuctionId Auction
  type Users = FiniteMap UserId User
  type Bids = FiniteMap BidId Bid
  type Database = (Auctions,Users,Bids)

If I want to add a bid, it seems like I have
to traverse the whole Database looking for objects
that point to the bid.

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?

-Alex-

_________________________________________________________________
S. Alexander Jacobson                  mailto:me at alexjacobson.com
tel:917-770-6565                       http://alexjacobson.com