simbolos - Bibliotecas para estructuras de datos estrictas en Haskell

multiplicar haskell

Question

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

Descargos de responsabilidad:

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 estricta similar a un contenedor no garantiza que todo lo que contiene se evaluará completamente, pero la estructura en sí debería ser estricta, por ejemplo

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

   (Aquí, los elementos contenidos están en WHNF, y posiblemente no están completamente evaluados, pero la estructura de la lista es. Por ejemplo, las listas infinitas serán valores que no terminan).

3. Conozco el paquete ''estricto'' sobre hackage, pero tiene un conjunto muy limitado de estructuras de datos estrictas. No contiene listas estrictas ni conjuntos.

4. Escribir listas estrictas a mí mismo parece increíblemente fácil (me encantan las extensiones de ghc para derivar Functor, Traversable y Foldable, por cierto), pero todavía parece que sería mejor hacerlo en una biblioteca separada. Y las implementaciones eficientes de conjuntos no me parecen tan triviales.

Answer 1

El paquete de containers (enviado con ghc) pronto tendrá variantes estrictas de Set y Map (no estoy seguro de que se incluyan con ghc-7.4, pero hay razones para esperar). Así que una implementación eficiente de conjuntos y mapas estrictos está en camino. Las listas estrictas son, como usted dice fácil, todavía un paquete sobre hackage que las proporcione sería bueno, por lo que no todos tienen que hacerlo ellos mismos. Que más necesitas?

Answer 2

Para su segundo punto, el término que he visto más a menudo es estricto.

Para una lista estricta de la espina dorsal, probablemente podría usar Data.Seq.Sequence (de contenedores) o Data.Vector (de vector ). Ninguna de las dos es una lista, sin embargo, dependiendo de lo que esté haciendo, es probable que una (o ambas) sea mejor. La secuencia proporciona O (1) contras y snoc, con acceso muy rápido a cualquiera de los extremos de la estructura. El rendimiento del vector es similar a una matriz. Si desea una interfaz más parecida a una lista para la 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í sola). Ambos son estrictos.

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