[Haskell] updating graphs non-destructively

Tom Pledger tpledger at ihug.co.nz
Tue Feb 17 14:04:49 EST 2004

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:

>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).


More information about the Haskell mailing list