1

上下文：

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]

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

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

问题：

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

1 回答 1

8

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

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

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

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

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

于 2020-07-04T20:52:38.603 回答