19

我正在寻找 Haskell 中的可变（平衡）树/映射/哈希表或如何在函数中模拟它的方法。即当我多次调用同一个函数时，结构被保留。到目前为止，我已经尝试过 Data.HashTable （还可以，但有点慢）并尝试过 Data.Array.Judy 但我无法使其与 GHC 6.10.4 一起使用。还有其他选择吗？

4

5 回答 5

13

如果你想要可变状态，你可以拥有它。只需继续传递更新的地图，或将其保存在状态单子中（事实证明是同一件事）。

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]
于 2010-02-10T17:00:02.017 回答
8

基于@Ramsey 的回答，我还建议您重新构思您的函数以获取地图并返回修改后的地图。然后使用良好的 ol' 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 通用于以这种方式使用映射的函数。

于 2010-02-10T00:25:50.830 回答
5

尽管您要求使用可变类型，但我建议您使用不可变数据结构，并将连续版本作为参数传递给您的函数。

关于使用哪种数据结构，

问题是我不能使用（或者我不知道如何）使用非可变类型。

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

如果你正在尝试记忆，你可以尝试 Conal Elliott 博客中的一些惰性记忆技巧，但是一旦你超越了整数参数，惰性记忆就会变得非常模糊——我不建议你作为初学者尝试。也许您可以发布有关您要解决的更广泛问题的问题？通常对于 Haskell 和可变性，问题是如何在某种范围内包含突变或更新。

在没有任何全局可变变量的情况下学习编程并不容易。

于 2010-02-09T23:57:01.147 回答
0

如果我没看错你的评论，那么你就有一个可能有大约 500k 总值的结构要计算。计算成本很高，因此您只希望它们完成一次，并且在随后的访问中，您只需要不重新计算的值。

在这种情况下，利用 Haskell 的懒惰来发挥你的优势！~500k 并不是那么大：只需构建所有答案的地图，然后根据需要获取。第一次提取将强制计算，相同答案的后续提取将重用相同的结果，如果您从未提取特定计算 - 它永远不会发生！

您可以在文件PointCloud.hs中找到使用 3D 点距离作为计算的这个想法的一个小实现。该文件用于Debug.Trace记录计算实际完成的时间：

> 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
于 2010-02-10T05:54:14.187 回答
0

还有其他选择吗？

对纯函数字典的可变引用，例如Data.Map.

于 2012-06-06T12:30:17.150 回答