Как вы определяете ориентированный ациклический граф (DAG) (строк) (с одним корнем) лучше всего в Haskell?
Мне особенно нужно как можно быстрее применить следующие две функции в этой структуре данных:
- Найти всех (прямых и косвенных) предков одного элемента (включая родителей родителей и т.д.).
- Найти всех (прямых) дочерних элементов одного элемента.
Я думал о [(String,[String])], где каждая пара является одним элементом графа, состоящим из его имени (String) и списка строк ([String]), содержащих имена (прямых) родителей этого элемента. Проблема с этой реализацией заключается в том, что выполнить вторую задачу сложно.
Вы также можете использовать [(String,[String])] снова, в то время как список строк ([String]) содержит имена (прямых) дочерних элементов. Но здесь снова трудно выполнить первую задачу.
Что я могу сделать? Какие существуют альтернативы? Каков наиболее эффективный способ?
EDIT: Еще одно замечание: мне также хотелось бы, чтобы это было легко определено. Мне нужно определить экземпляр этого типа данных "вручную", поэтому я бы хотел избежать ненужных повторений.
