come implementare liste doppiamente collegate

Question

È possibile avere una lista doppiamente collegata in Haskell e qual è la soluzione ideale per implementarle? Sto implementando un grafico delle scene in cui ogni widget ha un genitore e un figlio, ed è vantaggioso esaminare sia il grafico che il grafico.

Answer 1

Non è molto pratico avere una lista doppiamente collegata in Haskell, perché devi costruirlo tutto in una volta.

Ad esempio, immagina di avere un elenco [1, 2, 3, 4, 5] che desideri rendere doppiamente collegato. Ora, immaginiamo come la lista è rappresentata:

data DoubleList a 
    = LeftEnd a (DoubleList a) 
    | Middle a (DoubleList a) (DoubleList a) 
    | RightEnd a (DoubleList a) 

(io uso due costruttori diversi per le due estremità per semplicità)

Per costruire l'elenco di cui sopra, si deve costruire prima il primo elemento:

let e1 = LeftEnd 1 ... 

Ma per costruire il primo elemento, è già bisogno di avere il secondo elemento:

let e1 = LeftEnd 1 e2 
    e2 = Middle 2 e1 ... 

E per il secondo elemento, è necessario il terzo, ecc:

let e1 = LeftEnd 1 e2 
    e2 = Middle 2 e1 e3 
    e3 = Middle 3 e2 e4 
    e4 = Middle 4 e3 e5 
    e5 = RightEnd 5 e4 

Questo è possibile fare in Haskell grazie alla valutazione pigra; questa strategia è chiamata "legare il nodo" (E non devi letteralmente metterlo tutto in un blocco let, puoi dividere la costruzione in funzioni)

Ma, in altre parole, fare un doppio - elenco collegato, è necessario costruirlo tutto in una volta e, se si desidera modificare qualsiasi parte di esso, è necessario utilizzare uno Zipper o semplicemente effettuare una copia completa di esso ogni volta.

Si consiglia di utilizzare invece Data.Sequence, che è un'implementazione di archiviazione sequenziale basata su albero dito ottimizzata. Supporta l'inserimento, la cancellazione e l'iterazione molto veloci pur rimanendo una struttura dati puramente funzionale.

In caso contrario, è possibile utilizzare solo le cerniere, ma utilizzarle per gli alberi anziché per gli elenchi. Ulteriori informazioni su Zippers sono disponibili su Haskell Wiki. Le cerniere si adatterebbero molto bene in questa situazione, perché offrono la funzionalità esatta che stai cercando: se visiti un albero con una chiusura lampo, ottieni l'accesso ai "genitori" della parte dell'albero che stai visitando, ma l'albero stesso non deve contenere i riferimenti genitore.

Answer 2

Dato che in Haskell non si hanno (di solito) oggetti in stile OO, è strano pensare che i dati siano auto-consapevoli. È importante notare che di solito non si fa uso dell'aggregazione nei tipi di dati Haskell, preferendo invece la composizione.

Si potrebbe voler esaminare XMonad per vedere se il loro design corrisponde alle proprie esigenze (il codice è sorprendentemente leggibile).

Si potrebbe anche voler ristrutturare il progetto in modo da non dover mai guardare in alto (ad esempio, passando "callback" per bambini).

Si potrebbe anche voler vedere se è possibile scrivere una cerniera per l'intero grafico.