Mi piacerebbe imparare come creare grafici ed eseguire alcune operazioni locali su di essi in Haskell, ma la domanda non è specifica per Haskell, e invece di grafici potremmo considerare elenchi doppiamente collegati.
Domanda: Quale sarebbe un modo idiomatico o consigliato per implementare una lista doppiamente collegata (o altra struttura di dati doppiamente collegata o circolare) e operazioni su di essa in una lingua che supporta e difende strutture di dati immutabili (Haskell, Clojure, ecc.)? In particolare, come utilizzare gli aggiornamenti sul posto, che sono formalmente vietati dalla lingua?
Posso facilmente immaginare che se alcune operazioni locali vengono eseguite su una lista doppiamente collegata (se un articolo è inserito, ad esempio), potrebbe non essere necessario copiare immediatamente l'intera lista a causa della pigrizia della lingua. Tuttavia, poiché l'elenco è doppiamente collegato, se è modificato in un posto, nessuno dei vecchi nodi può essere utilizzato nella nuova versione dell'elenco e dovrebbero essere in qualche modo contrassegnati, copiati, raccolti in modo prioritario prima o poi . Ovviamente si tratta di operazioni ridondanti se si utilizzerà solo la copia aggiornata della lista, ma aggiungerebbero un "overhead" proporzionale alla dimensione della lista.
Questo significa che per tali compiti i dati immutabili sono semplicemente inappropriati e che i linguaggi dichiarativi funzionali senza supporto "nativo" per i dati mutabili non sono altrettanto validi di quelli imperativi? O c'è qualche soluzione complicata?
P.S. Ho trovato alcuni articoli e presentazioni su questo argomento in Internet, ma ho avuto difficoltà a seguirli, mentre penso che la risposta a questa domanda non dovrebbe richiedere più di un paragrafo e forse un diagramma ... Voglio dire, se non c'è soluzione "funzionale" a questo problema, la risposta probabilmente è "usa C". Se ce n'è uno, allora quanto può essere complicato?
Domande correlate
-
"Strutture dati nella programmazione funzionale" . La mia domanda specifica sull'utilizzo di aggiornamenti sul posto invece di alternative inefficienti non è discussa qui.
-
"Mutazione interna di strutture dati persistenti" . Lì l'enfasi sembra essere sull'implementazione di basso livello in un linguaggio non specificato, mentre la mia domanda riguarda la scelta giusta di una lingua (funzionale o meno) e su possibili soluzioni idiomatiche in linguaggi funzionali.
Citazioni pertinenti
Purely functional programming languages allow many algorithms to be expressed very concisely, but there are a few algorithms in which in-place updatable state seems to play a crucial role. For these algorithms, purely-functional languages, which lack updatable state, appear to be inherently inefficient ([Ponder, McGeer and Ng, 1988]).
- John Launchbury e Simon Peyton Jones, Thread di stato funzionale pigro (1994), anche John Launchbury e Simon Peyton Jones, Stato in Haskell ( 1995). Questi documenti introducono ST costruttore di tipi monadici in Haskell.