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:[EMAIL PROTECTED] tel:917-770-6565 http://alexjacobson.com _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell