tuplas - multiplicar haskell

Haskell: Listas, Arreglos, Vectores, Secuencias

Question

Estoy aprendiendo Haskell y leo un par de artículos sobre las diferencias de rendimiento de las listas de Haskell y las matrices de (inserte su idioma).

Siendo un aprendiz, obviamente solo uso listas sin siquiera pensar en la diferencia de rendimiento. Recientemente comencé a investigar y encontré numerosas bibliotecas de estructuras de datos disponibles en Haskell.

¿Puede alguien explicar la diferencia entre Listas, Arrays, Vectores, Secuencias sin profundizar mucho en la teoría de las ciencias de la computación de las estructuras de datos?

Además, ¿hay algunos patrones comunes en los que utilizaría una estructura de datos en lugar de otra?

¿Hay otras formas de estructuras de datos que me falten y que puedan ser útiles?

Answer 1

Listas de rock

Con mucho, la estructura de datos más amigable para datos secuenciales en Haskell es la Lista

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

Las listas te dan cons (1) contras y coincidencia de patrones. La biblioteca estándar, y para el caso el preludio, está llena de funciones de lista útiles que deberían foldr su código ( foldr , map , filter ). Las listas son persistentes , también puramente funcionales, lo cual es muy bueno. Las listas de Haskell no son realmente "listas" porque son coinductivas (otros idiomas llaman a estas secuencias) así que cosas como

ones :: [Integer]
ones = 1:ones
twos = map (+1) ones
tenTwos = take 10 twos

trabajar maravillosamente Infinitas estructuras de datos de roca.

Las listas en Haskell proporcionan una interfaz muy parecida a los iteradores en lenguajes imperativos (debido a la pereza). Por lo tanto, tiene sentido que sean ampliamente utilizados.

Por otra parte

El primer problema con las listas es que indexarlas (!!) toma ϴ (k) tiempo, lo cual es molesto. Además, los apéndices pueden ser lentos ++ , pero el modelo de evaluación perezoso de Haskell significa que estos pueden tratarse como totalmente amortizados, si es que ocurren.

El segundo problema con las listas es que tienen una mala localidad de datos. Los procesadores reales incurren en constantes altas cuando los objetos en la memoria no están dispuestos uno al lado del otro. Por lo tanto, en C ++ std::vector tiene un "snoc" más rápido (poniendo objetos al final) que cualquier estructura de datos de listas enlazadas puras que conozco, aunque esta no es una estructura de datos persistente tan amigable como las listas de Haskell.

El tercer problema con las listas es que tienen poca eficiencia de espacio. Los conjuntos de punteros adicionales aumentan su almacenamiento (por un factor constante).

Las secuencias son funcionales

Data.Sequence se basa internamente en árboles de dedos (lo sé, no quieres saber esto), lo que significa que tienen algunas propiedades agradables

1. Puramente funcional. Data.Sequence es una estructura de datos totalmente persistente.
2. Darn acceso rápido al principio y al final del árbol. ϴ (1) (amortizado) para obtener el primer o el último elemento, o para agregar árboles. Cuando las listas de cosas son más rápidas, Data.Sequence es a lo más una constante más lenta.
3. ϴ (log n) acceso a la mitad de la secuencia. Esto incluye insertar valores para hacer nuevas secuencias.
4. API de alta calidad

Por otro lado, Data.Sequence no hace mucho por el problema de la localidad de datos, y solo funciona para colecciones finitas (es menos perezoso que las listas)

Las matrices no son para los débiles de corazón.

Las matrices son una de las estructuras de datos más importantes en CS, pero no encajan muy bien con el mundo funcional puro perezoso. Las matrices proporcionan ϴ (1) acceso a la mitad de la recopilación y factores de constante / constante de datos excepcionalmente buenos. Pero, como no encajan muy bien en Haskell, es un dolor utilizarlos. En realidad, hay una multitud de tipos de matriz diferentes en la biblioteca estándar actual. Estos incluyen matrices totalmente persistentes, matrices mutables para la mónada IO, matrices mutables para la mónada ST y versiones sin caja de las anteriores. Para más visita la wiki de haskell.

Vector es una matriz "mejor"

