Was ist neu in rein funktionalen Datenstrukturen seit Okasaki?

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?

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(\sqrt{n})$$\Theta(n \lg n)$Θ(lg2n$\Theta(\sqrt{n \lg n})$ und Suchzeit von$\Theta(\lg^2 n)$

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)$$m$$O(\lg \lg n)$

• 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:

• Phantomtypen sind eine alte Methode zum Erstellen einer API, die bestimmte fehlerhafte Operationen nicht zulässt. Eine raffinierte Anwendung finden Sie in Oleg Kiselyov und Chung-chieh Shans Lightweight Static Capabilities .

• Verschachtelte Typen sind nicht aktueller als 1998 - Okasaki verwendet sie sogar in seinem Buch. Es gibt viele andere Beispiele, die nicht in Okasakis Buch stehen. manche sind neu und manche alt. Sie beinhalten:

  • Stefan Kahrs ' rot-schwarze Bäume mit Typen ( Code )
  • Ross Patersons AVL-Bäume ( Spiegel )
  • Chris Okasaki's Von der schnellen Potenzierung zur quadratischen Matrix: ein Abenteuer in Typen
  • Richard S. Bird und Ross Petersons de Bruijn-Notation als verschachtelter Datentyp
  • Ralf Hinzes numerische Darstellungen als übergeordnete verschachtelte Datentypen .

• GADTs sind auch nicht allzu neu. Sie sind ein Neuzugang bei Haskell und einigen MLs, aber ich glaube, sie sind seit den 1970er Jahren in verschiedenen typisierten Lambda-Kalkülen vorhanden .

• 2004-2010: Coq und Isabelle für die Richtigkeit . Mehrere Personen haben Theorembeweiser verwendet, um die Richtigkeit rein funktionaler Datenstrukturen zu überprüfen. Coq kann diese Überprüfungen in Arbeitscode in Haskell, OCaml und Scheme extrahieren. Isabelle kann nach Haskell, ML und OCaml extrahieren.

  • Coq:
    • Pierre Letouzey und Jean-Christophe Filliâtre formalisierten Rot-Schwarz- und AVL-Bäume und fanden dabei einen Fehler in der OCaml-Standardbibliothek .
    • Ich habe Brodal und Okasakis asymptotisch optimale Prioritätswarteschlangen formalisiert .
    • Arthur Charguéraud formalisierte 825 der 1.700 Zeilen ML in Okasakis Buch .
  • Isabelle:
    • Tobias Nipkow und Cornelia Pusch haben AVL-Bäume formalisiert .
    • Viktor Kuncak formalisierte unausgeglichene binäre Suchbäume .
    • Peter Lammich veröffentlichte The Isabelle Collections Framework , das Formalisierungen effizienter rein funktionaler Datenstrukturen wie rot-schwarzer Bäume und Versuche sowie Datenstrukturen enthält, die weniger effizient sind, wenn sie dauerhaft verwendet werden, wie Zwei-Stapel-Warteschlangen (ohne Okasakis Faulheitstrick) ) und Hash-Tabellen.
    • Peter Lammich veröffentlichte auch Formalisierungen von Baumautomaten , Hinze & Pattersons Fingerbäumen (mit Benedikt Nordhoff und Stefan Körner) sowie Brodal und Okasakis rein funktionalen Prioritätswarteschlangen (mit Rene Meis und Finn Nielsen).
    • René Neumann formalisierte Warteschlangen mit Binomialpriorität .

• 2007: Refined Typechecking with Stardust , von Joshua Dunfield : In diesem Artikel werden Verfeinerungstypen für ML verwendet, um Fehler in der rot-schwarzen Baumlöschfunktion von SMLNJ zu finden.

• 2008: Leichte semiformale Zeitkomplexitätsanalyse für rein funktionale Datenstrukturen von Nils Anders Danielsson : Verwendet Agda mit manueller Annotation, um Zeitgrenzen für einige PFDS zu beweisen.

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

• The Soft Heap: Eine Warteschlange mit ungefährer Priorität und optimaler Fehlerrate von Bernard Chazelle : Diese Datenstruktur verwendet keine Arrays und hat daher zuerst den IRC-Kanal #haskell und später die Benutzer von Stack Overflow in Versuchung geführt, enthält jedochdeletein o (lg n) Dies ist in der Regel in einem funktionalen Umfeld nicht möglich, und eine zwingend amortisierte Analyse, die in einem rein funktionalen Umfeld nicht gültig ist.

• Ausgeglichene binäre Suchbäume mit O (1) Finger-Updates . Um Datenstrukturen persistent zu machen , präsentieren James R. Driscoll, Neil Sarnak, Daniel D. Sleator und Robert E. Tarjan eine Methode zum Gruppieren der Knoten in einem rot-schwarzen Baum, sodass persistente Aktualisierungen nur O (1) Platz benötigen. Die von Tarjan, Kaplan und Mihaescu entworfenen rein funktionalen Deques und Fingerbäume verwenden alle eine sehr ähnliche Gruppierungstechnik, um O (1) -Updates an beiden Enden zu ermöglichen. AVL-Bäume für die lokalisierte Suche von Athanasios K. Tsakalidis funktionieren ähnlich.

• Schnellere Paarungshaufen oder bessere Grenzen für Paarungshaufen : Seit der Veröffentlichung von Okasakis Buch sind mehrere neue Analysen von imperativen Paarungshaufen erschienen, einschließlich Paarungshaufen mit O (log log n) senken Kosten von Amr Elmasry und Hin zu einer endgültigen Analyse von Paarungshaufen von Seth Pettie. Es ist möglich, einige dieser Arbeiten auf Okasakis faule Paarungshaufen anzuwenden.

• Deterministisch voreingenommen Finger Bäume : In Biased Skip-Liste , die von Amitabha Bagchi, Adam L. Buchsbaum und Michael T. Goodrich, ein Entwurf ist für deterministische voreingenommen Sprunglisten dargestellt. Durch die oben erwähnte Sprunglisten- / Baumtransformation kann es möglich sein, deterministisch voreingenommene Suchbäume zu erstellen. Die von John Iacono und Özgür Özkan in Mergeable Dictionaries beschriebenen Finger- Bias-Überspringlisten könnten dann auf Bias- Überspringbäumen möglich sein. Ein voreingenommener Fingerbaum wird von Demaine et al. in ihrem Artikel über rein funktionale Versuche (siehe oben), um die zeitlichen und räumlichen Grenzen der Fingeraktualisierung bei Versuchen zu verringern.

• Der String-B-Tree: Eine neue Datenstruktur für die Suche nach Strings im externen Speicher und ihre Anwendungen von Paolo Ferragina und Roberto Grossi ist eine gut untersuchte Datenstruktur, die die Vorteile von Try und B-Tree kombiniert.

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)

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

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

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.

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