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