Thank you for the link to FGL. I also looked at the boilerplate stuff. If *feels* like there should be a way to embed the graph stuff in the boilerplate stuff to allow non-destructive update of arbitrary object graphs without handcoding the mapping of the datastructure to an object graph? Is this possible? Has anyone does this? Any reason to believe its a bad idea? Alternatively, I could decide up front to represent my data as RDF triples (amenable to a graph system), but I'd rather take advantage of Haskell's type system. -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com On Mon, 16 Feb 2004, andrew cooke wrote:

have you looked at the functional graph library? i can't remember the details, but think it is efficient and it is certainly a better way to think about graphs :o) - the details are in the paper by erwig

http://web.engr.oregonstate.edu/~erwig/fgl/

andrew

S. Alexander Jacobson said:

...

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

-- personal web site: http://www.acooke.org/andrew personal mail list: http://www.acooke.org/andrew/compute.html