Haskell mutable map/tree

Question

Estoy buscando una tabla de árbol/mapa/hash mutable (balanceada) 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 intentado Data.HashTable (que está bien, pero algo lento) y he intentado con Data.Array.Judy pero no he podido hacer que funcione con GHC 6.10.4. ¿Hay más opciones?

Answer 1

Si desea que el estado mutable, puede tenerlo. Simplemente siga pasando el mapa actualizado o manténgalo en una mónada de estado (que resulta ser la misma cosa).

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 

Puede usar esto como tal. (En la práctica, es posible que desee agregar una forma de borrar elementos de la memoria caché, también.)

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 forma insegura escape de la exigencia de enhebrar 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 2

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

En cuanto a qué estructura de datos a utilizar,

• Hay un implementation of red-black trees en Kent

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

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

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

Si tiene suerte, puede pasar su estructura de datos de tablas como un parámetro extra a cada función que lo necesite. Sin embargo, si su tabla necesita ser ampliamente distribuida, puede usar un state monad donde el estado es el contenido de su tabla.

Si usted está tratando de memoize, puede probar algunos de los trucos memoization perezosos desde el blog de Conal Elliott, pero tan pronto como vas más allá de argumentos enteros, memoization perezoso se vuelve muy turbia — no es algo que le recomendaría probar como principiante. ¿Tal vez puede 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 variables mutables globales.

Answer 3

Basándome en la respuesta de @Ramsey, también sugiero que vuelva a configurar su función para tomar un mapa y devolver uno modificado. A continuación, codifique usando 0'03', que es bastante eficiente en las modificaciones. Este es 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 mapFuncWithMap genérico sobre las funciones que utilizan los mapas de esta manera.

Answer 4

Si leo sus comentarios derecha, entonces usted tiene una estructura con, posiblemente, ~ 500k valores totales de calcular. Los cálculos son costosos, por lo que desea que se realicen solo una vez, y en los accesos posteriores, solo desea el valor sin recalcular.

En este caso, utilice la pereza de Haskell a su ventaja! ~ 500k no es tan grande: solo construye un mapa de todas las respuestas, y luego busca según sea necesario. La primera extracción forzará el cálculo, las recuperaciones posteriores de la misma respuesta reutilizarán el mismo resultado, y si nunca se obtiene un cálculo en particular, ¡nunca sucede!

se puede encontrar una pequeña aplicación de esta idea utilizando las distancias de puntos en 3D como el cálculo en el archivo PointCloud.hs.Ese archivo utiliza Debug.Trace para iniciar la sesión cuando el cálculo se hace realidad:

> 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 5

¿Hay alguna otra opción?

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