haskell - Haskell 中缓存了哪些函数？

Question

我有以下代码:

memoize f = (map f [0 ..] !!)

fib' 0 = 1
fib' 1 = 1
fib' n = fib' (n - 1) + fib' (n - 2)

fibMemo n = memoize fib' n
fibMemo'  = memoize fib'

(我知道斐波那契实现具有指数时间复杂度并且不使用缓存)

第一次执行 fibmemo' 30 需要 3 秒，第二次大约需要 0 秒，因为结果被缓存了。但第一个版本fibmemo并没有缓存结果，它总是需要3秒才能执行。唯一的区别是定义(据我所知是等效的)。

所以我的问题是，Haskell 中缓存了哪些函数？

我已经读过https://wiki.haskell.org/Memoization并没有解决我的问题。

Answer 1

本质上，您定义的函数的行为如下:

fibMemo n = let m = map fib' [0..] in m !! n
fibMemo'  = let m = map fib' [0..] in (m !!)

为什么fibMmemo'效率更高？好吧，我们可以将其重写为

fibMemo'  = let m = map fib' [0..] in \n -> m !! n

这使得更清楚的是，单个列表m是在n作为输入之前创建的。这意味着对 fibMemo' 的所有调用都将使用相同的 m。第一个调用缓慢地计算 m 的一部分，后续调用将重用该缓存结果(当然，假设调用命中缓存，否则 m 的另一部分是评估并缓存)。

相反，fibMemo 相当于

fibMemo = \n -> let m = map fib' [0..] in m !! n

在创建列表m 之前接受输入n。因此，每次调用都会获得一个新的缓存，这是毫无意义的，因为缓存的全部目的是稍后重用它。

lambda \n -> 与 let m = .. 的顺序对于性能而言非常重要。由于 m = .. 不使用 n，从技术上讲，let m = .. 可以向外 float ，本质上是把 fibMemo 转换成 fibMemo'，而不影响语义。然而，正如您所发现的，这通常不会保留性能!

这确实是 GHC 可以执行的优化，但实际上却没有，因为它很容易使性能显着变差。