Warum hat die funktionale Programmierung keine dynamischen Bäume untersucht?

19

Dynamische Bäume spielen eine wichtige Rolle bei der Lösung von Problemen wie Netzwerkflüssen, dynamischen Graphen, kombinatorischen Problemen ("Dynamic Trees in Practice" von Tarjan und Werneck) und kürzlich zusammengeführten Wörterbüchern ("A Simple Mergeable Dictionary" von Adam Karczmarz).

Unter dynamischen Bäumen verweise ich auf die Definition in Sleator & Tarjans Aufsatz "Eine Datenstruktur für dynamische Bäume" aus dem Jahr 1983. Seitdem wurden im Forschungsbereich der funktionalen Programmierung nur wenige Anstrengungen unternommen.

  1. Edward Kmett hat eine Version der ST-Bäume hauptsächlich als Übersetzung des C ++ - Gegenstücks implementiert (siehe Link-cut trees) .
  2. Chris Okasaki hat eine eingeschränkte Implementierung der Splay-Bäume in seinem bekannten Buch "Rein funktionale Datenstrukturen" geschrieben.
  3. Ralf Hinze und Ross Paterson führten eine funktionale Datenstruktur mit der Bezeichnung 2-3 Finger-Bäume ein, die jedoch ein etwas anderes Ziel verfolgt als die ursprüngliche Definition dynamischer Bäume.

Die Implementierung (und möglicherweise die Leistung) dynamischer Bäume wird in drei Ansätze unterteilt:

  1. Linearisierung, bei der ET-Bäume (Euler-Tour) eine große Rolle spielen. Keine rein funktionale Studie gefunden.
  2. Die Pfadzerlegung, bei der ST-Bäume das Flaggschiff sind, hat gerade die Kmett-Version gefunden.
  3. Baumkontraktion, bei der Top-Bäume, Topologie-Bäume und RC-Bäume die Spieler sind. Keine rein funktionale Studie gefunden.

Eine rein funktionale Analyse und Implementierung findet sich in Splay, AVL, Rot-Schwarz-Baum, aber das sind KEINE dynamischen Bäume. Die ersteren werden als die Schatten- (auch virtuelle oder Hilfs-) Datenstruktur der letzteren betrachtet.

Meine Frage lautet also:

Was sind die Gründe (Nachteile, Schwächen) für die Forschungsgemeinschaft der funktionalen Programmierung, nicht an der dynamischen Baumdatenstruktur teilzunehmen?

data-structures trees functional-programming Richard Chambers
quelle
14
Ich verstehe nicht, wie dies möglicherweise beantwortet werden kann, ohne ein Community-Komitee für maßgebliche funktionale Programmierung zur Bildung offizieller Meinungen zu bilden. Können wir die Frage nicht so umformulieren, dass hier etwas beantwortet werden kann? Soweit ich das beurteilen kann, sollte das OP einfach seine dynamischen Bäume in Haskell oder was auch immer implementieren und dann hierher zurückkehren, um zu berichten, dass es doch getan wurde.
Andrej Bauer
Update auf @AndrejBauer: Das OP hat seine dynamischen Bäume in Haskell implementiert: arxiv.org/abs/1908.11105
jbapple

Antworten:

-1

"In der Informatik ist funktionale Programmierung ein Programmierparadigma. Ein Stil zum Aufbau der Struktur und der Elemente von Computerprogrammen, bei dem Berechnungen als Bewertung mathematischer Funktionen betrachtet werden und Änderungen des Zustands und veränderlicher Daten vermieden werden." - Wikipedia

"sich ändernder Zustand und veränderbare Daten" mit anderen Worten "dynamisch".

Ihre Frage ist also ein bisschen so, als würde man fragen, warum links nicht richtig ist.

Anthony Bachler
quelle
1
Funktionsprogramme können dynamische Daten mit persistenten Datenstrukturen darstellen. Diese Frage stellt sich die Frage, warum die Entwicklung persistenter Datenstrukturen für ein bestimmtes Problem nicht untersucht wurde. Die Frage macht Sinn.
Setzen Sie Monica