Haskell mapa mutable / árbol

Question

Busco una mesa mutable (equilibrada) árbol / mapa / hachís en Haskell o una manera cómo simular que dentro de una función. Es decir. cuando llamo la misma función varias veces, se conserva la estructura. Hasta ahora he intentado Data.HashTable (lo cual está bien, pero un poco lento) y trató Data.Array.Judy pero fue incapaz de hacerlo funcionar con GHC 6.10.4. ¿Hay otras opciones?

Answer 1

Si desea que el estado mutable, lo puedes tener. Sólo seguir pasando el mapa actualizado su alrededor, o mantenerlo en un estado mónada (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 utilizar este 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 no segura escape de la exigencia de enhebrar estado a través de todo lo que 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

Sobre la base de la respuesta de Ramsey @, también sugieren que reconcebir su función para tomar un mapa y devolver uno modificado. A continuación, utilizando código de buen ol' Datos .map , que es bastante eficiente en modificaciones. Aquí 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 3

A pesar de pedir un tipo mutable, permítanme sugerir que se utiliza una estructura de datos inmutables y que se pasa versiones sucesivas de sus funciones como argumento.

En cuanto a que la estructura de datos para utilizar,

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

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

• Si tiene claves de cadena, el bytestring-trie paquete de apariencia Hackage muy bueno.

  

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 la tabla como un parámetro adicional para cada función que lo requiera. Si, sin embargo, su mesa tiene que ser ampliamente distribuido, es posible que desee utilizar un rel="nofollow mónada estado donde el estado es el contenido de la 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 un principiante . Tal vez usted puede enviar una pregunta sobre el problema más amplio que está tratando de resolver? A menudo con Haskell y la mutabilidad de la cuestión es cómo contener la mutación o cambios dentro de algún tipo de ámbito.

No es tan fácil el aprendizaje de programa sin ninguna de las variables globales mutables.

Answer 4

  

¿Hay otras opciones?

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

Answer 5

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

En este caso, utilice la pereza de Haskell a su ventaja! ~ 500k no es tan grande: Sólo construir un mapa de todas las respuestas, y luego ir a buscar como sea necesario. La primera se ha podido recuperar obligará computación, recuperaciones posteriores de la misma respuesta se vuelva a utilizar el mismo resultado, y si nunca buscar un cómputo particular, - que nunca sucede

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