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

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

¿Alguien puede explicar la diferencia entre listas, matrices, vectores, secuencias sin profundizar en la teoría de la informática de las estructuras de datos?

Además, ¿hay algunos patrones comunes en los que usarí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 Rock

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

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

Las listas le dan ϴ (1) contras y coincidencia de patrones. La librería estándar, y para el caso de la antesala, está lleno de funciones de lista de útiles que deberían basura su código ( foldr, map, filter). Las listas son persistentes , es decir , puramente funcionales, lo cual es muy agradable. Las listas de Haskell no son realmente "listas" porque son coinductivas (otros idiomas llaman a estas corrientes) así que cosas como

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

Trabaja maravillosamente. Estructuras de datos infinitos rock.

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 (!!)lleva ϴ (k) tiempo, lo cual es molesto. Además, los anexos pueden ser lentos ++, pero el modelo de evaluación perezosa de Haskell significa que estos 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 altas cuando los objetos en la memoria no están dispuestos uno al lado del otro. Por lo tanto, en C ++ std::vectortiene un "snoc" (poner objetos al final) más rápido que cualquier estructura de datos de listas enlazadas puras que conozco, aunque esta no es una estructura de datos persistente tan menos amigable que las listas de Haskell.

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

Las secuencias son funcionales

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

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

Por otro lado, Data.Sequenceno hace mucho por el problema de la localidad de datos, y solo funciona para colecciones finitas (es menos vago 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 y vago. Las matrices proporcionan acceso ϴ (1) a la mitad de la colección y a una localidad de datos excepcionalmente buena / factores constantes. Pero, dado que no encajan muy bien en Haskell, son difíciles de usar. En realidad, hay una multitud de diferentes tipos de matriz 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 información, consulte el wiki de Haskell

El vector es una matriz "mejor"

El Data.Vectorpaquete proporciona todas las bondades de la matriz, 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 rendimiento similar a la matriz. Por supuesto, todavía se aplican algunas advertencias: la matriz mutable, como las estructuras de datos, simplemente no funciona bien en lenguajes vagos puros. Aún así, a veces quieres ese rendimiento O (1) y te lo Data.Vectorda en un paquete utilizable.

Tienes otras opciones

Si solo desea listas con la capacidad de insertar eficientemente al final, puede usar una lista de diferencias . El mejor ejemplo de listas que arruinan el rendimiento tiende a provenir del [Char]cual el preludio se ha apodado como String. CharLas listas son convenientes, pero tienden a ejecutarse en el orden de 20 veces más lento que las cadenas C, así que siéntase libre de usar Data.Texto muy rápido Data.ByteString. Estoy seguro de que hay otras bibliotecas orientadas a la secuencia 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 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 []cubre 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 la 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 cosa "lista como".

Aún así, aunque puede ser bueno y escribir solo código completamente paramétrico, la mayoría de nosotros no lo somos y usamos la lista por todas partes. Si está aprendiendo, le sugiero que también lo haga.

EDIT: En base a los comentarios que se da cuenta que nunca he explicado cuándo utilizar Data.Vectorvs Data.Sequence. Las matrices y los vectores proporcionan operaciones de indexación y corte extremadamente rápidas, pero son estructuras de datos fundamentalmente transitorias (imperativas). Las estructuras de datos funcionales puras tienen gusto 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 tiene que copiarla. Entonces, incluso si oldListes 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 newValuefor en lugar de su elemento 3000. Nuevamente, no destruye la secuencia anterior, 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 yk es el índice que modifica.

No puedes hacer esto fácilmente con Vectorsy Arrays. Se pueden modificar, pero esa es una modificación imperativa real, por lo que no se puede hacer en el código Haskell normal. Eso significa operaciones en el Vectorpaquete que hacen modificaciones snocy constienen que copiar todo el vector, así que tómese el O(n)tiempo. La única excepción a esto es que puede usar la versión mutable ( Vector.Mutable) dentro de la STmónada (o IO) y hacer todas sus modificaciones como lo haría 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ía usarlo de manera predeterminada Data.Sequencesi una lista no es apropiada. Úselo Data.Vectorsolo 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: una razón más para seguir siendo puro, rápido y hermoso Data.Sequence.