Haskell: Datastruture con O (1) anexión y O (1) indización?

Question

Estoy buscando una estructura de datos en Haskell que sea compatible con indexación rápida y rápida. Esto es para un problema de memorización que surge de la recursión.

Desde el modo en que funcionan los vectores en C++ (que son mutables, pero eso no debería importar en este caso) parece que los vectores inmutables con (O) amortiguado (1) añaden y O (1) indexación debería ser posible (ok, no lo es, mira los comentarios a esta pregunta). ¿Es posible esto en Haskell o debería ir con Data.Sequence que tiene (AFAICT de todos modos) O (1) anexar y O (log (min (i, n-i))) indización?

En una nota relacionada, como novato de Haskell, anhelo una guía práctica y concisa de las estructuras de datos de Haskell. Idealmente, esto proporcionaría una visión general bastante completa de las estructuras de datos más prácticas junto con las características de rendimiento y los indicadores de las bibliotecas de Haskell donde se implementan. Parece que hay mucha información por ahí, pero me parece un poco dispersa. ¿Estoy pidiendo demasiado?

Answer 1

Si la memoria sirve, los vectores C++ se implementan como una matriz con información de límites y tamaños. Cuando una inserción aumenta los límites más allá del tamaño, el tamaño se duplica. Esto se amortiza O (1) inserción de tiempo (no O (1) como usted afirma), y se puede emular muy bien en Haskell usando el tipo Array, quizás con IO o ST antepuesto.

Answer 2

Eche un vistazo a this para hacer una elección más informada de lo que debe usar.

Pero lo simple es que, si quiere el equivalente de un vector C++, use Data.Vector.

Answer 3

Para problemas simples de memorización, normalmente desea compilar la tabla una vez y luego no modificarla más adelante. En ese caso, puede evitar tener que preocuparse por agregar, al pensar en la construcción de la tabla de memorización como una sola operación.

Un método es aprovechar la evaluación perezosa y consultar la tabla mientras la estamos construyendo.

import Data.Array 
fibs = listArray (0, n-1) $ 0 : 1 : [fibs!(i-1) + fibs!(i-2) | i <- [2..n-1]] 
    where n = 100 

Este método es especialmente útil cuando las dependencias entre los elementos de la tabla hace que sea difícil llegar a una simple orden de evaluación de las mismas antes de tiempo. Sin embargo, requiere el uso de matrices o vectores en caja, lo que puede hacer que este enfoque sea inadecuado para tablas grandes debido a la sobrecarga adicional.

Para los vectores sin caja, tiene operaciones como constructN que le permite construir una tabla de manera pura mientras utiliza la mutación debajo para hacerlo eficiente. Hace esto dando a la función que pasa una vista inmutable del prefijo del vector construido hasta el momento, que luego puede usar para calcular el siguiente elemento.

import Data.Vector.Unboxed as V 
fibs = constructN 100 f 
    where f xs | i < 2 = i 
      | otherwise = xs!(i-1) + xs!(i-2) 
      where i = V.length xs