Qual è il vantaggio di struttura di dati puramente funzionale?

Question

Ci sono gran numero di testi su strutture di dati, e le librerie di codice strutture di dati. Capisco che la struttura dei dati puramente funzionale è più facile ragionare su. Tuttavia ho difficoltà a capire il vero vantaggio mondo di utilizzare la struttura di dati puramente funzionale nel codice pragmatico (usando il linguaggio di programmazione funzionale o meno) rispetto alla controparte imperativo. Qualcuno può fornire alcuni casi mondo reale, dove puramente funzionale struttura di dati ha un vantaggio e perché?

Gli esempi lungo la linea come io uso data_structure_name in programming_language per fare applicazione perché può fare certain_thing .

Grazie.

PS: cosa intendo per struttura di dati puramente funzionale non è la stessa struttura dati persistente. struttura di dati persistente è una struttura di dati che non cambia ?? Sull'altra mano puramente struttura dati funzionale è una struttura di dati che opera puramente.

Answer 1

strutture di dati puramente funzionale (aka persistente o immutabile) offrono diversi vantaggi:

• Non hai mai di bloccare loro, che migliora estremamente della concorrenza .
• possono condividere struttura, che riduce l'utilizzo della memoria . Si consideri ad esempio la lista [1, 2, 3, 4] in Haskell e alcuni linguaggio imperativo come Java. Per produrre nuovo elenco in Haskell devi solo per creare nuovi cons (coppia di valore e di riferimento-a-next-elemento) e collegarlo alla lista precedente. In Java è necessario creare completamente nuovo elenco non danneggiare quella precedente.
• è possibile rendere le strutture di dati persistenti pigro .
• anche, se si utilizza lo stile funzionale, è possibile non pensare di tempo e la sequenza delle operazioni , e quindi, rendere i programmi più dichiarativa .
• infatti, che la struttura dei dati è immutabile, consente di effettuare alcune ulteriori ipotesi e quindi espandere le capacità del linguaggio . Ad esempio, Clojure utilizza il fatto dell'immutabilità correttamente fornire implementazioni di hashCode () metodo su ciascun oggetto, in modo che qualsiasi oggetto può essere utilizzato come una chiave in una mappa.
• con i dati immutabili e stile funzionale è anche possibile utilizzare liberamente Memoizzazione .

C'è molto di più vantaggi, in generale, è un altro modo di modellare il mondo reale. Questo e di alcuni altri capitoli da SICP vi darà visione più accurata della programmazione con strutture immutabili, i suoi vantaggi e svantaggi.

Answer 2

Oltre alla sicurezza memoria condivisa più puramente strutture di dati funzione anche darvi persistenza , e praticamente gratis. Per esempio, diciamo che ho un set in OCaml, e voglio aggiungere alcuni nuovi valori ad esso posso fare questo:

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

resti a non modificata dopo l'aggiunta di nuovi personaggi (contiene solo annuncio), mentre b contiene ah, e condividono alcuni degli stessi di memoria (con un set è una specie di difficile da dire quanto la memoria è condivisa dal momento che è un albero AVL e la forma dei cambiamenti degli alberi). Posso continuare a fare questo, tenere traccia di tutte le modifiche che ho apportato alla struttura ad albero che mi permette di tornare a uno stato precedente.

Ecco una grande schema dalla Wikipedia su puramente funzionale che mostra i risultati di inserimento del carattere 'e' contro l'albero xs binario:

Answer 3

programmi Erlang utilizzare strutture dati puramente funzionali quasi esclusivamente, e trarre benefici sostanziali scalando quasi senza soluzione di continuità a più core. Poiché i dati (principalmente binari e stringhe di bit) in comune non è mai modificato, non c'è mai una necessità di bloccare tali dati.

Answer 4

Prendete questo piccolo frammento di F #:

let numbers = [1; 2; 3; 4; 5]

Si può dire con certezza al 100% che si tratta di un elenco immutabile di interi da 1 a 5. È possibile passare intorno ad un riferimento a tale elenco e non hanno mai preoccuparsi che la lista potrebbe essere stato modificato. Questa è una ragione sufficiente per me di utilizzare esso.

Answer 5

strutture di dati puramente funzionale presentano i seguenti vantaggi:

• Persistenza:. Le vecchie versioni possono essere riutilizzati con la certezza che non possono sono stati cambiati

• Condivisione:. Molte versioni di una struttura di dati possono essere tenuti in contemporanea con requisiti di memoria solo modesti

• Sicurezza Discussione:. Alcuna mutazione è nascosto all'interno del thunk pigri (se presente) e, di conseguenza, gestito da l'implementazione del linguaggio

• Semplicità:. Non dover tenere traccia dei cambiamenti di stato rende strutture dati puramente funzionali semplice da utilizzare, in particolare nel contesto della concorrenza

• L'incrementalità:. Strutture di dati puramente funzionali sono composti da molte parti molto piccole, che li rende ideali per la garbage collection incrementale che porta ad abbassare le latenze

Si noti che non ho elencato il parallelismo come un vantaggio di strutture di dati puramente funzionali, perché non credo che questo sia il caso. Efficiente multicore parallelismo richiede località prevedibile al fine di cache leva ed evitare di essere collo di bottiglia in materia di accesso condiviso a memoria principale e le strutture di dati puramente funzionali avere, nella migliore delle ipotesi, caratteristiche sconosciute a questo proposito. Di conseguenza, molti programmi che utilizzano strutture di dati puramente funzionali non scala bene quando parallelizzato su un multicore perché spendono tutto il loro tempo in cache miss, a contendersi i percorsi di memoria condivisa.

Quello che intendo per struttura di dati puramente funzionale, non è la stessa struttura di dati persistenti.

C'è una certa confusione qui. Nel contesto di strutture di dati puramente funzionale, la persistenza è un termine usato per riferirsi alla capacità di fare riferimento alle versioni precedenti di una cassetta di sicurezza struttura di dati nella consapevolezza che essi sono ancora validi. Questo è un risultato naturale dell'essere puramente funzionale e, quindi, la persistenza è una caratteristica inerente di tutte le strutture di dati puramente funzionale.