El paquete Data.Vector proporciona toda la bondad del arreglo, en un nivel más alto y una API más limpia. A menos que realmente sepa lo que está haciendo, debe usarlos si necesita un arreglo como el rendimiento. Por supuesto, todavía se aplican algunas advertencias: una matriz mutable como las estructuras de datos simplemente no juegan bien en lenguajes perezosos puros. Sin embargo, a veces desea que el rendimiento de O (1) y Data.Vector ofrezca en un paquete utilizable.

Tienes otras opciones

Si solo desea listas con la capacidad de insertar de manera eficiente al final, puede usar una lista de diferencias . El mejor ejemplo de listas que arruinan el rendimiento suele provenir de [Char] que el preludio ha asignado como String . Char listas de caracteres son convenientes, pero tienden a ejecutarse en el orden 20 veces más lento que las cadenas C, así que siéntase libre de usar Data.Text o el muy rápido Data.ByteString . Estoy seguro de que hay otras bibliotecas orientadas a secuencias en las que no estoy pensando en este momento.

Conclusión

Más del 90% del tiempo que necesito una colección secuencial en las listas de Haskell son la estructura de datos correcta. Las listas son como iteradores, las funciones que consumen listas se pueden usar fácilmente con cualquiera de estas otras estructuras de datos utilizando las funciones de lista de toList que vienen con. En un mundo mejor, el preludio sería totalmente paramétrico en cuanto al tipo de contenedor que utiliza, pero actualmente [] ocupa la biblioteca estándar. Por lo tanto, usar listas (casi) en todas partes está bien.
Puede obtener versiones totalmente paramétricas de la mayoría de las funciones de la lista (y son nobles para usarlas)

Prelude.map ---> Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc ---> Data.Foldable.foldr/foldl/etc
Prelude.sequence ---> Data.Traversable.sequence
etc

De hecho, Data.Traversable define una API que es más o menos universal en cualquier "lista como".

Aun así, aunque puede ser bueno y escribir solo código totalmente paramétrico, la mayoría de nosotros no lo somos y usamos la lista por todas partes. Si estás aprendiendo, te sugiero que lo hagas también.

EDIT: Basado en los comentarios, me doy cuenta de que nunca expliqué cuándo usar Data.Vector vs Data.Sequence . Las matrices y vectores proporcionan operaciones de indexación y corte extremadamente rápidas, pero son estructuras de datos fundamentalmente transitorias (imperativas). Las estructuras de datos Data.Sequence funcionales como Data.Sequence y [] permiten producir de manera eficiente nuevos valores a partir de valores antiguos como si hubiera modificado los valores anteriores.

 newList oldList = 7 : drop 5 oldList

no modifica la lista antigua, y no tiene que copiarla. Así que incluso si oldList es increíblemente largo, esta "modificación" será muy rápida. similar

 newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence

producirá una nueva secuencia con un nuevo newValue en lugar de sus 3000 elementos. Una vez más, no destruye la secuencia antigua, solo crea una nueva. Pero, lo hace de manera muy eficiente, tomando O (log (min (k, kn)) donde n es la longitud de la secuencia, y k es el índice que modificas).

No puedes hacer esto fácilmente con Vectors y Arrays . Se pueden modificar, pero eso es una modificación imperativa real, por lo que no se puede hacer en el código Haskell normal. Eso significa que las operaciones en el paquete de Vector que realizan modificaciones como snoc y cons tienen que copiar todo el vector, así que tómese el tiempo O(n) . La única excepción a esto es que puede usar la versión mutable ( Vector.Mutable ) dentro de la mónada ST (o IO ) y hacer todas sus modificaciones como lo haría en un lenguaje imperativo. Cuando haya terminado, "congela" su vector para que se convierta en la estructura inmutable que desea usar con código puro.

Mi sensación es que debería usar Data.Sequence forma predeterminada si una lista no es apropiada. Use Data.Vector solo si su patrón de uso no implica realizar muchas modificaciones, o si necesita un rendimiento extremadamente alto dentro de las mónadas ST / IO.

Si toda esta conversación sobre la mónada ST te deja confundido: mayor razón para apegarte a la Data.Sequence pura, rápida y hermosa.