How to define a tree-like DAG in Haskell

Question

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.

Answer 1

Have you looked at the tree implemention in Martin Erwig's Functional Graph Library? Each node is represented 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.