Haskell可变地图/树

Question

我在Haskell中寻找一个可变(平衡)树/ map/hash表,或者在函数内部如何模拟它.即,当我多次调用相同的函数时,结构将被保留.到目前为止,我已经尝试了Data.HashTable(可以,但有点慢)并尝试了Data.Array.Judy,但我无法使其与GHC 6.10.4一起使用.还有其他选择吗？

Answer 1

如果你想要可变状态,你可以拥有它.只是继续传递更新的地图,或将其保持在状态monad(事实证明是相同的).

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

你可以像这样使用它.(实际上,您可能还想添加一种方法来清除缓存中的项目.)

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]

您可以自担风险,不必安全地从需要它的所有线程状态中逃脱.

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

在@ Ramsey的答案的基础上,我还建议您重新使用您的函数来获取地图并返回修改后的地图.然后使用良好的' Data.Map代码,这在修改时非常有效.这是一种模式:

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

很容易抽象这个模式,并使mapFuncWithMap通用于以这种方式使用地图的函数.

Answer 3

虽然你要求一个可变类型,但我建议你使用一个不可变的数据结构,并将连续版本作为参数传递给你的函数.

关于使用哪种数据结构,

• 肯特有一个红黑树的实施

• 如果你有整数键,Data.IntMap效率极高.

• 如果你有字符串键,bytestring-trieHackage的包看起来非常好.

问题是我不能使用(或者我不知道如何)使用非可变类型.

如果幸运的话,您可以将表数据结构作为额外参数传递给需要它的每个函数.但是,如果您的表需要广泛分发,您可能希望使用状态monad,其中state是表的内容.

如果你想要记忆,你可以尝试Conal Elliott的博客中的一些懒惰的记忆技巧,但是一旦你超越整数论证,懒惰的记忆变得非常模糊 - 不是我建议你作为初学者尝试的东西.也许你可以发一个关于你想要解决的更广泛问题的问题？通常使用Haskell和可变性的问题是如何在某种范围内包含突变或更新.

没有任何全局可变变量,学习编程并不容易.