Jak zdefiniować drzewiastą DAG w Haskell

Question

Jak można zdefiniować skierowany graf acykliczny (DAG) (ciągów) (z jednego korzenia) najlepiej w Haskell?

Szczególnie należy zastosować następujące dwie funkcje na tej struktury danych tak szybko, jak to możliwe:

1. Znajdź wszystkie (bezpośrednie i pośrednie) przodków jednego elementu (w tym rodziców, rodziców itp).
2. Znajdź wszystkie (bezpośrednio) dzieci jednego elementu.

myślałem [(String,[String])] gdzie każda para ma jeden element wykresu składającej się z jej nazwą (String) oraz listę ciągów ([String]) zawierającego nazwiska rodziców (bezpośrednich) tego elementu. Problem z tą implementacją polega na tym, że trudno jest wykonać drugie zadanie.

Można również ponownie użyć [(String,[String])], podczas gdy lista ciągów znaków ([String]) zawiera nazwy dzieci (bezpośrednich). Ale tutaj znowu ciężko jest wykonać pierwsze zadanie.

Co mogę zrobić? Jakie są alternatywy? Który sposób jest najbardziej efektywny?

EDYCJA: Jeszcze jedna uwaga: chciałbym również, aby łatwo ją zdefiniować. Muszę zdefiniować instancję tego typu danych osobiście "ręcznie", więc chciałbym uniknąć niepotrzebnych powtórzeń.

Answer 1

Czy spojrzałeś na the tree implementtion in Martin Erwig's Functional Graph Library? Każdy węzeł jest reprezentowany jako kontekst zawierający zarówno jego dzieci, jak i ich rodziców. Zobacz klasę typów graph, aby uzyskać dostęp do tego. To może nie być tak łatwe, jak prosiłeś, ale już jest, jest dobrze przetestowane i łatwe w użyciu. Używałem go przez ponad dekadę w dużym projekcie.