Was ist neu in rein funktionalen Datenstrukturen seit Okasaki?

563

Seit Chris Okasakis 1998 erscheinendem Buch "Rein funktionale Datenstrukturen" sind nicht mehr allzu viele neue aufregende rein funktionale Datenstrukturen aufgetaucht. Ich kann nur einige nennen:

  • IntMap (ebenfalls von Okasaki im Jahr 1998 erfunden, aber in diesem Buch nicht vorhanden)
  • Fingerbäume (und ihre Verallgemeinerung über Monoide)

Es gibt auch einige interessante Möglichkeiten, bereits bekannte Datenstrukturen zu implementieren, z. B. die Verwendung von "verschachtelten Typen" oder "generalisierten algebraischen Datentypen", um Bauminvarianten sicherzustellen.

Welche weiteren neuen Ideen sind seit 1998 in diesem Bereich aufgetaucht?

jkff
quelle
20
Gute Frage. Ich hatte gerade eine Schülerin, die mich danach fragte und die Antwort nicht kannte.
Suresh Venkat
Dies ist hier in Ordnung, aber Sie erhalten möglicherweise bessere Antworten zum Stapelüberlauf. Wenn Sie dort fragen, seien Sie sicher und verlinken Sie zur Diskussion hier.
Charles Stewart
3
Nun, der Haskell Reddit hat dies gesehen, so dass auch von dort einige gute Antworten eingehen werden, aber ausgezeichnete Fragen. Gerade in der Mitte von Okasakis Buch wunderte ich mich, dasselbe auch zu denken. +1
Robert Massaioli

Antworten:

553

Neue rein funktionale Datenstrukturen veröffentlicht seit 1998:

  • 2001: Ideal Hash Trees und sein Vorgänger, Fast And Space Efficient Trie Searches (2000) , von Phil Bagwell : Anscheinend als grundlegender Baustein in Clojures Standardbibliothek verwendet.

  • 2001: Eine einfache Implementierungstechnik für Priority Search Queues von Ralf Hinze : Eine wirklich einfache und schöne Technik zum Implementieren dieser wichtigen Datenstruktur (nützlich zum Beispiel im Dijkstra-Algorithmus). Die Implementierung ist besonders schön und lesbar, da häufig "Ansichtsmuster" verwendet werden.

  • 2002: Bootstrapping einseitiger flexibler Arrays , von Ralf Hinze : Ähnlich wie Okasakis Direktzugriffslisten, aber sie können so angepasst werden, dass sie den zeitlichen Kompromiss zwischen consund der Indizierung ändern .

  • 2003: Neue verkettbare und nicht verkettbare Deques von Radu Mihaescu und Robert Tarjan : Eine neue Version älterer Arbeiten (von Kaplan und Tarjan), die Okasaki zitiert (Die neueste Version von Kaplan & Tarjans Arbeiten wurde im Jahr 2000 veröffentlicht ). Diese Version ist in mancher Hinsicht einfacher.

  • 2005: Maxiphobe Haufen ( Papier und Code ), von Chris Okasaki : Präsentiert nicht als neue, effizientere Struktur, sondern als Möglichkeit, Prioritätswarteschlangen zu unterrichten.

  • 2006: Rein funktionale Worst-Case-Konstante-Time-Catenable-Sorted-Lists von Gerth Stølting Brodal, Christos Makris und Kostas Tsichlas : Beantwortet eine herausragende Frage von Kaplan und Tarjan, indem eine Struktur mit O (lg n) insert, search und delete und O demonstriert wird (1) concat.

  • 2008: Konsequent anhaltende Versuche zur effizienten Versionskontrolle von Erik D. Demaine, Stefan Langerman und Eric Price : Präsentiert mehrere Datenstrukturen für Versuche, die eine effiziente Navigation und Änderung in der Nähe der Blätter ermöglichen. Einige sind rein funktional. Andere verbessern tatsächlich eine langjährige Datenstruktur von Dietz et al. für vollständig persistente (aber nicht konfluent persistente oder rein funktionale) Arrays. In diesem Artikel werden auch rein funktionale Link-Cut-Bäume vorgestellt , die manchmal als "dynamische Bäume" bezeichnet werden.

  • 2010: Ein neuer rein funktionaler Löschalgorithmus für rot-schwarze Bäume von Matt Might : Wie bei Okasakis Einfügealgorithmus für rot-schwarze Bäume handelt es sich hierbei nicht um eine neue Datenstruktur oder eine neue Operation für eine Datenstruktur, sondern um eine neue, einfachere Methode Schreiben Sie eine bekannte Operation.

  • 2012: RRB-Trees: Effiziente unveränderliche Vektoren , von Phil Bagwell und Tiark Rompf : Eine Erweiterung der Hash Array Mapped Tries, die unveränderliche Vektorverkettung, Insert-at und Split-in-O (lg n) -Zeit unterstützt, während der Index aktualisiert wird und Einfügungsgeschwindigkeiten des ursprünglichen unveränderlichen Vektors.

