Haskell缓存函数的结果

Question

我有一个函数,它接受一个参数并产生一个结果.不幸的是,函数产生结果需要很长时间.使用相同的输入经常调用该函数,这就是为什么我可以方便地缓存结果.就像是

let cachedFunction = createCache slowFunction
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1)

我正在研究Data.Array,虽然数组是懒惰的,但我需要用一对对象(使用listArray)初始化它 - 这是不切实际的.如果'key'是例如'Double'类型,我根本无法初始化它,即使理论上我可以为每个可能的输入分配一个Integer,我有几万个可能的输入,我实际上只使用了少数几个.我需要使用函数而不是列表初始化数组(或者,最好是哈希表,因为只使用少量的resutls).

更新:我正在阅读备忘录文章,据我所知,MemoTrie可以按我想要的方式工作.也许.有人可以尝试生成'cachedFunction'吗？对于一个需要2个Double参数的慢函数？或者,或者,在〜[0..1亿]的域中采用一个不会占用所有内存的Int参数？

Answer 1

嗯,有Data.HashTable.然而,散列表不能很好地使用不可变数据和引用透明度,所以我认为它看不到很多用途.

对于少量值,将它们存储在搜索树(例如Data.Map)中可能足够快.如果你能忍受做一些改进Double,那么更强大的解决方案就是使用类似trie的结构,例如Data.IntMap; 这些查找时间主要与密钥长度成比例,并且集合大小大致不变.如果Int限制太多,你可以挖掘Hackage,找到在使用密钥类型方面更灵活的trie库.

至于如何缓存结果,我认为你想要的通常称为"memoization".如果您想按需计算和记忆结果,该技术的要点是定义一个包含所有可能结果的索引数据结构,这样当您要求特定结果时,它只强制获得答案所需的计算你要.常见示例通常涉及索引到列表,但相同的原则应适用于任何非严格的数据结构.根据经验,非函数值(包括无限递归数据结构)通常会被运行时缓存,而不是函数结果,因此诀窍是将所有计算都包含在顶级定义中,而不是取决于任何论点.

编辑: MemoTrie例子啊!

这是一个快速而肮脏的概念证明; 可能存在更好的方法.

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.MemoTrie
import Data.Binary
import Data.ByteString.Lazy hiding (map)

mangle :: Double -> [Int]
mangle = map fromIntegral . unpack . encode

unmangle :: [Int] -> Double
unmangle = decode . pack . map fromIntegral

instance HasTrie Double where
    data Double :->: a = DoubleTrie ([Int] :->: a)
    trie f = DoubleTrie $ trie $ f . unmangle
    untrie (DoubleTrie t) = untrie t . mangle

slow x 
    | x < 1 = 1
    | otherwise = slow (x / 2) + slow (x / 3)

memoSlow :: Double -> Integer
memoSlow = memo slow

请注意MemoTrie包使用的GHC扩展; 希望这不是问题.加载它在GHCI和尝试调用slow与memoSlow喜欢的东西(10 ^ 6)或(10 ^ 7)看到它的行动.

将此推广到采用多个参数或诸如此类的函数应该相当简单.有关使用MemoTrie的更多详细信息,您可能会发现其作者的博文有用.

Answer 2

查看备忘录