haskell - 记住廉价的副作用

Question

我想用类型来内存一个函数，比如说，

f :: Int -> Integer

我可以轻松做到这一点，例如使用MemoCombinators包，例如:

f_ = Memo.integral f

但是，当给定一对 (x, f x) 时，还有很多其他点需要计算 f很容易给出f x :

freebies :: (Int, Integer) -> [(Int, Integer)]

但给定一点x' ，算起来也不便宜了一些x其中elem x' . map fst $ freebies (x, f x) 。所以我想存储这些额外的 (x', y')当它们变得可用时配对，以便稍后 f x'可以有效地计算。

我的问题是，内存这样一个函数的好方法是什么？

Answer 1

要使用纯粹内存来实现此目的，您需要找到一种方法将免费赠品的x映射回生成它的点。如果您想考虑纯记忆化的功能，请不要将其视为会更新的缓存表；相反，可以将其视为逐渐简化的数据依赖图。您需要一种方法让免费赠品指向计算它们的因素。

假设你有:

-- Representative k finds a k', where it is easy to calculate
-- k from (k')'s value (this calculation is the Value -> Value
-- function)
-- There should be multiple (k')'s per k; and representative k' 
-- on one of those should return (k', const v), where v is the
-- value.
representative :: Key -> (Key, Value -> Value)

然后你可以记住:

table = memoKey go
    where
    go k = let (k', vf) = representative k in
           vf (table k')

其中 memoKey 是 Key 的内存器。

请记住，Value 可能是一个更复杂的类型，它具有计算免费赠品所需的信息，然后您可以为最终用户丢弃额外的信息。

如果您无法将免费赠品 转化为代表 的形式，那么我认为您对于纯粹内存策略不太走运。这是因为，如果您按照建议的方式进行操作，免费赠品表中的值将取决于首先评估的内容，而这在纯 Haskell 中是禁忌。 (即使您知道值将相同，纯粹的内存策略甚至无法依赖于评估顺序)

您也可以使用具有显式状态保存表的方法，或基于 unsafePerformIO 的不纯备忘录表。