Haskell: listas, matrices, vectores, secuencias
Estoy aprendiendo Haskell y leo un par de artículos sobre las diferencias de rendimiento de las listas de Haskell y las matrices (inserte su idioma).
Como estudiante, 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.
¿Alguien puede explicar la diferencia entre listas, matrices, vectores y secuencias sin profundizar mucho en la teoría informática de las estructuras de datos?
Además, ¿existen algunos patrones comunes en los que se utilizaría una estructura de datos en lugar de otra?
¿Hay otras formas de estructuras de datos que me faltan y que podrían ser útiles?
Listas de rock
Con diferencia, la estructura de datos más amigable para datos secuenciales en Haskell es la Lista.
data [a] = a:[a] | []
Las listas le brindan ϴ (1) desventajas y coincidencia de patrones. La biblioteca estándar, y de hecho el preludio, está llena de funciones de lista útiles que deberían ensuciar su código ( foldr, map, filter). Las listas son persistentes , también conocidas como puramente funcionales, lo cual es muy bueno. Las listas de Haskell no son realmente "listas" porque son coinductivas (otros idiomas las llaman secuencias), por lo que cosas como
ones :: [Integer]
ones = 1:ones
twos = map (+1) ones
tenTwos = take 10 twos
Trabaja de maravilla. Infinitas estructuras de datos son geniales.
Las listas en Haskell proporcionan una interfaz muy parecida a los iteradores en lenguajes imperativos (debido a la pereza). Por tanto, tiene sentido que se utilicen ampliamente.
Por otro lado
El primer problema con las listas es que indexarlas (!!)lleva ϴ (k) tiempo, lo cual es molesto. Además, los anexos pueden ser lentos ++, pero el modelo de evaluación perezoso de Haskell significa que pueden tratarse como totalmente amortizados, si es que ocurren.
El segundo problema con las listas es que tienen una localidad de datos deficiente. Los procesadores reales incurren en constantes elevadas cuando los objetos en la memoria no están dispuestos uno al lado del otro. Entonces, en C++ std::vectortiene un "snoc" (poner objetos al final) más rápido que cualquier estructura de datos de lista enlazada pura que conozca, aunque esta no es una estructura de datos persistente, por lo que es menos amigable que las listas de Haskell.
El tercer problema con las listas es que tienen poca eficiencia espacial. Un montón de consejos adicionales aumentan su almacenamiento (en un factor constante).
Las secuencias son funcionales
Data.Sequencese basa internamente en árboles de dedos (lo sé, no querrás saber esto), lo que significa que tienen algunas propiedades interesantes
Puramente funcional.
Data.SequenceEs una estructura de datos totalmente persistente.Acceso muy rápido al principio y al final del árbol. ϴ (1) (amortizado) para obtener el primer o último elemento, o para añadir árboles. En lo que las listas de cosas son más rápidas,
Data.Sequencees como máximo una constante más lenta.ϴ (log n) acceso a la mitad de la secuencia. Esto incluye insertar valores para crear nuevas secuencias.
API de alta calidad
Por otro lado, Data.Sequenceno soluciona mucho el problema de la localidad de los datos y solo funciona para colecciones finitas (es menos vago que las listas)
Los arrays 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 perezoso mundo puramente funcional. Las matrices proporcionan acceso ϴ (1) al centro de la colección y factores constantes/localidad de datos excepcionalmente buenos. Pero, dado que no encajan muy bien en Haskell, es complicado usarlos. En realidad, hay una multitud de tipos de matrices 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 lo anterior. Para obtener más información, consulte la wiki de Haskell.
El vector es una matriz "mejor"
El Data.Vectorpaquete proporciona todas las bondades de la matriz, en una API más limpia y de nivel superior. A menos que realmente sepa lo que está haciendo, debe usarlos si necesita un rendimiento similar al de una matriz. Por supuesto, aún se aplican algunas advertencias: las estructuras de datos mutables similares a matrices simplemente no funcionan bien en lenguajes puramente perezosos. Aún así, a veces desea ese rendimiento O (1) y Data.Vectorse lo ofrece en un paquete utilizable.
Tienes otras opciones
Si solo desea listas con la capacidad de insertarse de manera eficiente al final, puede usar una lista de diferencias . El mejor ejemplo de listas que arruinan el rendimiento tiende a provenir de [Char]aquellas en las que el preludio tiene el alias String. CharLas listas son cómodas, pero tienden a ejecutarse del orden de 20 veces más lentas que las cadenas C, así que siéntete libre de usarlas Data.Texto las muy rápidas 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% de las veces necesito una colección secuencial en listas de Haskell que tengan 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 usando las toListfunciones que vienen con ellas. En un mundo mejor, el preludio sería completamente paramétrico en cuanto al tipo de contenedor que utiliza, pero actualmente []ensucia la biblioteca estándar. Entonces, usar listas (casi) en todas partes definitivamente está bien.
Puede obtener versiones completamente paramétricas de la mayoría de las funciones de lista (y es noble 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.Traversabledefine una API que es más o menos universal en cualquier "lista similar".
Aún así, aunque puedes ser bueno y escribir sólo código completamente paramétrico, la mayoría de nosotros no lo somos y usamos listas por todas partes. Si estás aprendiendo, te recomiendo que lo hagas también.
Según los comentarios, me doy cuenta de que nunca expliqué cuándo usar Data.Vectorvs. Data.SequenceLas matrices y los vectores proporcionan operaciones de indexación y división extremadamente rápidas, pero son estructuras de datos fundamentalmente transitorias (imperativas). A las estructuras de datos puramente funcionales les gusta Data.Sequencey []permiten producir eficientemente nuevos valores a partir de valores antiguos como si hubiera modificado los valores antiguos.
newList oldList = 7 : drop 5 oldList
No modifica la lista anterior y no es necesario copiarla. Así que aunque oldListsea increíblemente larga, esta "modificación" será muy rápida. Similarmente
newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
Producirá una nueva secuencia con un newValuefor en lugar de sus 3000 elementos. Nuevamente, no destruye la secuencia anterior, simplemente 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 modifica.
No puedes hacer esto fácilmente con Vectorsy Arrays. Se pueden modificar, pero esa es una modificación realmente imperativa y, por lo tanto, no se puede realizar en el código Haskell normal. Eso significa operaciones en el Vectorpaquete que realizan modificaciones como snocy constienen que copiar el vector completo, por lo que lleva O(n)tiempo. La única excepción a esto es que puedes usar la versión mutable ( Vector.Mutable) dentro de la STmónada (o IO) y hacer todas las modificaciones tal como lo harías en un lenguaje imperativo. Cuando haya terminado, "congelará" su vector para convertirlo en la estructura inmutable que desea usar con código puro.
Mi sensación es que deberías utilizarla de forma predeterminada Data.Sequencesi una lista no es apropiada. Úselo Data.Vectorsólo 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 charla sobre la STmónada te deja confundido: razón de más para seguir con lo puro, rápido y hermoso Data.Sequence.
