[Haskell-cafe] help with creating a DAG?

David Roundy droundy at darcs.net
Sat Jul 8 12:25:18 EDT 2006

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.  :(
David Roundy

More information about the Haskell-Cafe mailing list