在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

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

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

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