Die meisten funktionalen Sprachen verwenden verknüpfte Listen als primäre unveränderliche Datenstruktur. Warum Listen und nicht zB Bäume? Bäume können auch Pfade und sogar Modelllisten wiederverwenden.
functional-programming
Filip Haglund
quelle
quelle
Antworten:
Weil Listen einfacher sind als Bäume. (Sie können dies trivial daran erkennen, dass eine Liste ein entarteter Baum ist, bei dem jeder Knoten nur ein einziges untergeordnetes Element hat.)
Die Cons-Liste ist die einfachste mögliche rekursive Datenstruktur beliebiger Größe.
Guy Steele argumentierte beim Entwurf der Programmiersprache Fortress, dass für die massiv parallelen Berechnungen der Zukunft sowohl unsere Datenstrukturen als auch unser Kontrollfluss baumförmig mit mehreren Verzweigungen sein sollten, nicht linear wie sie jetzt sind. Vorläufig wurden die meisten unserer zentralen Datenstrukturbibliotheken jedoch mit sequentieller, iterativer Verarbeitung (oder Endrekursion, es ist eigentlich egal, sie sind dasselbe) und nicht mit paralleler Verarbeitung entwickelt.
Beachten Sie, dass z. B. in Clojure, dessen Datenstrukturen speziell für die parallele, verteilte, "wolkige" Welt von heute entworfen wurden, sogar Arrays (in Clojure Vektoren genannt), die wahrscheinlich "linearste" Datenstruktur von allen, tatsächlich als implementiert werden Bäume.
Kurz gesagt: Eine Cons-Liste ist die einfachste beständige rekursive Datenstruktur, und es war nicht erforderlich, einen komplizierteren "Standard" zu wählen. Andere sind natürlich als Optionen verfügbar, z. B. Haskell hat Arrays, Prioritätswarteschlangen, Maps, Heaps, Treaps, Versuche und alles, was Sie sich vorstellen können, aber die Standardeinstellung ist die einfache Liste der Nachteile.
quelle
data Tree a = Leaf a | Branch a (Tree a) (Tree a)
. Dies untermauert Ihr Argument der "Einfachheit".Sequence
oder ScalaVector
), aber verwenden Sie keine Bäume, wenn sie nur gelesen werden müssen, da sie dies in echter konstanter Zeit erreichen können (z. B. Haskell'sVector
oder F # via .Net'sImmutableArray
)pmap
greift das Pingen über einen Vektor in Clojure immer noch nacheinander auf jedes Element zu; Die Baumstruktur des Vektors ist im Allgemeinen für den Endbenutzer nicht sichtbar.Eigentlich diese Listen sind Bäume! Sie haben Knoten mit zwei Feldern
car
undcdr
, die mehrere solcher Knoten oder Blätter enthalten können. Das einzige, was diese Bäume zu Listen macht, ist die Konvention, die Verknüpfung als Verknüpfung zum nächsten Knoten in einer linearen Liste und die Verknüpfung als Wert des aktuellen Knotens zu interpretieren .cdr
car
Das heißt, ich vermute, dass die Prävalenz von verknüpften Listen in der funktionalen Programmierung mit der Prävalenz von Rekursion über Iteration zusammenhängt. Wenn Ihr einziges Schleifenkonstrukt die (End-) Rekursion ist, möchten Sie Datenstrukturen, die damit einfach zu verwenden sind. und verknüpfte Listen sind perfekt dafür.
quelle