haskell可变地图/树

如果你想要可变的状态,你可以拥有它。只需不断地传递更新后的地图,或者将其保持在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]

基于@ramsey的答案,我还建议您重新接收您的函数,获取一个映射并返回一个修改后的映射。然后用good 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对以这种方式使用map的函数通用。

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

关于要使用的数据结构,

• 有一个 implementation of red-black trees 在Kent

• 如果您有整数键, Data.IntMap 非常有效。

• 如果您有字符串键, bytestring-trie package from Hackage 看起来很不错。

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

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

如果你试图记忆,你可以尝试一些来自Conal Elliott博客的懒惰记忆技巧,但是一旦你超越了整型论点,懒惰记忆就会变得非常模糊,这不是我推荐你作为一个初学者去尝试的。也许你可以发布一个关于你要解决的更广泛问题的问题?通常,由于haskell和易变性,问题是如何在某种范围内包含突变或更新。

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

还有其他选择吗?

对纯功能字典的可变引用,如 Data.Map .

如果我正确地阅读了您的评论,那么您就有了一个总值可能为~500k的结构。计算是昂贵的,所以您只需要执行一次,在后续访问中,您只需要不进行重新计算的值。

在这种情况下,利用哈斯克尔的懒惰为你的优势!~500k不是那么大:只需绘制一张所有答案的地图,然后根据需要提取。第一次获取将强制计算,随后对相同答案的获取将重用相同的结果,如果从未获取特定的计算,则不会发生这种情况!

您可以在文件中使用三维点距离作为计算,找到这个想法的一个小实现。 PointCloud.hs . 该文件使用 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