Take the 2-minute tour ×

How do you define a directed acyclic graph (DAG) (of strings) (with one root) best in Haskell?

I especially need to apply the following two functions on this data structure as fast as possible:

  1. Find all (direct and indirect) ancestors of one element (including the parents of the parents etc.).
  2. Find all (direct) children of one element.

I thought of [(String,[String])] where each pair is one element of the graph consisting of its name (String) and a list of strings ([String]) containing the names of (direct) parents of this element. The problem with this implementation is that it's hard to do the second task.

You could also use [(String,[String])] again while the list of strings ([String]) contain the names of the (direct) children. But here again, it's hard to do the first task.

What can I do? What alternatives are there? Which is the most efficient way?

EDIT: One more remark: I'd also like it to be defined easily. I have to define the instance of this data type myself "by hand", so i'd like to avoid unnecessary repetitions.

share|improve this question
data Family = Ego { parents, children :: [String] }; type DAG = Map String Family? If you store parents as well as children, both find operations should be reasonably fast. –  Daniel Fischer May 6 '13 at 21:04
Or have two maps. One from parents to children, second from children to parents. Choose the way fits you best. –  Adrian May 6 '13 at 21:08
I added an additional remark in the original question which makes your suggetion difficult. –  Mekeor Melire May 6 '13 at 21:12
@MekeorMelire Define your own map-like datatype. You can start with type Map k v = [(k, v)]. –  Rhymoid May 6 '13 at 21:14
Cheap, fast, correct, pick two. Err, you can have two of 1. easy/fast finding of parents, 2. easy/fast finding of children, 3. simple representation. Consider the tradeoffs and take your pick. –  Daniel Fischer May 6 '13 at 21:27
show 2 more comments

1 Answer

Have you looked at the tree implementtion in Martin Erwig's Functional Graph Library? Each node is represebted as a context containing both its children and its parents. See the graph type class for how to access this. It might not be as easy as you requested, but it is already there, well-tested and easy-to-use. I have used it for more than a decade in a large project.

share|improve this answer
Any idea about its speed over Haskell maps? I want to use this library but my graphs are pretty big. –  Dilawar Jun 7 '13 at 9:32
add comment

Your Answer


