In che modo i linguaggi di programmazione puramente funzionali si occupano dei dati in rapida evoluzione?

Esiste una vasta gamma di strutture di dati che sfruttano la pigrizia e altri trucchi per ottenere tempi di ammortamento costanti o addirittura (per alcuni casi limitati, come code ) aggiornamenti a tempo costante per molti tipi di problemi. La tesi di dottorato "Strutture dati puramente funzionali" di Chris Okasaki e il libro con lo stesso nome sono esempio (forse il primo principale), ma il campo è avanzato da . Queste strutture dati in genere non solo sono puramente funzionali nell'interfaccia, ma possono anche essere implementate in puro Haskell e in linguaggi simili e sono completamente persistenti.

Anche senza nessuno di questi strumenti avanzati, gli alberi di ricerca binari bilanciati semplici forniscono aggiornamenti in tempo logaritmico, quindi la memoria mutevole può essere simulata nel peggiore dei casi con un rallentamento logaritmico.

Ci sono altre opzioni, che possono essere considerate imbrogli, ma sono molto efficaci per quanto riguarda lo sforzo di implementazione e le prestazioni del mondo reale. Ad esempio, i tipi di tipi lineari o di unicità consentono l'aggiornamento sul posto come strategia di implementazione per un linguaggio concettualmente puro, impedendo al programma di mantenere il valore precedente (la memoria che sarebbe stata modificata). Questo è meno generale delle strutture di dati persistenti: ad esempio, non è possibile creare facilmente un registro di annullamento memorizzando tutte le versioni precedenti dello stato. È ancora uno strumento potente, sebbene AFAIK non sia ancora disponibile nei principali linguaggi funzionali.

Un'altra opzione per introdurre in sicurezza lo stato mutabile in un'impostazione funzionale è la ST monad in Haskell. Può essere implementato senza la mutazione e escludendo le funzioni unsafe* , si si comporta come se fosse solo un involucro di fantasia per passare implicitamente una struttura di dati persistente (cfr State ). Ma a causa di qualche tipo di inganno del sistema che impone l'ordine di valutazione e impedisce la fuga, può essere implementato in modo sicuro con la mutazione sul posto, con tutti i vantaggi in termini di prestazioni.

Una struttura mutabile economica è lo stack di argomenti.

Dai un'occhiata al calcolo fattoriale tipico in stile SICP:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

Come puoi vedere, il secondo argomento di fac viene utilizzato come accumulatore mutabile per contenere il prodotto in rapida evoluzione n * (n-1) * (n-2) * ... . Non c'è nessuna variabile mutabile in vista, tuttavia, e non c'è modo di alterare inavvertitamente l'accumulatore, ad es. da un altro thread.

Questo è, naturalmente, un esempio limitato.

È possibile ottenere liste collegate immutabili con la sostituzione a buon mercato del nodo principale (e per estensione qualsiasi parte a partire dalla testa): basta fare in modo che la nuova punta punti sullo stesso nodo successivo della vecchia testa. Funziona bene con molti algoritmi di elaborazione delle liste (qualsiasi cosa fold -based).

È possibile ottenere prestazioni piuttosto buone dagli array associativi basati per es. su HAMT . Logicamente si riceve un nuovo array associativo con alcune coppie di valori-chiave modificate. L'implementazione può condividere la maggior parte dei dati comuni tra il vecchio e gli oggetti appena creati. Questo non è O (1) però; di solito ottieni qualcosa di logaritmico, almeno nel peggiore dei casi. Gli alberi immutabili, d'altra parte, non subiscono solitamente alcuna penalità di prestazioni rispetto agli alberi mutevoli. Ovviamente, questo richiede un sovraccarico di memoria, solitamente lontano dal proibitivo.

Un altro approccio si basa sull'idea che se un albero cade in una foresta e nessuno lo sente, non ha bisogno di produrre suoni. Cioè, se puoi dimostrare che un po 'di stato mutato non lascia mai alcun ambito locale, puoi mutare i dati al suo interno in modo sicuro.

Clojure ha transienti che sono "ombre" mutevoli di strutture di dati immutabili che non fuoriescono dall'ambito locale. Clean usa Uniques per ottenere qualcosa di simile (se non ricordo male). Rust aiuta a fare cose simili con puntatori unici controllati staticamente.

Quello che chiedi è un po 'troppo ampio. O (1) rimozione e sostituzione da quale posizione? La testa di una sequenza? La coda? Una posizione arbitraria? La struttura dei dati da utilizzare dipende da questi dettagli. Detto questo, 2-3 Finger Trees sembra uno dei dati persistenti più versatili strutture là fuori:

We present 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece.

(...)

Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more.

Generalmente strutture di dati persistenti hanno prestazioni logaritmiche quando si alterano posizioni arbitrarie. Questo può o meno essere un problema, poiché la costante in un algoritmo O (1) può essere alta, e il rallentamento logaritmico potrebbe essere "assorbito" in un algoritmo complessivo più lento.

Ancora più importante, le strutture dati persistenti rendono più facile ragionare sul tuo programma e questa dovrebbe sempre essere la modalità operativa predefinita. Dovresti favorire strutture di dati persistenti laddove possibile, e utilizzare una struttura dati mutevole solo dopo averlo profilato e determinato che la struttura persistente dei dati è un collo di bottiglia per le prestazioni. Qualsiasi altra cosa è l'ottimizzazione prematura.