Bekannt aus dem Jahr 1997, aber in Okasakis Buch nicht erwähnt:

  • Viele andere Arten des ausgeglichenen Suchbaums . AVL, Brother, Rank-Balanced, Bounded-Balance und viele andere ausgeglichene Suchbäume können (und wurden) rein funktional durch Pfadkopieren implementiert werden. Besonders zu erwähnen sind vielleicht:

    • Bias Search Trees von Samuel W. Bent, Daniel D. Sleator und Robert E. Tarjan : Ein Schlüsselelement in der Arbeit von Brodal et al. Aus dem Jahr 2006 und in der Arbeit von Demaine et al. Aus dem Jahr 2008.
  • Unendliche Mengen, die eine schnelle, erschöpfende Suche zulassen , von Martín Escardó : Vielleicht keine Datenstruktur an sich .

  • Drei Algorithmen für Braun-Bäume von Chris Okasaki : Braun-Bäume bieten viele Stapeloperationen im ungünstigsten Fall O (lg n). Diese Grenze wird von vielen anderen Datenstrukturen übertroffen, aber Braun-Bäume haben eineconsOperation, die im zweiten Argument faul ist, und können daher auf eine Weise als unendliche Stapel verwendet werden, die andere Strukturen nicht können.

  • Der entspannte Min-Max-Heap: Eine verschmelzbare, doppelendige Prioritätswarteschlange und der KD-Heap: Eine effiziente, mehrdimensionale Prioritätswarteschlange von Yuzheng Ding und Mark Allen Weiss : Diese sind rein funktional, obwohl dies in den Artikeln nicht behandelt wird . Ich denke nicht, dass die erreichten Zeitgrenzen besser sind als die, die durch die Verwendung von Fingerbäumen (von Hinze & Paterson oder Kaplan & Tarjan) als Warteschlangen mit k-dimensionaler Priorität erreicht werden können, aber ich denke, dass die Strukturen von Ding & Weiss weniger Platz beanspruchen .

  • The Zipper von Gérard Huet : In vielen anderen Datenstrukturen (z. B. in Hinze & Patersons Fingerbäumen) wird auf diese Weise eine Datenstruktur umgedreht.

  • Differenzlisten sind O (1) verkettbare Listen mit einer O (n) -Umwandlung in gewöhnliche consListen. Sie sind anscheinend seit der Antike in der Prolog-Gemeinschaft bekannt, wo sie eine O (1) -Umwandlung zu üblichen consListen haben. Die O (1) -Transformation scheint in der traditionellen funktionalen Programmierung unmöglich zu sein, aber Minamids Lochabstraktion aus POPL '98 diskutiert einen Weg, O (1) -Anhängen und O (1) -Transformation in der reinen funktionalen Programmierung zuzulassen. Im Gegensatz zu den üblichen funktionalen Programmierimplementierungen von Differenzlisten, die auf Funktionsabschlüssen basieren, sind Lochabstraktionen (sowohl in ihrer Verwendung als auch in ihrer Implementierung) im Wesentlichen dieselben wie Prolog-Differenzlisten. Es scheint jedoch, dass dies jahrelang die einzige Person war, die dies bemerkteeiner der Rezensenten von Minamide .

  • Einzigartig dargestellte Wörterbücher unterstützen das Einfügen, Aktualisieren und Nachschlagen mit der Einschränkung, dass keine zwei Strukturen, die dieselben Elemente enthalten, unterschiedliche Formen haben können. Beispielsweise werden sortierte, einfach verknüpfte Listen eindeutig dargestellt, herkömmliche AVL-Bäume jedoch nicht. Versuche sind auch einzigartig vertreten. Tarjan und Sundar zeigten in "Einzigartige binäre Suchbaumdarstellungen und Gleichheitsprüfung von Mengen und Sequenzen" ein rein funktionales, einzigartig dargestelltes Wörterbuch, das Suchen in logarithmischer Zeit und Aktualisierungen in . Es verwendet jedoch Speicherplatz. Es gibt eine einfache Darstellung unter Verwendung von Braun-Bäumen , die nur linearen Raum verwendet, aber eine Aktualisierungszeit von hatΘ(nlgn)Θ(O(n)Θ(nlgn)Θ(lg2n)Θ(nlgn) und Suchzeit vonΘ(lg2n)

Hauptsächlich funktionale Datenstrukturen vor, während und nach Okasakis Buch:

  • Viele Verfahren, um Datenstrukturen persistent, vollständig persistent oder konsequent persistent zu machen : Haim Kaplan hat eine hervorragende Umfrage zu diesem Thema verfasst . Siehe auch oben die Arbeit von Demaine et al., Die ein vollständig persistentes Array im -Raum (wobei die Anzahl der jemals an dem Array ausgeführten Operationen ist) und die erwartete demonstrieren .m O ( lg lg n )O(m)mO(lglgn)

  • 1989: Randomisierte Suchbäume von Cecilia R. Aragon und Raimund Seidel : Diese wurden in einem rein funktionalen Setting von Guy E. Blelloch und Margaret Reid-Miller in Fast-Set-Operationen mit Treaps und von Dan Blandford und Guy Blelloch in Functional-Set-Operationen mit diskutiert Treaps ( Code). Sie bieten alle Operationen von rein funktionalen Fingerbäumen und voreingenommenen Suchbäumen, erfordern jedoch eine Zufallsquelle, sodass sie nicht rein funktional sind. Dies kann auch die zeitliche Komplexität der Operationen auf Truppen ungültig machen, vorausgesetzt, ein Gegner kann Operationen zeitlich festlegen und die langen Operationen wiederholen. (Dies ist der gleiche Grund, warum zwingende Amortisationsargumente in einer dauerhaften Einstellung nicht gültig sind, es jedoch einen Gegner mit einer Stoppuhr erfordert.)

  • 1997: Skip-Trees, eine alternative Datenstruktur zu Skip-Listen in einem simultanen Ansatz von Xavier Messeguer und Exploring the Duality Between Skip Lists und Binary Search Trees von Brian C. Dean und Zachary H. Jones : Skip-Listen sind nicht rein funktional, aber sie können funktional als Bäume implementiert werden. Wie Treaps benötigen sie eine Quelle von Zufallsbits. (Es ist möglich, Überspringlisten deterministisch zu gestalten, aber nach der Übersetzung in einen Baum denke ich, dass dies nur eine andere Sichtweise auf 2-3 Bäume ist.)

  • 1998: Alle amortisierten Strukturen in Okasakis Buch! Okasaki erfand diese neue Methode zum Mischen von Amortisations- und funktionalen Datenstrukturen, die zuvor als inkompatibel galten. Es kommt auf das Auswendiglernen an, was, wie Kaplan und Tarjan manchmal erwähnt haben, tatsächlich ein Nebeneffekt ist. In einigen Fällen ( z. B. PFDS auf SSDs aus Leistungsgründen ) kann dies ungeeignet sein.

  • 1998: Simple Confluently Persistent Catenable Lists von Haim Kaplan, Chris Okasaki und Robert E. Tarjan : Verwendet Modifikationen unter der Haube, um amortisierte O (1) -Catenable-Deques zu erhalten, die die gleiche Oberfläche aufweisen wie frühere (rein funktionale, aber mit Memoization ) Version in Okasakis Buch. Kaplan und Tarjan hatten zuvor eine rein funktionale O (1) Worst-Case-Struktur erstellt, die jedoch wesentlich komplizierter ist.

  • 2007: Wie in einer anderen Antwort auf dieser Seite erwähnt, semi-persistente Datenstrukturen und persistente Gewerkschaftsfindung von Sylvain Conchon und Jean-Christophe Filliâtre

Techniken zur Überprüfung funktionaler Datenstrukturen vor, während und nach Okasakis Buch:

Imperative Datenstrukturen oder Analysen, die in Okasakis Buch nicht behandelt wurden, sich aber auf rein funktionale Datenstrukturen beziehen:

jbapple
quelle
5
Ich kann mich nicht erinnern, das Kontrollkästchen "Community-Wiki" für diese Antwort aktiviert zu haben. Gibt es eine Möglichkeit, das rückgängig zu machen?
Jbapple
7
@jbapple: Nach einer bestimmten Anzahl von Änderungen werden alle Beiträge zu Community-Wiki. Das ist eine beeindruckend gründliche Überprüfung. Danke.
Phil Miller
29
Tolle Liste! Was mich wünscht, Okasaki würde eine zweite Ausgabe veröffentlichen.
Radu GRIGore
4
Beachten Sie, dass Isabelle / HOL Code für SML, OCaml, Haskell, Scala generieren kann. Das Haskabelle-Tool kann Haskell auch in Isabelle / HOL importieren.
Makarius
2
Die Terminologie der "Programmextraktion" ist eine von Coq: Sie nehmen einen konstruktiven Beweis und erstellen daraus ein ausführbares Programm, wobei Sie einige Dinge entfernen. In Isabelle wird dies als "Codegenerierung" bezeichnet und funktioniert anders, wobei die HOL- Spezifikationen als Pseudocode verwendet werden und nicht die Beweise. Die Proof-Extraktion in Isabelle / HOL nach Berghofer funktioniert wie Coq, wird aber heutzutage nur noch selten eingesetzt.
Makarius
63

Zu den bereits gemachten hervorragenden Notizen werde ich Reißverschlüsse hinzufügen .

Huet, Gerard. "Functional Pearl: The Zipper" Journal of Functional Programming 7 (5): 549-554, September 1997.

Wikipedia: Reißverschluss (Datenstruktur)

Matt Might
quelle
4
Reißverschlüsse sind super. Für viele Anwendungsfälle ermöglichen sie, dass baumbasierte Darstellungen für viele Arten von Daten die "richtige" Wahl werden, wenn dies sonst etwas komplizierter wäre
Carter Tazio Schonwald,
1
Ein Beispiel für ihre Verwendung zur XML-Manipulation: anti-xml.org/zippers.html
Mechanische Schnecke
40

Conchon, Filliatre, eine persistente UNION-FIND-Datenstruktur und semipersistente Datenstrukturen .

Radu GRIGore
quelle
Wow, ein hartnäckiger UNION-FIND! Vielen Dank!
jkff
3
Nun, irgendwie ... Siehe den Artikel.
Radu GRIGore
1
... oder, wenn Sie es vorziehen, sehen Sie sich Code an (von Matt Parkinson) github.com/septract/jstar/blob/master/src/utils/…
Radu GRIGore
5
Jetzt verstehe ich, warum der Kommentar "kind of .." positiv bewertet wurde. Sie haben nur dann eine gute Leistung, wenn man fast ausschließlich entweder keine Persistenz verwendet oder die ganze Zeit zurückfährt: Wenn Sie häufig sowohl "neue" als auch "alte" Versionen verwenden, sind Sie durchgeknallt. Coole Rerooting-Idee.
jkff
Radus Link kann jetzt unter github.com/septract/jstar-old/blob/…
jbapple am
20

Ich würde McBrides Version von Reißverschlüssen als Ableitungen von Datentypen hinzufügen.

keiner
quelle
Ich liebe das Zeug. Es ist einfach so cool, dass das Derivat eine ganz andere Anwendung hat, als Änderungsraten zu finden!
SamB,
3
SamB, Sie könnten auch an Derivaten regulärer Ausdrücke interessiert sein (falls Sie diese noch nicht kennen).
Jbapple
14

Rangemaps

Es handelt sich um eine spezialisierte Datenstruktur, die jedoch als Ersatz für Martin Erwigs DIET mit geringfügig unterschiedlichen Eigenschaften verwendet werden kann, sodass mindestens eine Datenstruktur zum Vergleich vorhanden ist. Das DIET selbst wurde 1998 in einem Artikel in JFP beschrieben, sodass es möglicherweise nicht in rein funktionale Datenstrukturen aufgenommen wird.

Kompliziert siehe bio
quelle
7

In Anlehnung an das oben verlinkte Papier von 2012 wurde die Arbeit an RRB-Vektoren seitdem erweitert und im ICFP'15 veröffentlicht.

RRB-Vektor: eine praktische, nicht veränderbare Sequenz für allgemeine Zwecke http://dl.acm.org/citation.cfm?id=2784739

Mike Rainey
quelle