13

当前流行的函数式语言中是否有任何一种对记忆化有很好的支持？如果我要根据记忆化的强度来选择一种，你会推荐它吗？为什么？

更新：我正在寻找优化有向图（其中节点可以是函数或数据）。当图中的节点更新时，我希望仅当其他节点的值依赖于更改的节点时才重新计算它们。

Update2：需要免费或开源语言/运行时。

4

3 回答 3

7

对于 Haskell，Conal Elliott 发布了一篇关于功能性备忘录尝试的漂亮博客文章。这项工作非常聪明而且相当深刻，Conal 后来将其扩展到多态函数。无论您使用哪种语言，都强烈推荐使用这些东西，因为它揭示了函数式语言中记忆化的深层思想。

但是，查看您的更新，尚不清楚 memoization 是否真的是您想要的。您的扩展问题陈述（通过有向图传播更新）几乎是增量计算的教科书示例，Bob Harper 和Umut Acar在这方面做了很多工作。我相信他们有一个用标准 ML 编写的免费库。查看 Umut 关于自调整计算的页面。

于 2010-03-06T17:24:58.967 回答
4

在 Haskell 上，请参阅此作为开始。

对于 Lisp 来说， 这是 Google 的第一个看起来相关的热门产品。

对于 F# ，这可能是一个很好的起点。

现在我已经为你完成了谷歌搜索。这有什么好的支持吗？你决定 ：-）

哦，我推荐 Mathematica，但我知道很多人都被它的价格标签吓到了。严格来说，它可能更像是一个术语重写系统，而不是一个函数式编程系统，而且它在任何意义上都不是纯粹的。但它确实做记忆。

编辑：我忘记了 Erlang，它目前有很大的吸引力——我不知道怎么做，但我希望它可以做记忆。

于 2010-03-06T10:32:56.653 回答
3

是的，你根本不需要记忆，你想要精确的依赖跟踪。您可以使用 Haskell 函数图库 (fgl) 创建您的有向图，然后使用后继函数来准确了解要更新哪些节点：http: //hackage.haskell.org/cgi-bin/hackage-scripts/package/ fgl

本文将极大地帮助理解文档： http ://web.engr.oregonstate.edu/~erwig/fgl/

后继函数名为 suc，在模块 Data.Graph.Inductive.Graph 中

朝着不同的方向发展，一种支持此功能的流行功能语言是 Excel。:)

于 2010-03-09T01:25:11.623 回答