1

很抱歉这个问题描述太抽象了：它是为了我的工作，出于商业机密的原因，我不能给出现实世界的问题，只是一个抽象。

我有一个接收包含键值对的消息的应用程序。键来自一组定义的关键字，每个关键字都有一个固定的数据类型。因此，如果“Foo”是整数，“Bar”是日期，您可能会收到如下消息：

Foo: 234
Bar: 24 September 2011

消息中可能包含任何键子集。键的数量相当大（几十个）。但现在让我们坚持使用 Foo 和 Bar。

显然有这样的记录对应的消息：

data MyRecord {
   foo :: Maybe Integer
   bar :: Maybe UTCTime
   -- ... and so on for several dozen fields.
}

该记录使用“可能”类型，因为该字段可能尚未收到。

我还有许多需要从当前值（如果存在）计算的派生值。例如我想拥有

baz :: MyRecord -> Maybe String
baz r = do -- Maybe monad
   f <- foo r
   b <- bar r
   return $ show f ++ " " ++ show b

其中一些功能很慢，所以我不想不必要地重复它们。我可以为每条新消息重新计算 baz 并以原始结构记录它，但如果一条消息保持 foo 和 bar 字段不变，那么这就是浪费 CPU 时间。相反，我可以在每次需要时重新计算 baz ，但是如果自上次以来基础参数没有改变，那又会浪费 CPU 时间。

我想要的是某种智能记忆或基于推送的重新计算，仅在参数发生变化时重新计算 baz。我可以通过注意到 baz 仅依赖于 foo 和 bar 来手动检测到这一点，因此仅根据更改这些值的消息重新计算它，但对于容易出错的复杂函数。

另一个问题是，其中一些函数可能有多种策略。例如，您可能有一个可以使用“mplus”从 Foo 或 Bar 计算的值。

有谁知道现有的解决方案？如果没有，我应该怎么做？

4

3 回答 3

2

我假设您有一个“状态”记录，并且这些消息都涉及更新它以及设置它。所以如果Foo是12，以后可能是23，因此 的输出baz会改变。如果不是这种情况，那么答案将变得非常微不足道。

让我们从 baz 的“核心”开始——一个不在记录上的函数，而是你想要的值。

baz :: Int -> Int -> String

现在让我们转换它：

data Cached a b = Cached (Maybe (a,b)) (a -> b)
getCached :: Eq a => Cached a b -> a -> (b,Cached a b)
getCached c@(Cached (Just (arg,res)) f) x | x == arg = (res,c)
getCached (Cached _ f) x = let ans = f x in (ans,Cached (Just (x,ans) f)

bazC :: Cached (Int,Int) String
bazC = Cached Nothing (uncurry baz)

现在，每当您使用普通函数时，您都可以使用缓存转换函数，将生成的缓存转换函数替换回您的记录中。这本质上是一个大小为 1 的手动备忘录。

对于您描述的基本情况，这应该没问题。

一个涉及动态依赖关系图的更高级、更通用的解决方案被称为“增量计算”，但我看到的研究论文比严肃的生产实现还要多。您可以先看看这些，然后按照参考路径前进：

  1. http://www.carlssonia.org/ogi/Adaptive/
  2. http://www.andres-loeh.de/Incrementalization/paper_final.pdf

增量计算实际上也与函数式反应式编程非常相关，所以你可以看看 conal 的论文，或者玩一下 Heinrich Apfelmus 的反应式香蕉库：http ://www.haskell.org/haskellwiki/Reactive-banana

在命令式语言中，看看 python 中的格子：http: //pypi.python.org/pypi/Trellis或 lisp 中的单元格：http: //common-lisp.net/project/cells/

于 2012-05-18T23:35:40.973 回答
1

我想要的是某种智能记忆或基于推送的重新计算，仅在参数发生变化时重新计算 baz。

在我看来，您想要一个不可变的变量，但允许从“尚未计算”到“已计算”的一次性突变。好吧，你很幸运：这正是惰性评估给你的！因此，我提出的解决方案非常简单：只需为您要计算的每项内容添加字段即可。这是一个这样的例子，我们正在做的 CPU 密集型任务正在破坏一些加密方案：

data Foo = Foo
    { ciphertext :: String
    , plaintext :: String
    }

-- a smart constructor for Foo's
foo c = Foo { ciphertext = c, plaintext = crack c }

这里的重点是要求foo有这样的费用：

  1. 如果你从不要求plaintext结果，它很便宜。
  2. 在第一次调用 时plaintext，CPU 搅动了很长时间。
  3. 在随后调用 时plaintext，将立即返回先前计算的答案。
于 2012-05-19T00:02:45.470 回答
1

您可以构建一个与您需要执行的计算相对应的有状态图。当新值出现时，您将它们推送到图表中并重新计算，更新图表直到达到输出。（或者您可以将值存储在输入中并按需重新计算。）这是一个非常有状态的解决方案，但它确实有效。

您是否正在根据实时输入的利率等创建市场数据，例如收益率曲线？

于 2012-05-18T23:22:04.440 回答