在惰性评估的上下文中，什么时候需要尾递归？

Question

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

如果是这样的话，这是否意味着在惰性评估的上下文中不需要尾递归？

更新

具体来说，让我们看看下面的示例：

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

这个函数可以很容易地转换成尾递归函数.然而，如果是这样的话，我们将失去懒惰的优势-评估。

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

Answer 1

TL；博士将函数定义为“尾递归”，在惰性语言中通常并不有用。即使在这种情况下，您也可以获得堆栈溢出(与具有适当的尾调用优化的严格语言相反)。

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

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

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

严格评价length [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 [] 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

这使用堆栈上的常量空间，直到“魔术”部分，但在堆(通常)上构建延迟计算(添加)。标记为“魔术”的部分是所有的总和发生的地方，在一个简单的实现中，它使用堆栈。(请注意，在这种情况和类似的情况下，优化评估器实际上可能在计算期间执行添加操作，然后只返回3，您不能真正区分不同之处，但是没有使用堆栈。它可以使用其他技巧来防止堆栈溢出，比如CPS)。

摘要：

懒求值函数最终在其简单的实现中使用堆栈，而不管它们是否以尾递归的形式编写。

但是，您需要向编译器应用各种技巧，以便对堆栈使用进行优化。但是，在严格的语言中，它们并不像尾叫优化那样简单。

更好的选择是具体地使用这些语言，并使用各种高阶函数，这些函数大大减少了对递归函数定义的需求(而且在某种程度上也是因为这个原因而使用惰性语言)。