Listas en Haskell: tipo de datos o tipo de datos abstractos?

Question

Por lo que entiendo, el tipo de lista en Haskell se implementa internamente mediante una lista vinculada. Sin embargo, el usuario del idioma no puede ver los detalles de la implementación, ni tiene la capacidad de modificar los "enlaces" que componen la lista vinculada para permitirle apuntar a una dirección de memoria diferente. Esto, supongo, se hace internamente.

Entonces, ¿cómo se puede calificar el tipo de lista como en Haskell? ¿Es un "tipo de datos" o un "tipo de datos abstracto"? ¿Y qué hay del tipo de lista enlazada de la implementación?

Además, dado que el tipo de lista proporcionado por el Preludio no es un tipo de lista vinculada, ¿cómo se pueden implementar las funciones básicas de la lista enlazada?

Tomemos, por ejemplo, este fragmento de código diseñado para añadir un elemento a en el índice n de una lista:

add [] acc _ _ = reverse acc 
add (x:xs) acc 0 a = add xs (x:a:acc) (-1) a 
add (x:xs) acc n a = add xs (x:acc) (n-1) a 

El uso de una lista "real", el añadido de un elemento sería simplemente consistir en la modificación un puntero a una dirección de memoria. Esto no es posible en Haskell (¿o no?), De ahí la pregunta: ¿es mi implementación de agregar un elemento a una lista el mejor posible, o me falta algo (el uso de la función reverse es, creo, particularmente feo, pero ¿es posible prescindir?)

Por favor, no dude en corregirme si algo de lo que he dicho es incorrecto, y gracias por su tiempo.

Answer 1

Está confundiendo la mutabilidad con la estructura de datos. Es es una lista adecuada, simplemente no se puede modificar. Haskell es puramente funcional, lo que significa que los valores son constantes: no puede cambiar un elemento en una lista más de lo que podría convertir el número 2 en 3. En su lugar, realiza cálculos para crear nuevos valores con los cambios que desea.

Se podría definir que la función más simple de esta manera:

add ls idx el = take idx ls ++ el : drop idx ls 

La lista el : drop idx ls reutiliza la cola de la lista original, por lo que sólo tiene que generar una nueva lista hasta idx (que es lo que el take la función lo hace). Si desea hacerlo usando recursión explícita, podría definirlo así:

add ls 0 el = el : ls 
add (x:xs) idx el 
    | idx < 0 = error "Negative index for add" 
    | otherwise = x : add xs (idx - 1) el 
add [] _ el = [el] 

Este reutiliza la cola de la lista de la misma manera (que es el el : ls en el primer caso).

Dado que parece tener problemas para ver cómo esta es una lista vinculada, seamos claros sobre qué es una lista vinculada: Es una estructura de datos compuesta de celdas, donde cada celda tiene un valor y una referencia al siguiente elemento . En C, se podría definir como:

struct ListCell { 
void *value; /* This is the head */ 
struct ListCell *next; /* This is the tail */ 
} 

En Lisp, Se define como (head . tail), donde head es el valor y tail es la referencia al siguiente elemento.

En Haskell, se define como data [] a = [] | a : [a], donde a es el valor y [a] es la referencia al siguiente elemento.

Como se puede ver, estas estructuras de datos son todos equivalentes. La única diferencia es que en C y Lisp, que no son puramente funcionales, los valores de cabeza y cola son cosas que puedes cambiar. En Haskell, no puedes cambiarlos.

Answer 2

Haskell es un lenguaje de programación puramente funcional. Esto significa que no se puede hacer ningún cambio.

Las listas son tipos no abstractos, es solo una lista vinculada.

Usted puede pensar de ellos se define de esta manera:

data [a] = a : [a] | [] 

que es exactamente la forma en que se define una lista enlazada - Un elemento de cabeza y (un puntero a) el resto.

Tenga en cuenta que esto no es diferente internamente. Si desea tener tipos más eficientes, use Sequence o Array. (Pero dado que no se permite ningún cambio, no es necesario copiar las listas para distinguir entre copias, lo que puede ser una ganancia de rendimiento en comparación con los idiomas imperativos)

Answer 3

Su código podría funcionar, pero definitivamente no es óptima. Tomemos el caso en el que desea insertar un elemento en el índice 0. Un ejemplo:

add [200, 300, 400] [] 0 100 

Si usted sigue la derivación de esto, se termina con:

add [200, 300, 400] [] 0 100 
add [300, 400] (200:100:[]) (-1) 100 
add [400] (300:[200, 100]) (-2) 300 
add [] (400:[300, 200, 100]) (-3) 400 
reverse [400, 300, 200, 100] 
[100, 200, 300, 400] 

Pero sólo está añadiendo una ¡artículo al principio de la lista! Tal operación es simple! Es (:)

add [200, 300, 400] [] 0 100 
100:[200, 300, 400] 
[100, 200, 300, 400] 

Piensa en cuánto de la lista realmente necesita revertirse.

le preguntas acerca de si el tiempo de ejecución modifica los punteros en la lista enlazada. Debido a que las listas en Haskell son inmutables, nadie (ni siquiera el tiempo de ejecución) modifica los punteros en la lista enlazada. Esta es la razón por la cual, por ejemplo, es barato agregar un artículo al principio de una lista, pero es costoso agregar un elemento al final de una lista. Cuando agrega un elemento al principio de la lista, puede reutilizar toda la lista existente. Pero cuando agrega un elemento al final, tiene que crear una lista vinculada completamente nueva. La inmutabilidad de los datos es necesaria para que las operaciones al principio de una lista sean baratas.

Answer 4

Re: añadir un elemento al final de una lista, me gustaría sugerir el uso del operador (++) y splitAt función:

add xs a n = beg ++ (a : end) 
    where 
    (beg, end) = splitAt n xs 

El List es una lista enlazada, pero es de sólo lectura. No puede modificar un List en su lugar; en su lugar, cree una nueva estructura List que tenga los elementos que desee. No lo he leído, pero this book probablemente llegue a tu pregunta subyacente.

HTH

Answer 5

En Haskell, "tipo de datos" y "tipo abstracto" son términos de la técnica:

• Un "tipo de datos" (que no es abstracta) tiene constructores de datos visibles que se puede emparejar patrones en expresiones case o definiciones de funciones.

• Un "tipo abstracto" no tiene constructores de datos visibles, por lo que no puede coincidir con el patrón de valores del tipo.

dado un tipo a, [a] (lista de a) es un datos tipo porque se puede ajuste de patrones sobre los constructores contras visibles (escrito :) y nula (escrito []). Un ejemplo de tipo abstracto sería IO a, que no puede deconstruir por coincidencia de patrones.

Answer 6

El compilador puede elegir libremente cualquier representación interna que desee para una lista. Y en la práctica, realmente varía. Claramente, la lista "[1 ..]" no está implementada como una serie clásica de células cons.

De hecho, una lista diferida se almacena como un thunk que se evalúa como una celda de cons que contiene el siguiente valor y el siguiente thunk (un thunk es básicamente un puntero de función más los argumentos para la función, que se reemplaza por el valor real una vez que se llama a la función). Por otro lado, si el analizador de rigor en el compilador puede probar que la lista completa siempre será evaluada, entonces el compilador simplemente crea la lista completa como una serie de celdas cons.