Bibliotecas para estructuras de datos estrictas en Haskell

Question

¿Qué bibliotecas existen que implementan estructuras de datos estrictas? Específicamente, estoy buscando listas estrictas y conjuntos estrictos.

Aviso legal:

1. soy consciente de deepseq. Es muy útil, pero agrega la sobrecarga de atravesar toda la estructura de datos cada vez que usa deepseq (que puede ser más de una vez).

2. Soy consciente de que una estructura de datos tipo contenedor estricta no garantizar todo lo que contiene será evaluado completamente, pero la estructura sí debe ser estricta, por ejemplo:

   data StrictList a = !a :$ !(StrictList a) | Empty 
   

   (Aquí, el los elementos contenidos están en WHNF, y posiblemente no se evalúan por completo, pero la estructura de la lista es. Por ejemplo, las listas infinitas serán valores no terminadores.)

3. Conozco el paquete 'estricto' sobre pirateo, pero tiene un límite muy d conjunto de estructuras de datos estrictas. No contiene listas ni conjuntos estrictos .

4. escribir listas estrictas mismo parece sorprendentemente fácil (me encanta extensiones de GHC para derivar Functor, de Traversable y plegable, por cierto.), Pero todavía parece que sería mejor hacerlo en una biblioteca independiente. Y implementaciones eficientes de conjuntos no me parecen tan triviales.

Answer 1

El containers paquete (incluido con GHC) pronto tendrá estrictas establecidas y Mapa variantes (no estoy seguro de que van a ser incluidos con GHC-7.4, pero no hay razón para esperar). Por lo tanto, una implementación eficiente de conjuntos y mapas estrictos está en camino. Las listas estrictas son, como dices fáciles, aún un paquete en hackage que las proporciona sería bueno, por lo que no todo el mundo tiene que hacerlo por sí mismo. Que más necesitas?

Answer 2

Para su segundo punto, el término que he visto con mayor frecuencia es riguroso.

Para una lista rigurosa, probablemente podría usar Data.Seq.Sequence (de contenedores) o Data.Vector (de vector). Ninguno de los dos es una lista, sin embargo, dependiendo de lo que esté haciendo, uno (o ambos) es probable que sea mejor. La secuencia proporciona O (1) contras y snoc, con acceso muy rápido a cualquier extremo de la estructura. El rendimiento de Vector es similar a una matriz. Si desea una interfaz más similar a la lista para Sequence, puede considerar el paquete ListLike (también hay una interfaz ListLike para vectores, pero es menos útil porque Vector proporciona una interfaz bastante completa por sí misma). Ambos son estrictos.

Para conjuntos estrictos, puede probar unordered-containers, que también proporciona un mapa estricto.