Haskell中函数调用的优化

Question

不知道这个问题到底要谷歌什么，所以我将它直接发布到 SO:

Haskell 中的变量是不可变的

纯函数应该为相同的参数产生相同的值

从这两点可以推断，如果您调用 somePureFunc somevar1 somevar2在您的代码中两次，只有在第一次调用期间计算值才有意义。结果值可以存储在某种巨大的哈希表(或类似的东西)中，并在随后调用该函数时进行查找。我有两个问题:

GHC真的会做这种优化吗？

如果是这样，在重复计算实际上比查找结果更便宜的情况下，行为是什么？

谢谢。

Answer 1

GHC 不做自动 memoization .请参阅 Common Subexpression Elimination 上的 GHC 常见问题解答(不完全一样，但我猜推理是一样的)和答案 this question .

如果你想自己做备忘录，那么看看 Data.MemoCombinators .

另一种看待记忆化的方法是利用惰性来利用记忆化。例如，您可以根据自身定义一个列表。下面的定义是所有斐波那契数的无限列表(取自 Haskell Wiki )

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

因为列表是延迟实现的，所以它类似于预先计算(内存)以前的值。例如 fibs !! 10将创建前十个元素，如 fibs 11快得多。