[Haskell-cafe] help with creating a DAG?

Brian Hulley brianh at metamilk.com
Sat Jul 8 17:50:14 EDT 2006

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

If you consider a DAG as just an optimized representation for a tree then 
you could annotate each node with a Unique and create monadic traversal 
functions analogous to tree functions but using a finite map Unique -> r to 
memoise the results of traversal so that a node is only traversed once.

Regards, Brian.
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.


More information about the Haskell-Cafe mailing list