data structures - Haskell mapa/árbol mutable

data-structures hashtable

Question

Estoy buscando una tabla de árbol / mapa / hash mutable (equilibrada) en Haskell o una forma de simularla dentro de una función. Es decir, cuando llamo a la misma función varias veces, la estructura se conserva. Hasta ahora he probado Data.HashTable (que está bien, pero es un poco lento) y probé Data.Array.Judy pero no pude hacer que funcionara con GHC 6.10.4. ¿Hay más opciones?

Answer 1

¿Hay más opciones?

Una referencia mutable a un diccionario puramente funcional como Data.Map .

Answer 2

Aunque pida un tipo mutable, permítame sugerirle que use una estructura de datos inmutables y que pase versiones sucesivas a sus funciones como un argumento.

Con respecto a qué estructura de datos utilizar,

• Hay una implementación de árboles rojo-negro en Kent

• Si tiene claves enteras, Data.IntMap es extremadamente eficiente.

• Si tiene claves de cadena, el paquete bytestring-trie de Hackage se ve muy bien.

El problema es que no puedo usar (o no sé cómo) usar un tipo no mutable.

Si tiene suerte, puede pasar la estructura de datos de su tabla como un parámetro adicional a cada función que lo necesite. Sin embargo, si su tabla necesita ser ampliamente distribuida, es posible que desee utilizar una mónada estatal donde el estado es el contenido de su tabla.

Si está tratando de memorizar, puede probar algunos de los trucos perezosos de la memoria del blog de Conal Elliott, pero tan pronto como vaya más allá de los argumentos enteros, la memoria perezosa se vuelve muy turbia, algo que no le recomiendo que pruebe como principiante. ¿Quizás pueda publicar una pregunta sobre el problema más amplio que está tratando de resolver? A menudo, con Haskell y la mutabilidad, el problema es cómo contener la mutación o las actualizaciones dentro de algún tipo de alcance.

No es tan fácil aprender a programar sin ninguna variable global mutable.

Answer 3

Si leo bien tus comentarios, entonces tienes una estructura con posiblemente ~ 500k valores totales para calcular. Los cálculos son costosos, por lo que los desea hacer solo una vez, y en los accesos posteriores, solo desea el valor sin recálputo.

¡En este caso, usa la pereza de Haskell para tu ventaja! ~ 500k no es tan grande: solo construya un mapa de todas las respuestas y luego recupérelo según sea necesario. La primera búsqueda forzará el cálculo, las recuperaciones subsiguientes de la misma respuesta reutilizarán el mismo resultado, y si nunca obtienes un cálculo en particular, ¡nunca sucederá!

Puede encontrar una pequeña implementación de esta idea utilizando distancias de puntos 3D como el cálculo en el archivo PointCloud.hs . Ese archivo utiliza Debug.Trace para iniciar sesión cuando el cálculo realmente se realiza:

> ghc --make PointCloud.hs 
[1 of 1] Compiling Main             ( PointCloud.hs, PointCloud.o )
Linking PointCloud ...

> ./PointCloud 
(1,2)
(<calc (1,2)>)
Just 1.0
(1,2)
Just 1.0
(1,5)
(<calc (1,5)>)
Just 1.0
(1,2)
Just 1.0

Answer 4

Si quieres un estado mutable, puedes tenerlo. Simplemente siga pasando el mapa actualizado o manténgalo en una mónada estatal (lo que resulta ser lo mismo).

import qualified Data.Map as Map
import Control.Monad.ST
import Data.STRef
memoize :: Ord k => (k -> ST s a) -> ST s (k -> ST s a)
memoize f = do
    mc <- newSTRef Map.empty
    return $ /k -> do
        c <- readSTRef mc
        case Map.lookup k c of
            Just a -> return a
            Nothing -> do a <- f k
                          writeSTRef mc (Map.insert k a c) >> return a

Puedes usar esto así. (En la práctica, es posible que también desee agregar una forma de borrar elementos del caché).

import Control.Monad
main :: IO ()
main = do
    fib <- stToIO $ fixST $ /fib -> memoize $ /n ->
        if n < 2 then return n else liftM2 (+) (fib (n-1)) (fib (n-2))
    mapM_ (print <=< stToIO . fib) [1..10000]

A su propio riesgo , puede escapar de forma insegura del requisito de enhebrar el estado a través de todo lo que lo necesita.

import System.IO.Unsafe
unsafeMemoize :: Ord k => (k -> a) -> k -> a
unsafeMemoize f = unsafePerformIO $ do
    f'' <- stToIO $ memoize $ return . f
    return $ unsafePerformIO . stToIO . f''

fib :: Integer -> Integer
fib = unsafeMemoize $ /n -> if n < 2 then n else fib (n-1) + fib (n-2)

main :: IO ()
main = mapM_ (print . fib) [1..1000]

Answer 5

Sobre la base de la respuesta de @ Ramsey, también sugiero que reconcebamos su función para tomar un mapa y devolver uno modificado. Luego codifique usando un buen Data.Map , que es bastante eficiente en las modificaciones. Aquí hay un patrón:

import qualified Data.Map as Map

-- | takes input and a map, and returns a result and a modified map
myFunc :: a -> Map.Map k v -> (r, Map.Map k v)
myFunc a m = … -- put your function here

-- | run myFunc over a list of inputs, gathering the outputs
mapFuncWithMap :: [a] -> Map.Map k v -> ([r], Map.Map k v)
mapFuncWithMap as m0 = foldr step ([], m0) as
    where step a (rs, m) = let (r, m'') = myFunc a m in (r:rs, m'')
    -- this starts with an initial map, uses successive versions of the map
    -- on each iteration, and returns a tuple of the results, and the final map

-- | run myFunc over a list of inputs, gathering the outputs
mapFunc :: [a] -> [r]
mapFunc as = fst $ mapFuncWithMap as Map.empty
    -- same as above, but starts with an empty map, and ignores the final map

Es fácil abstraer este patrón y hacer que mapFuncWithMap sea genérico sobre las funciones que usan mapas de esta manera.