Haskell (:) e (++) differenze

Question

Mi dispiace per una domanda come questa. Non sono troppo sicuro della differenza tra l'operatore : e ++ in Haskell.

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

anche

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

come per la funzione inversa che sorse questa domanda per me,

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

Perché non i seguenti lavori?

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

dare un errore di tipo.

Answer 1

L'operatore : è noto come l'operatore "cons" ed è usato per anteporre un elemento di testa a un elenco. Quindi [] è un elenco e x:[] è prepagante x nell'elenco vuoto facendo una lista [x]. Se poi si utilizza y:[x] si finisce con la lista [y, x] che è la stessa di y:x:[].

L'operatore ++ è l'operatore di concatenazione di elenchi che prende due elenchi come operandi e li "combina" in un unico elenco. Quindi se hai la lista [x] e la lista [y] allora puoi concatenarli in questo modo: [x]++[y] per ottenere [x, y].

Si noti che : accetta un elemento e un elenco mentre ++ accetta due elenchi.

Come per il codice che non funziona.

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

La funzione di inversione restituisce una lista. Poiché l'operatore : non accetta un elenco come primo argomento, allora reverse(xs):x non è valido. Ma reverse(xs)++[x] è valido.

Answer 2

: configura un elemento in un elenco.

++ aggiunge due elenchi.

Il primo ha digitare

a -> [a] -> [a] 

mentre il secondo è di tipo

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

Answer 3

concatenazione con (++)

forse sto pensando di profondità in questo, ma, per quanto ho capito, se si tenta di concatenare liste usando (++) ad esempio:

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

(++) deve attraversare la lista di sinistra completa. Dare uno sguardo allo code of (++) lo rende ancora più chiaro.

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

Pertanto, sarebbe preferibile evitare l'uso (++), dal momento che con ogni chiamata reverse(xs)++[x] nell'elenco è sempre più grande (o più piccolo a seconda sul punto di vista. In ogni modo, il programma deve semplicemente attraversare un'altra lista con ogni chiamata)

Esempio:

Diciamo implemento inverso come proposto attraverso la concatenazione.

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

Inversione di una lista [1, 2, 3, 4] apparirebbe un po 'come questo:

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] 

ricorsione in coda utilizzando l'operatore cons (:) !!!

Un metodo per gestire gli stack di chiamate è aggiungere accumulator. (non è sempre possibile aggiungere solo un accumulatore. Ma la maggior parte delle funzioni ricorsive offerte uno con sono primitive recursive e può quindi essere trasformata in tail recursive functions.)

Con l'aiuto dell'accumulatore, è possibile fare questo esempio lavoro, usando l'operatore cons (:). L'accumulatore - ys nel mio esempio - si accumula il risultato corrente e viene trasmesso come parametro. A causa della dell'accumulatore siamo ora in grado di utilizzare le contro all'operatore di accumulare il risultato aggiungendo il capo della nostra lista iniziale ogni volta.

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

C'è una cosa da notare qui.

L'accumulatore è un argomento in più. Non so se Haskell fornisce parametri di default, ma in questo caso sarebbe bello, perché si sarebbe sempre chiamare questa funzione con un elenco vuoto come l'accumulatore in questo modo: reverse' [1, 2, 3, 4] []

v'è abbondanza di letteratura sulla ricorsione in coda e sono sicuro che ci sono un sacco di domande simili su StackExchange/StackOverflow. Si prega di correggermi se trovate errori.

Cordiali saluti,

EDIT 1:

Will Ness ha sottolineato alcuni link per davvero buone risposte per quelli di voi che sono interessati:

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

EDIT 2:

Ok. Grazie a dFeuer e alle sue correzioni penso di capire Haskell un po 'meglio.

1.Il $! è al di fuori della mia comprensione. In tutti i miei test sembrava che lo peggiorasse le cose.

2.As dFeuer sottolineato: Il thunk rappresenta l'applicazione di (:) per x e y è semanticamente identico al x:y ma richiede più memoria. Quindi questo è speciale per l'operatore cons (e costruttori pigri) e non è necessario forzare le cose in alcun modo.

3.If che invece sumUp interi di un elenco utilizzando una funzione molto simile, valutazione rigorosa attraverso BangPatterns o la funzione seq impedirà la pila diventi troppo grande se utilizzati in modo appropriato. ad esempio:

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

Notare il botto di fronte a y. L'ho provato in ghci e lo occupa meno memoria.

Answer 4

cons tende ad essere un costruttore di tipi che un operatore. l'esempio è : può essere uso in let..in.. expresion ma ++ non è

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

tornerà 1 ma

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

restituirà un errore Variable not in scope x

Per rendere più facile, pensare cons così

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

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

Inoltre, se si desidera invertire un array utilizzando cons. Ecco un esempio, la conoscenza è tratto da Prolog

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