Haskell的回忆录

Question

上下文

F fib(n)：如果n< 2:返回1返回fib(n-1) + fib(n-2) 可以通过回忆录来加速： fib_memo = {} def (N)：如果n< 2:返回1如果不是fib_memo.has_key(n)：fib_memon = fib(n-1) + fib(n-2)返回fib_memon 这种回忆录实现技术在许多编程语言中得到了广泛的应用，但由于Haskell是纯的，我们不想仅仅为了回忆录函数而引入杂质，所以不能直接应用于Haskell。幸运的是，由于Haskell的懒惰评估特性，能够回忆一个没有副作用的函数。 下面的memoize函数接受Int -> a类型的函数，并返回相同函数的回忆录版本。诀窍是将一个函数转化为一个值，因为在Haskell中，函数不是回忆录，而是值。

问题：

1. 函数和值在函数式编程中不是相同的吗？
2. 缓存如何不被视为副作用(在纯函数的上下文中)

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，以便最多计算一次(这称为按需要调用)。但是，对其进行两次评估的按名调用Haskell实现在技术上是一致的。因为Haskell是纯的，所以计算的结果不会有任何差别。然而，在现实世界中，这一策略最终代价太高，无法付诸实施。

至于选择不回忆录功能，逻辑是一样的。对于编译器来说，使用像最优评价这样的工具，积极地回溯每个函数是完全一致的。Haskell的纯度意味着，如果选择这种评估策略，结果将没有差别。但是，在现实世界的应用程序中，回忆录这样的每个函数最终会占用大量的内存，而最优评估器的开销太高，无法提供良好的实际性能。

Haskell编译器也可以选择回忆录一些函数，而不是其他函数，以便最大限度地提高性能。这将是很好的--我的理解是，我们并不真正知道如何可靠地做到这一点。对于编译器来说，很难预先判断哪些计算比较便宜，哪些计算比较昂贵，哪些计算可能被重用，哪些计算不需要重用。

因此，我们选择了一种平衡，在这种平衡中，值的计算形式通常小于它们的块，而函数的回忆录形式通常大于它们的定义(因为它们需要一个完整的备忘表)。然后，根据我们作为程序员的判断，我们得到了一些技术，如本文中的技术，在这些表示之间来回切换。