[Haskell-cafe] help with creating a DAG?

Robert Dockins robdockins at fastmail.fm
Sat Jul 8 21:54:58 EDT 2006

On Saturday 08 July 2006 12:25 pm, David Roundy wrote:
> Hi all,
> I'm wanting to create a data structure to hold a directed acyclic
> graph (which will have patches represented by edges), and haven't yet
> been able to figure out a nice representation.  I'd like one that can
> be reasoned with recursively, or as closely to recursively as
> possible.  The problem is one of dependency relations between darcs
> patches, and "normally" reduces to a simple tree, with conflict
> resolution patches bringing branches of the tree back together.  Trees
> I know how to handle intuitively and elegantly, but DAGs are a whole
> different question.
> I looked for papers, and there was one on "an initial-algebra approach
> to DAGs" that looked promising, but I'm afraid I wasn't able to fully
> understand it, and it is able to describe more complicated DAGs than
> I'd like to support.
> Anyhow, any suggestions from persons with experience with this sort of
> thing would be great.  These are getting to be data structures that
> are more complicated than anything I'm comfortable with.  :(

Is there some reason you don't want to use FGL?


Rob Dockins

Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
       -- TMBG

More information about the Haskell-Cafe mailing list