[Haskell] updating graphs non-destructively

[S. Alexander Jacobson]

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 at 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 at alexjacobson.com
> > tel:917-770-6565                       http://alexjacobson.com
> > _______________________________________________
> > Haskell mailing list
> > Haskell at 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
>