Pourquoi les arbres sont ébrasés persistants particulièrement utiles dans la programmation fonctionnelle?

Question

Splay arbres Page Wikipédia il est dit (en la section Avantages):

Possibilité de créer une version de structure de données persistante des arbres qui évasement permet l'accès aux versions précédentes et les nouvelles après une mise à jour. Cela peut être utile dans la programmation fonctionnelle , et nécessite O amorti (log n) l'espace par mise à jour.

Pourquoi? Comment la programmation fonctionnelle de l'utilisation particulary fabrication de arbres Splay persistants

Answer 1

L'un des objectifs de conduite de la programmation fonctionnelle moderne est une meilleure gestion de l'Etat, en utilisant aussi peu de préférence comme nécessaire, étant donné que les programmes doivent exécuter stateful soigneusement les commandes dans la séquence correcte à des erreurs d'éviter.

structures de données persistantes sont très précisément parce qu'ils n'utilisent pas état mutable, leur permettant d'être utilisés dans les calculs purs et immuables

//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 citation vous l'avez dit est tout en soulignant que les structures de données persistantes sont couramment utilisés (et préféré) dans la programmation fonctionnelle pure. Il n'y a rien de particulier sur les arbres ébrasés dans ce cas.

Answer 2

Votre question semble venir d'un peu de confusion persistante malheureux terminological. Une meilleure expression pourrait être purement fonctionnel , à savoir, la programmation fonctionnelle sans mutation destructrice. La confusion vient probablement du fait que immuables, des structures de données persistantes sont plus fréquents dans la programmation fonctionnelle dans son ensemble, pour diverses raisons.

En bref, vous pouvez lire sans doute cette phrase comme « la création d'arbres ébrasés persistants peuvent être utiles lors de la programmation avec seulement des structures de données immuables », qui confine à l'tautologique.

Answer 3

Je même soutenir le contraire, les arbres ébrasés sont moins à l'aise de travailler avec la programmation fonctionnelle parce que vous devez retourner le nouvel arbre, même après chaque opération de recherche et de garder trace du dernier arbre pour presque toutes les opérations. En outre, tous les arbres de recherche que je connais peuvent être directement utilisés fonctionnellement avec O (log n) d'espace supplémentaire par opération. Je suppose que le seul fait intéressant dans cette phrase de que l'exigence de mémoire par des séjours d'opération O (log n) amorti, même si nous restructurons l'arbre tout le temps, mais l'avis que maintenant nous payons ce prix de l'espace, même pour les recherches.