Haskell 中的记忆

Question

上下文：

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

可以通过记忆加速：

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]

这种记忆化的实现技术在许多编程语言中被广泛使用，但它不能直接应用于 Haskell，因为 Haskell 是纯的，我们不想为了记忆一个函数而引入杂质。幸运的是，由于 Haskell 的惰性求值特性，可以在没有副作用的情况下记住一个函数。

以下memoize函数采用类型函数Int -> a 并返回同一函数的记忆版本。诀窍是将函数转换为值，因为在 Haskell 中，函数不会被记忆，但值会被记忆。

问题：

1. 函数式编程中的函数和值不是一样的吗？
2. 缓存如何不被视为副作用（在纯函数的上下文中）

Answer 1

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

这实际上是关于操作语义，它们有时棘手谈谈哈斯克尔因为Haskell是在它的术语所限定的指称语义-也就是说，什么值的表达式的计算结果为，而不是如何是评价发生。这不是副作用，因为记忆的“有状态”性质仍然隐藏在纯度抽象的背后：虽然有一些内部状态（在程序的部分图简化中表示），但您的程序无法观察以一种将其与非记忆版本区分开来的方式。这里的一个微妙之处在于，这些记忆策略实际上并不需要记忆——所保证的只是它们在一些未指定的有限时间后会给出的结果。

Haskell 实现不需要记忆任何东西——例如，它可以使用纯call-by-name，它不记忆值，而是重新计算所有内容。这是按名称调用的示例。

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 是纯的，所以计算结果不会有差异。然而，在现实世界中，这种策略最终过于昂贵而不实用。

至于选择不记忆功能，逻辑是一样的。对于编译器来说，使用诸如优化评估之类的东西来积极地记住每个函数是完全符合的。Haskell 的纯度意味着如果选择这种评估策略，结果不会有任何差异。但同样，在实际应用中，像这样记住每个函数最终会占用大量内存，并且最优评估器的开销太高，无法提供良好的实际性能。

Haskell 编译器也可以选择记住某些函数而不是其他函数，以最大限度地提高性能。这会很棒——我的理解是，并不知道如何可靠地做到这一点。编译器很难提前判断哪些计算成本低，哪些计算成本高，哪些计算可能会被重用，哪些不会。

因此选择了一种平衡，其中的值通常小于它们的 thunk 的评估形式，被记住；而函数，其记忆形式通常比它们的定义大（因为它们需要一个完整的备忘录表），而不是。然后我们根据我们自己作为程序员的判断，获得了一些类似于文章中的技术，可以在这些表示之间来回切换。