[Haskell] updating graphs non-destructively

[Tom Pledger]

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