Haskell: 为什么这个例子中的记忆化能够奏效？

Question

嗨，我在研究来自记忆化的这个例子:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

我只是在想为什么这个可以工作，因为如果你调用 memoized_fib（n-2），那么你正在“创建”一个新列表并对其进行操作，并且在从中返回后，包含部分结果的列表将会消失？ 因此，memorized_fib（n-1）根本不会从中获益吗？

- Bob Fang

---

记忆化破坏了你的思考方式，如果你将定义更改为memoized_fib n = map fib [0 ..] !! n。我不知道为什么，但也许其他人可以解释一下。 - hugomg

http://blog.ezyang.com/2011/04/the-haskell-heap/ 是一篇关于 Haskell 堆的好文章系列，它可能也能解释这个问题（不确定），但即使不能，它也是一篇值得阅读的好文章！ - bennofs

Answer 1

memoized_fib 是一个CAF，和字面常量一样，在避免创建新东西方面非常有效。没有变量 ⇒ 没有新东西绑定的东西 ⇒ 没有创建新东西（简化来说）。

memoized_fib是一个CAF，它可以像文本常量一样避免创建新的东西，因为没有变量需要绑定新东西，也就不会创建新东西（简化来说）。

- n. m.

---

那么这是否意味着只会有一个memized_fib实例？我如何判断一个函数是不是CAF？谢谢 :) - Bob Fang

是的，只有一个。您可以根据链接文章中的定义进行检查 ;) - n. m.

首先感谢您，我并不是有意冒犯，但问题在于当我点击链接后，发现我对超级组合器一无所知，然后我又发现我不知道什么是组合器，接着它被定义为“没有自由变量的函数”，自由变量？从未听说过。可能在学习 Haskell 之前，我错过了最重要的事情，即先学习 λ演算和范畴论！ - Bob Fang

没错，一点点的λ演算和范畴论也不会有害！ - n. m.

Lambda演算绝对是现代函数式编程语言的核心。而范畴论只有在你想要编写或理解利用范畴论结果的库的内部时才是必需的。 - Jon Purdy

Answer 2

我可以解释一下missingno的观察结果，这可能有助于您理解您所看到的行为。了解where子句的展开非常重要。

您提供的代码是：

memoized_fib = (map fib [0 ..] !!)
    where fib = ...

这将被转化为

memoized_fib = let fib = ...
               in \n -> map fib [0 ..] !! n

missingno提出了下面的内容，看起来像简单的eta扩展，但实际上并不是！

memoized_fib n = map fib [0 ..] !! n
    where fib = ...

重写为

memoized_fib = \n -> let fib = ...
                     in map fib [0 ..] !! n

在前一种情况下，您可以看到fib结构在调用memoized_fib之间共享，而在后一种情况下，fib每次都会重新构建。

- Tom Ellis

---

在你提到 fib 是共享的第一个情况中，为什么它是共享的？你是说 memoized_fib = let fib = ... 在再次调用时不会重新声明 fib 吗？它会重复使用之前的 fib？这是否意味着它等同于在 memoized_fib 函数外定义 fib？ - CMCDragonkai

是的，这相当于在 memoized_fib 外部定义 fib。 - Tom Ellis

Answer 3

您展示的代码取决于特定编译器的行为。这是像Tom Ellis建议的那样的解糖过程：

memoized_fib = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)
    in
       (map fib [0 ..] !!)

没有什么能保证列表map fib [0..]会被重复使用，也就是说它不是“共享”的。特别是当你省略类型签名时，就像我所做的那样，这将成为一个多态定义。

最好明确地给该列表命名：

memoized_fib n = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = g (n-2) + g (n-1)
          g = (fibs !!)
          fibs = map fib [0 ..]
    in
       g n

这是之前讨论过的。

- Will Ness