Warum sind mit funktionaler Programmierung Nachteile verbunden?

22

Mir ist aufgefallen, dass die meisten funktionalen Sprachen eine einfach verknüpfte Liste (eine "Nachteile" -Liste) als ihre grundlegendsten Listentypen verwenden. Beispiele hierfür sind Common Lisp, Haskell und F #. Dies unterscheidet sich von Standardsprachen, bei denen die systemeigenen Listentypen Arrays sind.

Warum das?

Für Common Lisp (dynamisch getippt) habe ich die Idee, dass die Nachteile allgemein genug sind, um auch die Basis für Listen, Bäume usw. zu sein. Dies könnte ein winziger Grund sein.

Für statisch typisierte Sprachen kann ich jedoch keine gute Begründung finden, ich kann sogar Gegenargumente finden:

  • Der funktionale Stil fördert die Unveränderlichkeit, daher ist das einfache Einfügen der verknüpften Liste weniger von Vorteil.
  • Der funktionale Stil fördert die Unveränderlichkeit, also auch den Datenaustausch. Ein Array lässt sich leichter "teilweise" teilen als eine verknüpfte Liste.
  • Sie können den Mustervergleich auch für ein reguläres Array durchführen, und noch besser (Sie können beispielsweise leicht von rechts nach links falten).
  • Darüber hinaus erhalten Sie freien Zugang,
  • Und (ein praktischer Vorteil) wenn die Sprache statisch geschrieben ist, können Sie ein reguläres Speicherlayout verwenden und eine Geschwindigkeitssteigerung aus dem Cache erhalten.

Warum also verknüpfte Listen bevorzugen?

programming-languages functional-programming list linked-list Kos
quelle
4
Aus den Kommentaren zu der Antwort von @ sepp2k muss meiner Meinung nach an array is easier to share "partially" than a linked listgeklärt werden, was Sie meinen. Aufgrund ihrer rekursiven Natur ist meines Wissens das Gegenteil der Fall - Sie können eine verknüpfte Liste zum Teil einfacher freigeben, indem Sie einen beliebigen Knoten darin übergeben, während ein Array Zeit für die Erstellung einer neuen Kopie benötigen würde. Bei der gemeinsamen Nutzung von Daten können zwei verknüpfte Listen auf dasselbe Suffix verweisen, was bei Arrays einfach nicht möglich ist.
Izkata
Wenn sich ein Array als Offset, Länge, Puffer-Tripel definiert, können Sie ein Array gemeinsam nutzen, indem Sie ein neues Array mit Offset + 1, Länge-1, Puffer erstellen. Oder Sie haben einen speziellen Array-Typ als Subarray.
Dobes Vandermeer
@Izkata Wenn wir über Arrays sprechen, meinen wir selten nur einen Puffer wie einen Zeiger auf den Beginn des zusammenhängenden Speichers in C. In der Regel meinen wir eine Art Struktur, die die Länge und einen Zeiger auf den Beginn eines umbrochenen Puffers speichert. Unter einem solchen System kann eine Slicing-Operation ein Subarray zurückgeben, dessen Pufferzeiger auf halbem Weg in den Puffer zeigt (am ersten Element des Subarrays) und dessen Anzahl so ist, dass Sie mit start + count das letzte Element erhalten. Solche Slicing-Operationen sind O (1) in Zeit und Raum
Alexander - Reinstate Monica

Antworten:

22

Der wichtigste Faktor ist, dass Sie einer unveränderlichen einfach verknüpften Liste in O (1) -Zeit voranstellen können, wodurch Sie rekursiv n-Element-Listen in O (n) -Zeit wie folgt aufbauen können:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

Wenn Sie dies mit unveränderlichen Arrays durchführen, ist die Laufzeit quadratisch, da bei jeder consOperation das gesamte Array kopiert werden muss, was zu einer quadratischen Laufzeit führt.

Der funktionale Stil fördert die Unveränderlichkeit, also auch den Datenaustausch. Ein Array lässt sich leichter "teilweise" teilen als eine verknüpfte Liste

Ich gehe davon aus, dass mit "teilweiser" Freigabe gemeint ist, dass Sie ein Subarray aus einem Array in O (1) -Zeit nehmen können, während Sie bei verknüpften Listen nur in O (1) -Zeit den Schwanz nehmen können und alles andere O (n) benötigt. Das ist wahr.

In vielen Fällen reicht es jedoch aus, den Schwanz zu nehmen. Und Sie müssen berücksichtigen, dass es Ihnen nicht hilft, Subarrays kostengünstig zu erstellen, wenn Sie keine Möglichkeit haben, Arrays kostengünstig zu erstellen. Und (ohne clevere Compiler-Optimierungen) gibt es keine Möglichkeit, ein Array Schritt für Schritt kostengünstig aufzubauen.

