Haskell 中函数调用的优化
不知道到底要谷歌什么这个问题，所以我将其直接发布到 SO：
- Haskell 中的变量是不可变的
- 纯函数应该为相同的参数产生相同的值
从这两点可以推断出，如果你调用 somePureFunc somevar1 somevar2 在代码中两次，只有在第一次调用期间计算值才有意义。结果值可以存储在某种巨大的哈希表（或类似的东西）中，并在后续调用该函数时进行查找。我有两个问题：
- GHC真的做了这种优化吗？
- 如果确实如此，当重复计算实际上比查找结果更便宜时，情况会怎样？
谢谢。
Not sure what exactly to google for this question, so I'll post it directly to SO:
- Variables in Haskell are immutable
- Pure functions should result in same values for same arguments
From these two points it's possible to deduce that if you call somePureFunc somevar1 somevar2 in your code twice, it only makes sense to compute the value during the first call. The resulting value can be stored in some sort of a giant hash table (or something like that) and looked up during subsequent calls to the function. I have two questions:
- Does GHC actually do this kind of optimization?
- If it does, what is the behaviour in the case when it's actually cheaper to repeat the computation than to look up the results?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
GHC 不会自动记忆。请参阅关于公共子表达式消除的 GHC 常见问题解答（不完全相同，但我的猜测是推理是相同的）以及 这个问题的答案。
如果您想自己进行记忆，请查看 Data.MemoCombinators。
看待记忆化的另一种方式是利用惰性来利用记忆化。例如，您可以根据自身定义一个列表。下面的定义是所有斐波那契数的无限列表（取自 Haskell Wiki）
因为该列表是惰性实现的，它类似于预先计算（记忆）先前的值。例如
撒谎！！ 10将创建前十个元素，这样fibs 11速度要快得多。GHC doesn't do automatic memoization. See the GHC FAQ on Common Subexpression Elimination (not exactly the same thing, but my guess is that the reasoning is the same) and the answer to this question.
If you want to do memoization yourself, then have a look at Data.MemoCombinators.
Another way of looking at memoization is to use laziness to take advantage of memoization. For example, you can define a list in terms of itself. The definition below is an infinite list of all the Fibonacci numbers (taken from the Haskell Wiki)
Because the list is realized lazily it's similar to having precomputed (memoized) previous values. e.g.
fibs !! 10will create the first ten elements such thatfibs 11is much faster.保存每个函数调用结果（参见哈希consing）是有效的，但可能会造成巨大的空间泄漏，并且通常也会减慢您的速度程序下降了很多。检查表中是否有某些内容的成本通常比实际计算的成本更高。
Saving every function call result (cf. hash consing) is valid but can be a giant space leak and in general also slows your program down a lot. It often costs more to check if you have something in the table than to actually compute it.