Perché albero splay persistenti particolarmente utile nella programmazione funzionale?

Question

Al Splay Alberi è detto pagina di Wikipedia esso (in la sezione Vantaggi):

Possibilità di creare una versione persistente struttura di dati di strombo alberi-, che permette di accedere a entrambe le versioni precedenti e nuovi dopo un aggiornamento. Questo può essere utile nella programmazione funzionale , e richiede ammortizzato O (log n) spazio per l'aggiornamento.

Perché? Come è la programmazione funzionale realizzazione particolarmente uso di albero splay persistenti

Answer 1

Uno degli obiettivi di guida della moderna programmazione funzionale è una migliore gestione dello stato, preferibilmente utilizzando come poco di esso, se necessario, dal momento che i programmi di stateful devono eseguire i comandi nella sequenza corretta da errori evitare.

strutture dati persistenti sono grandi proprio perché non usano stato mutevole, permettendo loro di essere utilizzati nei calcoli puri e immutabili

//mutable tree
var t = new_tree();
add(t, 1);
add(t, 2);
//the tree has now changed so if anyone was depending on the old value
//we will now have a problem

//persistent tree
var t = new_tree();
var t2 = add(t, 1);
var t3 = add(t2, 2);
//t1 and t2 have not changed

La citazione è stato sottolineato è solo sottolineando che le strutture di dati persistenti sono comunemente usati (e privilegiate) in programmazione funzionale pura. Non c'è niente di particolare circa albero splay in questo caso.

Answer 2

La tua domanda sembra provenire da un persistente sfavorevole po 'di confusione terminologica. Una frase migliore potrebbe essere puramente funzionale , vale a dire, la programmazione funzionale senza mutazione distruttiva. La confusione probabilmente nasce dal fatto che, strutture dati persistenti immutabili sono più comuni nella programmazione funzionale nel suo complesso, per una serie di motivi.

In breve, probabilmente si può leggere quella frase come "la creazione di albero splay persistenti può essere utile durante la programmazione con strutture di dati solo immutabili", che confina con il tautologico.

Answer 3

mi piacerebbe anche sostengono il contrario, albero splay sono meno comodo per lavorare con in programmazione funzionale perché è necessario restituire il nuovo albero anche dopo ogni operazione di ricerca e tenere traccia dell'ultimo albero per quasi tutte le operazioni. Inoltre, tutti gli alberi di ricerca che conosco può essere utilizzato direttamente funzionalmente con O (log n) spazio aggiuntivo per operazione. Suppongo che l'unico fatto interessante in quella frase di che il requisito di memoria per soggiorni di funzionamento O (log n) ammortamento, anche se abbiamo ristrutturare l'albero per tutto il tempo, a meno di notare che ora paghiamo quel prezzo lo spazio anche per le ricerche.