Haskell (:) und (++) Unterschiede

Den : Betreiber ist bekannt als der "cons" - operator und wird verwendet, um voran ein head-element einer Liste. So [] ist eine Liste und x:[] ist vor x auf die leere Liste, so daß eine Liste [x]. Wenn Sie dann Nachteile y:[x] Sie am Ende mit der Liste [y, x] das ist das gleiche wie y:x:[].

Den ++ Betreiber ist die Liste operator die zwei Listen, die als Operanden und "kombinieren" Sie in einer einzigen Liste. Also, wenn Sie die Liste [x] und die Liste [y] dann können Sie verketten Sie wie folgt: [x]++[y] zu bekommen [x, y].

Beachten Sie, dass : nimmt ein element und eine Liste während ++ nimmt zwei Listen.

Als für deinen code, der nicht funktioniert.

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

Die reverse-Funktion liefert eine Liste. Da die : operator ist nicht eine Liste als erstes argument dann reverse(xs):x ist ungültig. Aber reverse(xs)++[x] gültig ist.

InformationsquelleAutor der Antwort Vincent Ramdhanie

Verkettung mit (++)

Vielleicht denke ich zu tief in dieses aber,
soweit ich das verstehe, wenn Sie versuchen, Sie zu verketten
Listen mit (++) zum Beispiel:

[1, 2, 3] ++ [4, 5]

(++) Durchlaufen muss, die komplette linke Liste.
Ein Blick auf die code (++) macht es
alle die mehr klar.

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Somit wäre es wünschenswert, zu vermeiden, mit (++)da mit jedem Aufruf
reverse(xs)++[x] die Liste wird immer größer (oder kleiner, je nachdem
auf den Standpunkt. Wie auch immer, das Programm einfach Durchlaufen muss, eine andere
Liste bei jedem Aufruf)

Beispiel:

Können sagen, ich implementieren Umgekehrt wie vorgeschlagen, durch Verkettung.

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs)++[x]

Umkehrung die Liste [1, 2, 3, 4] würde ähnlich Aussehen, wie diese:

reversex [1, 2, 3, 4]
reversex [2, 3, 4]               ++ [1]
reversex [3, 4]           ++ [2] ++ [1]
reversex [4]       ++ [3] ++ [2] ++ [1]
reversex [] ++ [4] ++ [3] ++ [2] ++ [1]
         [] ++ [4] ++ [3] ++ [2] ++ [1]
         [4]       ++ [3] ++ [2] ++ [1]
         [4, 3]           ++ [2] ++ [1]
         [4, 3, 2]               ++ [1]
         [4, 3, 2, 1]

Tail-Rekursion mit dem cons-operator (:)!!!

Einer Methode zum Umgang mit call-stacks wird durch das hinzufügen einer Akkumulator.
(es ist nicht immer möglich, fügen Sie einfach ein Akkumulator. Aber die meisten der
rekursive Funktionen, die man befasst sich mit sind primitiv rekursive und kann somit
umgewandelt werden tail-rekursive Funktionen.)

Mit der Hilfe des Akkumulators ist es möglich, um in diesem Beispiel
funktionieren, mit dem cons-operator (:).
Der Akkumulator -- ys in meinem Beispiel -- sammelt sich das aktuelle Ergebnis und übergeben als parameter. Weil der Akku sind wir nun in der Lage,
die Verwendung der Nachteile Betreiber ansammeln, das Ergebnis ist, indem der
Kopf unserer ersten Liste, jedes mal.

reverse' :: (Ord a) => [a] -> [a] -> [a]
reverse' (x:xs) ys = reverse' xs (x:ys)
reverse' [] ys     = ys

Es ist eine Sache hier zu beachten.

Den Akkumulator ist ein zusätzliches argument. Ich weiß nicht, ob Haskell
bietet Standard-Parameter, aber in diesem Fall wäre es schön,
weil Sie würde immer rufen Sie diese Funktion mit einer leeren Liste
als der Akku in etwa so: reverse' [1, 2, 3, 4] []

Es gibt viel Literatur über die tail-Rekursion und ich bin
sicher, es gibt eine Menge ähnlicher Fragen auf
StackExchange /StackOverflow. Bitte korrigieren Sie mich, wenn Sie Fehler gefunden.

Freundlichen GRÜßEN,

BEARBEITEN 1:

Wird Ness wies darauf hin, dass einige links zu wirklich guten Antworten für diejenigen von Euch, die interessiert sind:

• Warum sind die Differenz-Listen effizienter als normale Verkettung?
• Haskell foldl' schlechte Leistung mit (++)

EDIT 2:

Ok.
Dank dFeuer und seine Korrekturen, ich glaube, ich verstehe, Haskell
ein kleines bisschen besser.

1.Die $! ist jenseits meines Verständnisses. In allen meinen tests schien es zu
machen alles noch schlimmer.

2.Als dFeuer hingewiesen:
Der thunk repräsentieren Sie die Anwendung von (:) zu x und y ist semantisch identisch zu x:y aber braucht mehr Speicher. So das ist das Besondere an den cons-operator
(und faul-Konstruktoren), und es gibt keine Notwendigkeit, die Dinge zu erzwingen, die in irgendeiner Weise.

3.Wenn ich anstatt sumUp ganzen eine Liste mit einer ganz ähnlichen Funktion,
strengen Bewertung durch BangPatterns oder die seq Funktion
wird verhindern, dass der stack wächst zu groß, wenn entsprechend verwendet. z.B.:

sumUp' :: (Num a, Ord a) => [a] -> a -> a
sumUp' (x:xs) !y = reverse' xs (x + y)
sumUp' [] y      = y

Beachten Sie die bang vor y. Ich versuchte es in ghci und es
braucht weniger Speicher.

InformationsquelleAutor der Antwort Nimi