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