sepp2k
quelle
Das stimmt überhaupt nicht. Sie können Arrays in amortisiertem O (1) anhängen.
DeadMG
10
@DeadMG Ja, aber nicht zu unveränderlichen Arrays.
29.
"teilweise teilen" - Ich denke beide, dass zwei Nachteile Listen auf die gleiche Suffix-Liste zeigen können (weiß nicht, warum Sie dies wollen), und dass Sie einen Mittelpunkt anstelle des Beginns der Liste an eine andere Funktion übergeben können, ohne kopieren zu müssen it (das habe ich schon oft gemacht)
Izkata
@Izkata Das OP sprach jedoch davon, Arrays teilweise gemeinsam zu nutzen, nicht von Listen. Ich habe auch noch nie gehört, was Sie als partielles Teilen bezeichnen. Das ist nur Teilen.
SEPP2K
1
@Izkata Das OP verwendet den Begriff "Array" genau dreimal. Einmal gesagt, dass FP-Sprachen verknüpfte Listen verwenden, während andere Sprachen Arrays verwenden. Einmal, um zu sagen, dass Arrays eine bessere Teilfreigabe bieten als verknüpfte Listen, und einmal, um zu sagen, dass Arrays genauso gut mit Mustern abgeglichen werden können (wie verknüpfte Listen). In allen Fällen stellt er Arrays und verknüpfte Listen gegenüber (um zu verdeutlichen, dass Arrays als primäre Datenstruktur nützlicher sind als verknüpfte Listen, was zu seiner Frage führt, warum verknüpfte Listen in FP bevorzugt werden), sodass ich nicht verstehe, wie er könnte die Begriffe austauschbar sein.
29.
4

Ich denke, es kommt darauf an, dass Listen ziemlich einfach in funktionalen Code implementiert werden können.

Planen:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Arrays sind schwieriger und bei weitem nicht so schön zu implementieren. Wenn Sie möchten, dass sie extrem schnell sind, müssen sie auf niedriger Ebene geschrieben werden.

Darüber hinaus funktioniert die Rekursion in Listen viel besser als in Arrays. Betrachten Sie die Häufigkeit, mit der Sie eine Liste rekursiv konsumiert / generiert haben, im Vergleich zu einem indizierten Array.

Pubby
quelle
Ich würde nicht sagen, dass es richtig ist, Ihre Schema-Version als Implementierung von verknüpften Listen zu bezeichnen. Sie können es nur zum Speichern von Funktionen verwenden. Es ist auch schwieriger (tatsächlich unmöglich), Arrays in einer Sprache zu implementieren, die diese nicht unterstützt (oder Speicherabschnitte), während verknüpfte Listen nur Strukturen, Klassen, Datensätze oder algebraische Datentypen erfordern. Das ist nicht spezifisch für funktionale Programmiersprachen.
29.
@ sepp2k Was meinst du mit "alles andere als Funktionen speichern" ?
Pubby
1
Was ich damit meinte war, dass Listen, die auf diese Weise definiert wurden, nichts speichern können, was keine Funktion ist. Das stimmt aber nicht. Keine Ahnung, warum ich das gedacht habe. Das tut mir leid.
29.
2

Eine einfach verknüpfte Liste ist die einfachste persistente Datenstruktur .

Persistente Datenstrukturen sind für eine performante, rein funktionale Programmierung unerlässlich.

Zickzack
quelle
1
dies scheint nur wiederholen Punkt gemacht und erklärte in der Top-Antwort , die vor mehr als 4 Jahren geschrieben wurde
gnat
3
@gnat: In der oberen Antwort werden persistente Datenstrukturen nicht erwähnt, oder einfach verknüpfte Listen sind die einfachste persistente Datenstruktur, oder sie sind für eine performante, rein funktionale Programmierung unerlässlich. Ich kann überhaupt keine Überschneidung mit der Top-Antwort finden.
Michael Shaw
2

Sie können Cons-Knoten nur dann problemlos verwenden, wenn Sie über eine Garbage-Collected-Sprache verfügen.

Die Nachteile von Nodes stimmen weitgehend mit dem funktionalen Programmierstil von rekursiven Aufrufen und unveränderlichen Werten überein. So passt es gut in das mentale Programmiermodell.

Und vergessen Sie nicht die historischen Gründe. Warum werden sie immer noch Cons Nodes genannt und nutzen immer noch Auto und CDR als Zugriffsmethoden? Die Leute lernen es aus Lehrbüchern und Kursen und benutzen es dann.

Sie haben Recht, in der Realität sind Arrays viel einfacher zu verwenden, belegen nur die Hälfte des Speicherplatzes und sind aufgrund von Ausfällen auf Cache-Ebene viel performanter. Es gibt keinen Grund, sie mit imperativen Sprachen zu verwenden.

Lothar
quelle
1

Verknüpfte Listen sind aus folgendem Grund wichtig:

Wenn Sie eine Zahl wie 3 nehmen und in eine Nachfolgereihenfolge wie konvertieren, verwenden Sie succ(succ(succ(zero)))die Substitution mit{succ=List node with some memory space} , und {zero = end of list}, werden Sie mit einer verknüpften Liste am Ende (der Länge 3).

Der eigentliche wichtige Teil ist Zahlen, Substitution und Speicherplatz und Null.

tp1
quelle