向递归定义的haskell函数添加内存
向递归定义的haskell函数添加内存
提问于 2019-07-20 21:45:50
我已经用Haskell解决了一个动态编程问题(实际上是一个Project Euler问题)，归根结底是Fibonacci序列的推广：
f(n) = f(n-1) + f(n-2)
g(n) = g(n-1) + g(n-3)
h(n) = h(n-1) + h(n-4)还有更多类似的函数，由于问题的规模，我不得不添加memoization，这是相当琐碎的，如下所示：
memF = (map f' [0 ..] !!)
where f' x | x <=1 = 1
f' 2 = 2
f' x = memF(x-1) + memF(x-2)
memG = (map f' [0 ..] !!)
where f' x | x <=2 = 1
f' 3 = 2
f' x = memG(x-1) + memG(x-3)这可以很好地工作，所以我可以像(memF 100) + (memG 100) + ...一样得到答案，并且我已经回答了这个问题，但是重复的代码很难看，我更愿意定义一个函数来生成记忆函数，比如：
mem d = (map f' [0 ..] !!)
where f' x | x < d = 1
f' x | x == d = 2
f' x = (mem d) (x-1) + (mem d)(x-d)然后回答这个失败，或者至少缓存不起作用，我猜因为每次调用都会重新创建数组，我想我可以使用StateMonad或memoization库，但我很有兴趣知道是否有一种方法可以在没有Monad的情况下做到这一点。有吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-07-20 21:56:54
您需要另一个绑定来避免对mem d的递归调用
mem d = g
where g = (map f' [0 ..] !!)
f' x | x < d = 1
f' x | x == d = 2
f' x = g (x-1) + g (x-d)在调用mem时也要小心，因为每次调用mem都会创建自己的缓存。例如。
mem 10 x + mem 10 y将不缓存任何内容，而
let g = mem 10 in g x + g y将使用相同的缓存。
另一种方法是使用(d,x)对上的memoization，对所有调用mem d x使用一个“全局”缓存。不过，这看起来更难实现。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/57128819
复制
![递归函数[通俗易懂]](https://ask.qcloudimg.com/http-save/yehe-8223537/3fcf1eb540f34848140ce229d6a1a1cc.gif)
相似问题
haskell如何管理递归函数调用的内存？
Haskell递归和内存使用
Haskell向构造函数添加约束
在模板Haskell中定义递归函数
Haskell:递归定义函数值的有效计算
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
社区富文本编辑器全新改版！诚邀体验～
全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验
腾讯云开发者
