当前流行的函数式语言中有没有对memoization有很好的支持&如果让我根据其memoization的强度来选择一种,您会推荐哪一种&为什么?
更新:我正在寻找优化有向图(其中节点可以是函数或数据)。当图中的一个节点被更新时,我希望仅当其他节点的值依赖于更改的节点时才重新计算它们。
Update2:需要免费或开源语言/运行时。
发布于 2010-03-07 01:24:59
对于Haskell,Conal Elliott在functional memo tries上发布了一篇漂亮的博客文章。这项工作非常聪明,而且相当深入,科纳尔后来将其扩展到polymorphic functions。无论您使用哪种语言,都强烈推荐使用这篇文章,因为它揭示了函数式语言中基本记忆化的深层思想。
然而,看看你的更新,并不清楚memoization是否真的是你想要的。您的扩展问题语句(通过有向图传播更新)几乎是增量计算的教科书示例,Bob Harper和Umut Acar在这方面做了大量工作。我相信他们有一个用标准ML编写的免费库。看看Umut在上的页面。
发布于 2010-03-06 18:32:57
发布于 2010-03-09 09:25:12
是的,你根本不想要记忆,你想要精确的依赖跟踪。您可以使用Haskell Functional graph Library (fgl)来创建ur有向图,然后使用后续函数精确地知道要更新哪些节点:http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fgl
这篇文章将极大地帮助ind理解文档:http://web.engr.oregonstate.edu/~erwig/fgl/
在模块Data.Graph.Inductive.Graph中,后续函数名为suc
在不同的方向上,支持这一点的一种流行的函数式语言是Excel。:)
https://stackoverflow.com/questions/2392109
复制相似问题