Haskell (:) y (++) diferencias

Question

Lamento una pregunta como esta. No estoy muy seguro de la diferencia del operador : y ++ en Haskell.

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

también

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

que para la función inversa que surgió esta pregunta para mí,

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

¿Por qué no el siguiente trabajo?

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

dando un error de tipo.

Answer 1

El operador : se conoce como el operador "contras" y se usa para anteponer un elemento de cabeza a una lista. Entonces, [] es una lista y x:[] está anteponiendo x a la lista vacía haciendo una lista [x]. Si luego cons y:[x] se termina con la lista [y, x] que es lo mismo que y:x:[].

El operador ++ es el operador de concatenación de listas que toma dos listas como operandos y los "combinan" en una sola lista. Entonces, si tiene la lista [x] y la lista [y], puede concatenarlas así: [x]++[y] para obtener [x, y].

Observe que : toma un elemento y una lista, mientras que ++ toma dos listas.

En cuanto a su código que no funciona.

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

La función inversa se evalúa en una lista. Como el operador : no toma una lista como su primer argumento, entonces reverse(xs):x no es válido. Pero reverse(xs)++[x] es válido.

Answer 2

: incluye un elemento en una lista.

++ anexa dos listas.

El primero tiene escriba

a -> [a] -> [a] 

mientras que el último tiene el tipo

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

Answer 3

concatenación con (++)

Tal vez estoy pensando profundamente en esto, pero, por lo que yo entiendo, si intenta concatenar listas utilizando (++) por ejemplo:

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

(++) tiene que recorrer la lista completa de la izquierda. Echando un vistazo a code of (++) lo hace mucho más claro.

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

Por lo tanto, sería deseable evitar el uso de (++), ya que con cada llamada reverse(xs)++[x] la lista es cada vez más grande (o más pequeño dependiendo en el punto de vista. De todas formas, el programa simplemente tiene que atravesar otra lista con cada llamada)

Ejemplo:

digamos que implemento inversa como se propone a través de la concatenación.

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

Invertir una lista [1, 2, 3, 4] se vería algo como esto:

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] 

recursión de cola usando el operador contras (:) !!!

Un método para hacer frente a las pilas de llamadas es agregando un accumulator. (que no siempre es posible sólo tiene que añadir un acumulador. Pero la mayoría de los funciones recursivas uno se ocupa de son primitive recursive y puede pues transformarse en tail recursive functions.)

Con la ayuda del acumulador es posible hacer este ejemplo funciona, utilizando el operador de cons (:). El acumulador - ys en mi ejemplo - acumula el resultado actual y se transfiere como parámetro. Debido al acumulador, ahora podemos utilizar el operador contra para acumular el resultado al agregar el encabezado de nuestra lista inicial cada vez.

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

Hay una cosa a tener en cuenta aquí.

El acumulador es un argumento adicional. No sé si Haskell proporciona parámetros por defecto, pero en este caso sería bueno, porque siempre llamarían a esta función con una lista vacía como el acumulador de este modo: reverse' [1, 2, 3, 4] []

hay un montón de literatura acerca de la recursividad de cola y estoy seguro de que hay muchas preguntas similares en StackExchange/StackOverflow. Por favor corrígeme si encuentra algún error.

Saludos cordiales,

EDIT 1:

Will Ness señalaron algunos enlaces para realmente buenas respuestas para aquellos de ustedes que están interesados:

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

EDITAR 2:

Ok. Gracias a dFeuer y sus correcciones, creo que entiendo Haskell un poco mejor.

1.El $! está más allá de mi comprensión. En todas mis pruebas, parecía empeorar las cosas.

2.As dFeuer señaló: El procesador que representa la aplicación de (:) a x y y es semánticamente idénticos a x:y pero toma más memoria. Así que esto es especial para el operador de cons (y constructores perezosos) y no hay necesidad de forzar las cosas de ninguna manera.

3. Si I en lugar sumUp números enteros de una lista utilizando una función muy similar, evaluación estricta a través de BangPatterns o la función seq evitará que la pila de crecer demasiado grande si se utiliza adecuadamente. e.g .:

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

Observe la explosión delante de y. Lo probé en ghci y lleva menos memoria.

Answer 4

cons tiende a ser un constructor de tipos de un operador. el ejemplo aquí es : puede haber uso en let..in.. expresion pero ++ no es

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

devolverá 1, pero

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

devolverá un error Variable not in scope x

Para hacerlo más fácil, pensar en cons como este

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

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

Además, si desea invertir una matriz usando contras. He aquí un ejemplo, el conocimiento se toma de 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