list - type - Haskell(:) y(++) diferencias

learn yourself a haskell

Question

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

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

además

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

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

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

¿Por qué no funciona lo siguiente?

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

dando un error de tipo.

Answer 1

: Conses un elemento en una lista.

++ añade dos listas.

El primero tiene tipo

a -> [a] -> [a]

mientras que este último tiene tipo

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

Answer 2

El operador : se conoce como el operador "contras" y se utiliza para anteponer un elemento de cabecera a una lista. Entonces [] es una lista y x:[] está precediendo a x de la lista vacía, haciendo que la lista sea [x] . Si luego cons y:[x] terminas 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 las "combina" en una sola lista. Entonces, si tiene la lista [x] y la lista [y] entonces puede concatenarlos 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 como una lista. Dado que el operador : no toma una lista como primer argumento, se reverse(xs):x no es válido. Pero el reverse(xs)++[x] es válido.

Answer 3

cons tiende a ser un constructor de tipo que un operador. el ejemplo aquí es : se puede usar en let..in.. expresion pero ++ no es

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

volverá 1 pero

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

devolverá una Variable not in scope x error que Variable not in scope x

Para hacerlo más fácil, piensa en cons como esta.

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 revertir una matriz utilizando contras. Aquí hay un ejemplo, el conocimiento es tomado 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

Answer 4

Concatenación con (++)

Tal vez estoy pensando en profundizar en esto pero, por lo que entiendo, si intentas concatenar listas usando (++) por ejemplo:

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

(++) tiene que atravesar la lista izquierda completa. Echar un vistazo al código de (++) lo hace aún 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 aumenta (o disminuye según el punto de vista). De todos modos, el programa simplemente tiene que recorrer otra lista con cada llamada)

Ejemplo:

Digamos que implemento inverso 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 así:

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 lidiar con las pilas de llamadas es agregar un accumulator . (No siempre es posible simplemente agregar un acumulador. Pero la mayoría de las funciones recursivas que se tratan son primitivas recursivas y, por lo tanto, pueden transformarse en funciones recursivas de cola ).

Con la ayuda del acumulador es posible hacer que este ejemplo funcione, utilizando el operador contras (:) . El acumulador, ys en mi ejemplo, acumula el resultado actual y se pasa como parámetro. Debido al acumulador, ahora podemos usar el operador de contras para acumular el resultado agregando 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 extra. No sé si Haskell proporciona parámetros predeterminados, pero en este caso sería bueno, porque siempre llamaría a esta función con una lista vacía como el acumulador, así: a la reverse'' [1, 2, 3, 4] []

Hay mucha literatura sobre la recursión de la cola y estoy seguro de que hay muchas preguntas similares en StackExchange / . Por favor corrígeme si encuentra algún error.

Saludos cordiales,

EDITAR 1 :

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

• ¿Por qué las listas de diferencias son más eficientes que la concatenación regular?
• Haskell foldl ''pobre rendimiento con (++)

EDIT 2 :

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

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

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

3. Si, en cambio, sumo los enteros de una lista usando una función muy similar, la evaluación estricta a través de BangPatterns o la función seq evitará que la pila crezca demasiado si se usa adecuadamente. p.ej:

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

Observe el golpe en frente de y. Lo probé en ghci y me lleva menos memoria.