哈斯克尔的评估策略在通过可代表的记忆中的作用是什么

Question

文章Memoization via Representables在解释如何通过Representaables对递归函数进行内存化方面做得很好。它从实现Fibonacci序列作为fibOp:的不动点开始

fibOp :: Num a => (Natural -> a) -> (Natural -> a)
fibOp v 0 = 0
fibOp v 1 = 1
fibOp v n = v (n-1) + v (n-2)
fix f = let x = f x in x
fibNaive :: Num a => Natural -> a
fibNaive = fix fibOp  

这种实现效率不高，因为它多次计算相同的值。

文章接着介绍了互逆函数streamTabulate和streamIndex(稍后将在Representable型类中推广(。这些功能使我们能够实现fibNaive:的记忆版本

fibSmart :: Num a => Natural -> a
fibSmart = fix (streamIndex . streamTabulate . fibOp)

正是在这一点上；"洗手"：

如果我们用fibOp组成制表函数，我们会得到一个函数，它将函数v转换为Stream，我们可以对其进行索引以获取函数。然而，在这种情况下，所有参数都共享相同的流。

这到底意味着什么？显然，这种记忆技术之所以有效，是因为Haskell的懒惰评估策略；不必要地"；。例如，这个答案提到Haskell每次输入其周围的lambda表达式时，最多计算一次给定的表达式。然而，streamTabulate的周围lambda表达式在由周围fix引起的每次迭代中输入一次，这意味着streamTabulate可能被评估多次。

为什么以及如何使用这种方法？它利用了Haskell评估策略的哪个方面？

Answer 1

您的函数：

fibSmart :: Num a => Natural -> a
fibSmart = fix (streamIndex . streamTabulate . fibOp)

确实可以通过将(.)内联到：来扩展

fibSmart = fix (f -> streamIndex (streamTabulate (fibOp f)))

但是λCCD_ 10在这里仅通过CCD_。

您还可以通过进一步内联fix:

fibSmart = let f = streamIndex (streamTabulate (fibOp f)) in f