Haskell: Zugriff auf Listen von hinten

Question

Heute habe ich angefangen, Haskell zu lernen. Ich bin ziemlich neu mit funktionalen Sprachen, und Haskell gefällt mir sehr gut.

Ich habe jedoch eine Frage zum Design, die mich stört: Nach dem, was ich bisher verstanden habe, sieht es so aus, als ob der Zugriff auf ein Element im hinteren Teil einer Liste viel komplizierter ist als der Zugriff auf ein Element im vorderen Teil (etwas wie xs:x wobei xs::[a] y x::a scheint nicht möglich zu sein).

(Soweit ich das verstanden habe) ist es möglich, eine Liste an eine andere anzuhängen ( xs++[a] ), aber es kostet mehr Laufzeit (es muss die gesamte Liste durchlaufen werden) und kann nicht für den Mustervergleich verwendet werden.

Warum fehlt in Haskell eine solche Operation?

Answer 1

Der Datentyp "Liste

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

ist wie oben definiert. Es gibt nur zwei Muster, denen Sie entsprechen können: [] y x : xs donde x ist der Kopf und xs ist der Schwanz.

Voranstellen einer Liste

a = 1 : 2 : []
b = 0 : a

 (:) <-- b
 / \\  
0  (:)  <-- a
   / \\
  1  (:)
     / \\
    2   \[\]

fügt einfach eine neue Cons-Zelle hinzu und verwendet die ursprüngliche Liste als Ende.

Beachten Sie jedoch, dass Haskell-Datenstrukturen unveränderlich sind. Anhängen an das Ende einer Liste

a = 1 : 2 : []
b = a ++ [3]

 (:) <-- a      (:) <-- b
 / \\            / \\
1  (:)         1  (:)
   / \\            / \\
  2   \[\]         2  (:)
                    / \\
                   3   \[\]

erfordert die Erstellung einer völlig neuen Liste, da kein Teil der ursprünglichen Struktur wiederverwendet werden kann.

In der Tat, bedenken Sie

a = 0 : a
b = 0 : [ x+1 | x <- b ]

 (:) <-- a         (:) <-- b
 / \\               / \\
0  (:) <-- a      0  (:) <-- \[ x+1 | x <- b \]
   / \\               / \\
  0  (:) <-- a      1  (:) <-- \[ x+1 | x <- \[ x+1 | x <- b \] \]
     ...               ...

Wie würden Sie jemals das letzte Element der Liste erhalten oder an das Ende anhängen?

Es gibt weitere Datenstrukturen wie dequeue s, die sowohl für den vor- als auch für den rückseitigen Zugriff besser geeignet sind.

Answer 2

Der Datentyp Liste in Haskell ist eine verkettete Liste, so dass ein Lookup O(n) Zeit benötigt. Wenn Sie häufig auf den hinteren Teil einer Liste zugreifen müssen, sollten Sie einen Blick auf Data.Sequence die O(1) am Anfang und Ende hat.

Die Antwort auf die Frage, warum Haskell diese Datenstruktur als "Standardcontainer" (wie C und Arrays) verwendet, ist, dass Haskell eine rein funktionale Sprache ist und daher rein funktionale Datenstrukturen (unveränderlich und persistent) bevorzugt. diese Wikiseite . Um nicht-funktionale Datenstrukturen in Haskell zu verwenden, müssten sie innerhalb der IO ou ST Monade.

Answer 3

Es ist das Problem mit der reinen List-Datenstruktur, nicht mit Haskell selbst. Sie können lesen Rein funktionale Datenstrukturen Papier, um mehr über andere reine Datenstrukturen zu erfahren, die bei solchen Operationen eine bessere Leistung erbringen können

Answer 4

Scheuen Sie sich nicht, Ihre Liste bei Bedarf umzukehren(). Es ist nicht ungewöhnlich, eine Liste umzukehren, bevor man sie an eine rekursive Funktion übergibt, oder das Endergebnis einer fold()-Funktion umzukehren.

Answer 5

Das sind keine Probleme mit der Sprache, sondern nur mit dem Datentyp List, der zwar eine spezielle Syntax hat, aber ansonsten nicht gerade ein "integraler Bestandteil von Haskell" ist. Das gleiche Problem hat man in C mit einfach verketteten Listen, aber das ist offensichtlich kein Problem der Programmiersprache C.

Wenn Sie eine doppelt verkettete Liste mit Schwanzzeiger wollen, dann erstellen Sie einen solchen Datentyp und verwenden Sie ihn! Vielleicht möchten Sie weitere Datentypen lernen (siehe die Container Paket, Vektor und die dlist Paket für Beispiele).