2009-11-30 5 views
25

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

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.

+2

Come nota a margine, si può (e dovrebbe) chiamata senza l'utilizzo di parentesi: 'inversa (x: xs) = xs invertire ++ [x]', o verrai inciampato quando lavori con funzioni con più argomenti. –

+3

Non chiamare funzioni come 'func (arg)'. Quello è il povero Haskell. Chiamate sempre funzioni come 'func arg'.Il codice con spazi chiari rende il codice più sicuro e leggibile. – AJFarmar

risposta

46

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.

16

: configura un elemento in un elenco.

++ aggiunge due elenchi.

Il primo ha digitare

a -> [a] -> [a] 

mentre il secondo è di tipo

[a] -> [a] -> [a] 
+1

Per "Lisp-vocabulary-challenge", "cons" costruisce un nuovo nodo di lista e lo aggiunge al capo della lista. –

6

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:

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.

+0

Haskell non fa mai ritardare pigramente l'applicazione di un costruttore pigro (perché non c'è mai alcun vantaggio nel farlo), quindi non è necessario, e senza alcun vantaggio, forzare manualmente quei risultati. Potresti anche finire per rallentare le cose forzando cose già valutate! – dfeuer

+0

@dfeuer Non sono troppo sicuro di Haskell in termini di rigore. https://wiki.haskell.org/Performance/Accumulating_parameter suggerisce tuttavia che si dovrebbe prendere in considerazione l'utilizzo della valutazione rigorosa dell'accumulatore: "Abbiamo bisogno di risolvere un piccolo problema per quanto riguarda l'overflow dello stack. La funzione si accumulerebbe (1 + acc) thunks mentre passiamo in rassegna la lista In generale, ha senso rendere i parametri dell'accumulatore severi, dal momento che il suo valore sarà necessario alla fine. " – Nimi

+1

GHC generalmente ritarda l'applicazione e la corrispondenza del modello, ma non l'applicazione di costruzione lenta. La ragione è che un * thunk * che rappresenta l'applicazione di '(:)' a 'x' e' y' è semanticamente identico a 'x: y' ma richiede più memoria. I costruttori sono speciali. I costruttori rigorosi non sono così speciali. – dfeuer

1

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