come definire un albero-come DAG in Haskell

Question

Come si fa a definire un diretto grafo aciclico (DAG) (di stringhe) (con una radice) migliore in Haskell?

ho particolarmente bisogno di applicare le seguenti due funzioni in questa struttura di dati il ​​più velocemente possibile:

1. Trova tutti gli antenati (diretti e indiretti) di un elemento (compresi i genitori dei genitori, ecc).
2. Trova tutti i figli (diretti) di un elemento.

ho pensato di [(String,[String])] dove ogni coppia è un elemento del grafico consistente del suo nome (String) e una lista di stringhe ([String]) contenente i nomi dei genitori (diretti) di questo elemento. Il problema con questa implementazione è che è difficile eseguire la seconda attività.

È anche possibile utilizzare [(String,[String])] mentre l'elenco di stringhe ([String]) contiene i nomi dei bambini (diretti). Ma anche qui, è difficile fare il primo compito.

Cosa posso fare? Quali alternative ci sono? Qual è il modo più efficace?

MODIFICA: Un'altra osservazione: mi piacerebbe anche che fosse definito facilmente. Devo definire l'istanza di questo tipo di dati "manualmente", quindi vorrei evitare ripetizioni inutili.

Answer 1

Hai guardato a the tree implementtion in Martin Erwig's Functional Graph Library? Ogni nodo è represso come un contesto che contiene sia i suoi figli che i suoi genitori. Vedi la classe di tipo graph per come accedere a questo. Potrebbe non essere facile come richiesto, ma è già lì, ben testato e facile da usare. L'ho usato per più di un decennio in un grande progetto.