Nella programmazione funzionale, avere la maggior parte delle strutture dati immutabili richiede più utilizzo della memoria?

L'unica risposta corretta a questo è "a volte". Ci sono molti trucchi che i linguaggi funzionali possono usare per evitare di sprecare memoria. L'immutabilità facilita la condivisione dei dati tra le funzioni e anche tra le strutture di dati, poiché il compilatore può garantire che i dati non saranno modificati. I linguaggi funzionali tendono a incoraggiare l'uso di strutture di dati che possono essere utilizzate efficientemente come strutture immutabili (ad esempio, alberi invece di tabelle hash). Se si aggiunge pigrizia nel mix, come fanno molti linguaggi funzionali, questo aggiunge nuovi modi per risparmiare memoria (aggiunge anche nuovi modi per sprecare memoria, ma non ho intenzione di approfondirlo).

In functional programming since almost all data structure are immutable, when the state has to change a new structure is created. Does this mean a lot more memory usage?

Dipende dalla struttura dei dati, dalle esatte modifiche eseguite e, in alcuni casi, dall'ottimizzatore. Come esempio, consideriamo prepending in un elenco:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

Qui il requisito di memoria aggiuntiva è costante, così come il costo di esecuzione di chiamare prepend . Perché? Poiché prepend crea semplicemente una nuova cella che ha 42 come testata e list1 come coda. Non è necessario copiare o altrimenti iterare su list2 per ottenere ciò. Cioè, ad eccezione della memoria richiesta per memorizzare 42 , list2 riutilizza la stessa memoria utilizzata da list1 . Poiché entrambe le liste sono immutabili, questa condivisione è perfettamente sicura.

Analogamente, quando si lavora con strutture ad albero bilanciate, la maggior parte delle operazioni richiede solo una quantità logaritmica di spazio aggiuntivo perché tutto, ma un percorso dell'albero può essere condiviso.

Per gli array la situazione è leggermente diversa. Ecco perché, in molti linguaggi FP, gli array non sono comunemente usati. Tuttavia, se fai qualcosa come arr2 = map(f, arr1) e arr1 non viene mai più utilizzato dopo questa riga, un ottimizzatore intelligente può effettivamente creare codice che muta arr1 invece di creare un nuovo array (senza influire sul comportamento del programma). In tal caso, la performance sarà come in una lingua imperativa, naturalmente.

Le implementazioni ingenue in effetti esporrebbero questo problema: quando crei una nuova struttura dati invece di aggiornarne una esistente sul posto, devi avere un sovraccarico.

Diverse lingue hanno diversi modi per affrontarlo, e ci sono alcuni trucchi che la maggior parte di loro usa.

Una strategia è garbage collection . Nel momento in cui la nuova struttura è stata creata, o poco dopo, i riferimenti alla vecchia struttura escono dal campo di applicazione e il garbage collector lo preleva immediatamente o abbastanza presto, a seconda dell'algoritmo GC. Ciò significa che mentre c'è ancora un sovraccarico, è solo temporaneo e non crescerà linearmente con la quantità di dati.

Un altro sta selezionando diversi tipi di strutture di dati. Laddove gli array sono la struttura di dati dell'elenco delle cose da fare in lingue imperative (solitamente racchiuse in una sorta di contenitore di riallocazione dinamica come std::vector in C ++), le lingue funzionali preferiscono spesso le liste concatenate. Con un elenco collegato, un'operazione di antefatto ('cons') può riutilizzare l'elenco esistente come coda della nuova lista, quindi tutto ciò che viene realmente allocato è il nuovo elenco. Esistono strategie simili per altri tipi di strutture di dati: set, alberi, nome.

E poi c'è una valutazione lenta, alla Haskell. L'idea è che le strutture dati che crei non siano completamente create immediatamente; invece, sono memorizzati come "thunks" (puoi considerarli come ricette per costruire il valore quando è necessario). Solo quando il valore è necessario il thunk viene espanso in un valore reale. Ciò significa che l'allocazione della memoria può essere posticipata fino a quando la valutazione è necessaria e, a quel punto, è possibile combinare più thunk in un'unica allocazione di memoria.

So solo un po 'di Clojure ed è Immutable Data Structures .

Clojure provides a set of immutable lists, vectors, sets and maps. Since they can't be changed, 'adding' or 'removing' something from an immutable collection means creating a new collection just like the old one but with the needed change. Persistence is a term used to describe the property wherein the old version of the collection is still available after the 'change', and that the collection maintains its performance guarantees for most operations. Specifically, this means that the new version can't be created using a full copy, since that would require linear time. Inevitably, persistent collections are implemented using linked data structures, so that the new versions can share structure with the prior version.

Graficamente, possiamo rappresentare qualcosa di simile a questo:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

Oltre a ciò che è stato detto in altre risposte, vorrei menzionare il linguaggio di programmazione Clean, che supporta i cosiddetti tipi unici . Non conosco questa lingua, ma suppongo che i tipi unici supportino una sorta di "aggiornamento distruttivo".

In altre parole, mentre la semantica dell'aggiornamento di uno stato è che si crea un nuovo valore da uno vecchio applicando una funzione, il vincolo di unicità può consentire al compilatore di riutilizzare gli oggetti dati internamente perché sa che il vecchio valore sarà non essere più referenziato nel programma dopo che il nuovo valore è stato prodotto.

Per maggiori dettagli, vedi per es. la Home page pulita e questo articolo di wikipedia