haskell - 在惰性求值的情况下，什么时候需要尾递归？

Question

我的理解(可能不正确或不完整)是惰性求值可以提供尾递归的所有优点，并且做得更好。

如果是这样，是否意味着在惰性求值的情况下不需要尾递归？

更新

具体来说，让我们看以下示例:

(define (foo f a)
  (if (number? a)
    (* a a)
    (lazy-map foo a)))

这个函数可以很容易地转换为尾递归函数。但是，如果是这样，我们将失去惰性求值的优势。

实际上，当输入是一个相当大的列表(或无限)时，这个非尾递归函数是否需要消耗很多堆栈？我不这么认为。那么，是否有充分的理由使用尾递归而不是惰性求值？

Answer 1

TL;DR 在惰性语言中，“尾递归”定义函数通常没什么用。即使在这些情况下，您也可能会出现堆栈溢出(与具有适当尾部调用优化的严格语言相反)。

通过使用函数参数的惰性求值(按名称调用)，您将失去用递归表达简单迭代(使用常量空间)的能力。

例如，让我们比较长度函数的两个版本。首先我们看一下非尾递归函数来比较惰性和非惰性:

length [] = 0
length (head:tail) = length tail + 1

严格评估长度[1,2,3]:

length [1, 2, 3] ->
  length (1:[2, 3]) = length [2, 3] + 1 ->
    length (2:[3]) + 1 = (length [3] + 1) + 1 ->
      (length (3:[]) + 1) + 1 = ((length [] + 1) + 1) + 1 ->
        ((length [] + 1) + 1) + 1 = ((0 + 1) + 1) + 1 ->
      (1 + 1) + 1 ->
    2 + 1
  3

惰性评估:

length [1, 2, 3] ->
length (1:[2, 3]) = length [2, 3] + 1 ->

此时需要减少 + 并且需要评估两个参数，第一个是 length [2, 3]，因此它会像以前一样继续，但是在一个少一个参数的列表上。堆栈空间用于评估+(如果我们正在考虑简单的实现)。

因此，两个版本都使用堆栈，但对于懒惰的版本来说，+ 是这里的“递归”函数，而不是 length。

尾递归变体(使用累加器):

length [] a = a
length (head:tail) a = length tail (a + 1)

利用尾调用优化的严格评估步骤:

length [1, 2, 3] 0 ->
length (1:[2, 3]) 0 = length [2, 3] (0 + 1) ->
length (2:[3]) 1 = length [3] (1 + 1) ->
length (3:[]) 2 = length [] 2 + 1 ->
length [] 3 = 3

这在堆栈上使用常量空间，在堆上没有空间

惰性评估:

length [1, 2, 3] 0 ->
length (1:[2, 3]) 0 = length [2, 3] (0 + 1) ->
length (2:[3]) (0 + 1) = length [3] ((0 + 1) + 1) ->
length (3:[]) ((0 + 1) + 1) = length [] ((0 + 1) + 1) + 1 ->
length [] (0 + 1) + 1) + 1 = ((0 + 1) + 1) + 1 ->
magic -> 3

这在堆栈上使用恒定空间，直到“神奇”部分，但在堆上(通常)建立延迟计算(添加)。标记为“magic”的部分是所有的总和发生的地方，在简单的实现中它使用堆栈。 (请注意，在这种情况和类似情况下，优化评估器实际上可能在评估过程中进行加法，然后只返回 3，您无法真正分辨出差异，但不使用堆栈。它可以使用其他技巧来防止堆栈溢出如 CPS)。

摘要:

惰性计算函数在其直接实现中最终使用堆栈，无论它们是否被编写为尾递归。

但是，您需要对编译器应用各种技巧来优化堆栈使用。不过，它们并不像严格语言中的尾部调用优化那么简单。

更好的选择是惯用地使用这些语言，并利用各种高阶函数，从而显着减少对递归函数定义的需求(并且在某种程度上也出于这个原因而使用惰性语言)。