haskell - 为什么备忘录不起作用？

阅读memoization introduction之后，我通过使用更通用的备忘录功能(仅出于学习目的)重新实现了斐波那契示例:

memoizer :: (Int -> Integer) -> Int -> Integer
memoizer f = (map f [0 ..] !!)

memoized_fib :: Int -> Integer
memoized_fib = memoizer fib
    where fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)

这行得通，但是当我将最后一行更改为以下代码时，备忘录突然无法按我预期的方式工作(程序再次变慢):

          fib n = memoizer fib (n-2) + memoizer fib (n-1)

关键区别在哪里要记忆？

最佳答案

它是关于显式共享与隐式共享的。当您显式命名事物时，它自然可以共享，即作为单独的实体存在于内存中，并可以重复使用。 (当然，共享本身并不是语言的一部分，我们只能稍微微调编译器来共享某些东西)。

但是，当您两次或三次编写相同的表达式时，则依靠编译器用一个明确共享的实体替换常见的子表达式。那可能会也可能不会发生。

您的第一个变体等于

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 :: Int -> Integer
memoized_fib = (fibs !!)  where
        fibs = map fib [0 ..]
        fib 0 = 0
        fib 1 = 1
        fib n = memoized_fib (n-2) + memoized_fib (n-1)

通过显式引用在此处共享的实际实体，可以使最后一行在视觉上更加明显:我们在上面的步骤中刚刚命名的列表fibs:

        fib n = fibs !! (n-2) + fibs !! (n-1)

您的第二个变体与此等效:

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

这里，我们有三个看似独立的map表达式，它们可能会或可能不会被编译器共享。 使用ghc -O2编译它似乎重新引入了共享，并提高了速度。