Haskell中的记忆化

Question

Context:

最初的回答

def fib(n):
    if n < 2: return 1
    return fib(n-1) + fib(n-2)

can be sped up by memoization:

fib_memo = {}
def fib(n):
    if n < 2: return 1
    if not fib_memo.has_key(n):
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

This implementation technique of memoization is used widely in many programming languages, but it can’t be applied directly to Haskell because Haskell is pure and we don’t want to introduce impurity just to memoize a function. Fortunately, it is possible to memoize a function without side effects thanks to Haskell’s nature of lazy evaluation.

The following memoize function takes a function of type Int -> a and returns a memoized version of the same function. The trick is to turn a function into a value because, in Haskell, functions are not memoized but values are.

问题：

1. 在函数式编程中，函数和值不是同一个东西吗？
2. 在纯函数的上下文中，为什么缓存不被视为副作用？

注：Original Answer翻译成"最初的回答"

- Meshugah

---

有时候你可以通过使用自引用的数据结构（corecursion）来免费获得记忆化功能：fibs = 1 : 1 : zipWith (+) fibs (tail fibs)。 - user5536315

说实话，我觉得那个页面有点令人困惑。它没有展示“基本”的记忆化形式，而是直接使用了fibMemo = fix (memoize . fib)这个比较微妙的表达方式，依赖于fix的定义。在我看来，理解记忆化的第一步是理解f = \x -> let y = expensive 42 in x+y和f = let y = expensive 42 in \x -> x+y在操作上的区别（在没有优化的情况下）。前者在每次调用时计算expensive 42，后者仅计算一次。 - undefined

"副作用"仅仅指的是一个函数做了什么，而不是它如何（快或慢）做到的。它的 "主要效果" 是计算和生成返回值；它的 "副作用" 是对外部世界（函数之外）状态所造成的任何改变。函数本身被视为一个黑盒子。 - undefined

Answer 1

所有函数都是值，但并非所有值都是函数。

这实际上涉及到操作语义，有时在Haskell中讨论起来可能会有些棘手，因为Haskell仅通过其指称语义进行定义——也就是说，一个表达式的值是什么，而不是它是如何被求值的。这不是副作用，因为记忆化的“有状态”性质仍然隐藏在纯度的抽象后面：虽然存在一些内部状态（以程序的部分图归约表示），但没有办法让程序以一种可以将其与非记忆化版本区分开来的方式“观察”该状态。这里的一个细微之处是，这些记忆化策略实际上并不需要记忆化——它们保证的只是在某个未指定的有限时间后它们将给出的结果。

Haskell实现没有要求记忆化任何内容——例如，它可以使用纯的名字调用，它不会记忆化值，而是重新计算所有内容。以下是名字调用的示例。

let f x = x * x in f (2 + 2)
= (2 + 2) * (2 + 2)
= 4 * (2 + 2)
= 4 * 4
= 16

这里2 + 2被计算了两次。大多数Haskell实现（优化除外）会创建一个thunk，以便最多计算一次（称为call-by-need）。但是，如果使用按名称调用的Haskell实现两次评估它将是技术上符合规范的。因为Haskell是纯的，所以计算结果不会有任何区别。不过，在现实世界中，这种策略最终变得过于昂贵而无法实用。

至于选择不对函数进行记忆化，逻辑是相同的。对于编译器来说，积极地记忆每个函数，使用类似optimal evaluation的东西是完全符合规范的。Haskell的纯洁性意味着，如果选择此评估策略，结果不会有任何区别。但是，再次强调，在实际应用中，像这样记忆化每个函数最终会占用大量内存，并且最优求值器的开销太高，以至于无法提供良好的实际性能。

一个Haskell编译器也可以选择对某些函数进行记忆化以最大化性能。这将是很棒的——我理解的是，目前并不真正知道如何可靠地做到这一点。编译器很难提前判断哪些计算是廉价的、哪些是昂贵的，以及哪些计算可能会被重用，哪些不会。因此，我们需要在平衡中做出选择，将那些计算的已求值形式通常小于其thunk的值进行记忆；而函数，则不进行记忆，因为它们的记忆形式通常比定义形式更大（因为它们需要整个memo表）。然后，我们可以像文章中所述的那样使用一些技巧来根据自己作为程序员的判断在这些表示之间来回切换。

- luqui