Haskell (:) und (++) Unterschiede

Question

Entschuldigung für eine Frage wie diese. Ich bin mir nicht sicher über den Unterschied der : und ++-Operator in Haskell.

x:y:[] = [x,y] 

auch

[x] ++ [y] = [x,y] 

wie für die umgekehrte Funktion, die mir diese Frage stellt sich,

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

Warum funktioniert die folgende Arbeit?

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

geben einen Typfehler.

Answer 1

Der : Operator wird als der „cons“ Operator bekannt und verwendet, um ein Kopfelement auf eine Liste vorangestellt wird. So [] ist eine Liste und x:[] ist x vor der leeren Liste vor, die eine Liste [x] macht. Wenn Sie dann cons y:[x] Sie am Ende mit der Liste [y, x], die das gleiche wie y:x:[] ist. Der Operator ++ ist der Listenverkettungsoperator, der zwei Listen als Operanden verwendet und sie zu einer einzigen Liste "kombiniert". Wenn Sie also die Liste [x] und die Liste [y] haben, können Sie sie wie folgt verketten: [x]++[y], um [x, y zu erhalten.

Beachten Sie, dass : ein Element und eine Liste enthält, während ++ zwei Listen enthält.

Wie für Ihren Code, der nicht funktioniert.

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

Die umgekehrte Funktion wird zu einer Liste ausgewertet. Da der Operator : keine Liste als erstes Argument annimmt, ist reverse(xs):x ungültig. Aber reverse(xs)++[x] ist gültig.

Answer 2

: wandelt ein Element in eine Liste um.

++ hängt zwei Listen an.

Ersteres hat

a -> [a] -> [a] 

geben, während der letztere Typ hat

[a] -> [a] -> [a] 

Answer 3

Verkettungs mit (++)

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

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

(++) muss die gesamte linke Liste durchlaufen. Ein Blick auf die code of (++) macht es umso klarer.

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

Somit wäre es wünschenswert, (++) zu vermeiden, verwenden, da bei jedem Aufruf reverse(xs)++[x] die Liste wird immer größer (oder kleiner auf der Sicht abhängig. Wie auch immer, hat das Programm einfach eine andere zu durchqueren Liste mit jedem Aufruf)

Beispiel:

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

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

Umkehren einer Liste [1, 2, 3, 4] aussehen würde etwas wie folgt aus:

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] 

Endrekursion die Nachteile Operator (:) !!!

Eine Methode zum Abwickeln von Aufrufstapeln ist das Hinzufügen einer accumulator. (es ist nicht immer möglich ist, nur einen Speicher hinzuzufügen. Aber die meisten der rekursiven Funktionen mit einer Angebot ist primitive recursive und somit in tail recursive functions umgewandelt werden kann.)

Mit Hilfe des Akkumulators ist es möglich zu machen, Dieses Beispiel arbeiten, mit dem Cons-Operator (:). Der Akku - ys in meinem Beispiel - akkumuliert das aktuelle Ergebnis und wird als Parameter weitergegeben. Wegen des Akkumulators sind wir nun in der Lage den cons Operator zu verwenden, um das Ergebnis anzusammeln, indem wir den Kopf unserer ursprünglichen Liste jedes Mal anfügen.

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

Hier ist eine Sache zu beachten.

Der Akku ist ein zusätzliches Argument. Ich weiß nicht, ob Haskell Standardparameter liefert, aber in diesem Fall wäre es schön, weil Sie immer diese Funktion mit einer leeren Liste als der Speicher wie so nennen würde: reverse' [1, 2, 3, 4] []

Es gibt viel Literatur über Schwanz Rekursion und ich bin sicher gibt es viele ähnliche Fragen auf StackExchange/StackOverflow. Bitte korrigieren Sie mich, wenn Sie Fehler finden.

Mit freundlichen Grüßen

EDIT 1:

Will Ness wies einige Links, um wirklich gute Antworten für diejenigen, die interessiert sind:

• Why are difference lists more efficient than regular concatenation?
• Haskell foldl' poor performance with (++)

BEARBEITEN 2:

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

1.Die $! ist jenseits meines Verständnisses. In allen meinen Tests schien es Dinge schlimmer zu machen.

2.As dFeuer hingewiesen: Thunk, die die Anwendung von (:) zu x und y ist semantisch identisch x:y aber mehr Speicher erfolgt. Das ist speziell für den Cons-Operator (und Lazy Constructors) und es gibt keine Notwendigkeit, die Dinge in irgendeiner Weise zu erzwingen.

3. Wenn ich stattdessen SUMUP Ganze Zahlen aus einer Liste eine sehr ähnliche Funktion, strenge Bewertung durch BangPatterns oder die seq Funktion den Stapel zu starkem Anwachsen verhindern, wenn in geeigneter Weise verwendet. Beispiel:

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

Beachten Sie den Knall vor y. Ich habe es in Ghci ausprobiert und es braucht weniger Speicher.

Answer 4

cons tendenziell ein Typ Konstruktor als ein Operator. Das Beispiel hier ist : Verwendung in let..in.. expresion sein kann, aber ++ nicht

let x : xs = [1, 2, 3] in x -- known as type deconstructing 

1 zurück, aber

let [x] ++ [y, z] = [1, 2, 3] in x 

wird ein Fehler Variable not in scope x

zurückkehren, um es einfach, denken Sie an cons zu machen so

data List a = Cons a (List a) -- is equvalent with `data [a] = a:[a]` 

https://en.wikibooks.org/wiki/Haskell/Other_data_structures

Zusätzlich, wenn Sie ein Array mit Widerständen umkehren möchten. Hier ist ein Beispiel wird das Wissen von Prolog genommen

import Data.Function 

reversex1 [] = [] 
reversex1 arr = reversex arr [] 

reversex [] arr = arr 
reversex (x:xs) ys = reversex xs (x:ys) 

main = do 
    reversex1 [1..10] & print