Warum sind persistente Spreizbäume besonders nützlich bei der funktionellen Programmierung?

Question

Auf der Spreizbäume Wikipedia -Seite Es heißt (im Abschnitt Vorteile):

Möglichkeit, eine persistente Datenstrukturversion von Splay -Bäumen zu erstellen, die nach einem Update den Zugriff sowohl auf die vorherigen als auch auf die neuen Versionen ermöglicht. Dies kann bei der funktionalen Programmierung nützlich sein, und erfordert amortisierte o (log n) Platz pro Update.

Warum ist das so? Wie nutzt funktionelle Programmierspartikel von Verwendung von anhaltende Spreizbäume?

Answer 1

Eines der treibenden Ziele der modernen funktionalen Programmierung ist eine bessere Verwaltung des Staates, das vorzugsweise so wenig davon wie nötig verwendet wird, da staatliche Programme die Befehle in der richtigen Reihenfolge sorgfältig ausführen müssen, um Fehler zu vermeiden.

Persistente Datenstrukturen sind genau darauf, dass sie keinen veränderlichen Zustand verwenden, sodass sie in reinen und unveränderlichen Berechnungen verwendet werden können

//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

Das von Ihnen hingewiesene Zitat betont nur, dass in der reinen funktionellen Programmierung häufig anhaltende Datenstrukturen verwendet (und bevorzugt) werden. In diesem Fall ist nichts Besonderes an Spreizbäumen.

Answer 2

Ihre Frage scheint aus einer anhaltend unglücklichen terminologischen Verwirrung zu stammen. Ein besserer Satz könnte sein rein funktionell, dh funktionelle Programmierung ohne destruktive Mutation. Die Verwirrung ergibt sich wahrscheinlich aus der Tatsache, dass unveränderliche, anhaltende Datenstrukturen aus einer Vielzahl von Gründen häufiger bei der funktionellen Programmierung als Ganzes auftreten.

Kurz gesagt, Sie können diesen Ausdruck wahrscheinlich als "Erzeugung anhaltender Spreizbäume können nützlich sein, wenn sie mit nur unveränderlichen Datenstrukturen programmiert werden", was an die Tautologischen grenzt.

Answer 3

Ich würde sogar das Gegenteil argumentieren, Spreizbäume sind weniger bequem in der funktionalen Programmierung, da Sie den neuen Baum auch nach jedem Fundoperation zurückgeben und den letzten Baum für fast alle Operationen verfolgen müssen. Außerdem können alle Suchbäume, die ich kenne, direkt mit O (log n) zusätzlicher Raum pro Betrieb verwendet werden. Ich nehme an, die einzig interessante Tatsache in diesem Satz, dass die Speicheranforderung pro Operation o (log n) amortisiert bleibt, obwohl wir den Baum ständig umstrukturieren, aber feststellen, dass wir jetzt diesen Platzpreis sogar für Suchanfragen zahlen.