Lists 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 te dan Θ(1) cons y coincidencia de patrones. La biblioteca estándar, y para el caso el preludio, está llena de útiles funciones de lista que deberían ensuciar su código (foldr,map,filter). Las listas son persistentes , también conocidas como puramente funcionales, lo cual es muy agradable. Las listas de Haskell no son realmente "listas" porque son coinductivas (otros idiomas las llaman corrientes) así que cosas como

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

Trabaja maravillosamente. Estructuras de datos infinitas rock.

Las listas en Haskell proporcionan una interfaz muy similar 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 tiempo Θ(k), lo cual es molesto. Además, los apéndices pueden ser lentos ++, pero el modelo de evaluación perezosa de Haskell significa que estos pueden ser tratados como totalmente amortizados, si es que ocurren.

El segundo problema con las listas es que tienen una localidad de datos pobre. Los procesadores reales incurren en constantes altas cuando los objetos en memoria no están dispuestos uno al lado del otro. Por lo tanto, en C++ std::vector tiene un "snoc" (poner objetos al final) más rápido que cualquier estructura de datos de listas enlazadas pura 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 pobre eficiencia del espacio. Racimos de punteros adicionales empujan hacia arriba 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. Maldito acceso rápido al principio y al final del árbol. Θ(1) (amortizado) para obtener el primer o último elemento, o a añadir árboles. At the thing lists are fastest at, Data.Sequence es a lo sumo 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 para el problema de la localidad de datos, y solo funciona para colecciones finitas (es menos perezoso que las listas)

Los arreglos no son para los débiles de corazón{[45]]}

Los arrays son uno de los datos más importantes estructuras en CS, pero no encajan muy bien con el mundo funcional puro perezoso. Los arrays proporcionan Θ (1) acceso a la mitad de la colección y factores de localidad/constantes de datos excepcionalmente buenos. Pero, ya que no encajan muy bien en Haskell, son un dolor de usar. En realidad, hay una multitud de tipos de matrices diferentes en la biblioteca estándar actual. Estos incluyen arrays completamente persistentes, arrays mutables para la mónada IO, arrays mutables para la mónada ST, y versiones sin caja de la arriba. Para más información echa un vistazo a el wiki de haskell

El vector es una matriz" mejor "

El paquete Data.Vector proporciona toda la bondad de la matriz, en una API de nivel superior y más limpia. A menos que realmente sepa lo que está haciendo, debe usar estos si necesita una matriz como rendimiento. Por supuesto, algunas advertencias todavía se aplican array matriz mutable como estructuras de datos simplemente no juegan bien en lenguajes perezosos puros. Sin embargo, a veces quieres que O (1) rendimiento, y Data.Vector te lo da en un paquete utilizable.

Tiene 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 venir de [Char] que el preludio ha alias String. Char las listas son convient, pero tienden a ejecutarse en el orden de 20 veces más lentas que las cadenas C, así que siéntase libre de usar Data.Text o la muy rápida Data.ByteString. Estoy seguro de que hay otras secuencias orientadas bibliotecas en las que no estoy pensando ahora mismo.

Conclusión

El 90+% de las veces 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 usando las funciones toList con las que vienen. En un mundo mejor, el preludio sería completamente paramétrico en cuanto a qué tipo de contenedor utiliza, pero actualmente [] almacena la biblioteca estándar. Por lo tanto, el uso de listas (casi) en todas partes está definitivamente 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.Traversable define una API que es más o menos universal a través de cualquier cosa "list like".

Aún así, aunque puede ser bueno y escribir solo código paramétrico completo, la mayoría de nosotros no lo somos y usamos la lista en todo el lugar. Si estás aprendiendo, te sugiero que también lo hagas.

EDITAR: Basado en comentarios I date cuenta de que nunca expliqué cuándo usar Data.Vector vs Data.Sequence. Los arrays y vectores proporcionan operaciones de indexación y corte extremadamente rápidas, pero son fundamentalmente estructuras de datos transitorias (imperativas). Las estructuras de datos funcionales puras como Data.Sequence y [] 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 antigua, y no tiene que copiarla. Así que incluso si oldList es increíblemente largo, esta "modificación" será muy rápido. Del mismo modo

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

Producirá una nueva secuencia con un newValue para en el lugar de su elemento 3000. De nuevo, no destruye la vieja secuencia, solo crea una nueva. Pero, lo hace muy eficientemente, tomando O(log(min(k,k-n)) donde n es la longitud de la secuencia, y k es el índice que modifica.

No puedes hacer esto fácilmente con Vectors y Arrays. Pueden ser modificados pero esa es una modificación imperativa real, y por lo tanto no se puede hacer en forma regular Código Haskell. Eso significa que las operaciones en el paquete Vector que hacen modificaciones como snoc y cons tienen que copiar todo el vector, por lo que toman O(n) tiempo. 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 tal como lo haría en un lenguaje imperativo. Cuando haya terminado, "congela" su vector para convertirlo en la estructura inmutable que desea usar con código puro.

Mi sensación es que debe usar Data.Sequence por defecto si una lista no es apropiada. Utilice Data.Vector solo si su patrón de uso no implica hacer muchas modificaciones, o si necesita un rendimiento extremadamente alto dentro de las mónadas ST/IO.

Si toda esta charla de la ST mónada te está dejando confundido: razón de más para apegarse a puro rápido y hermoso Data.Sequence.