何时需要尾递归,在惰性求值的背景下？

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

如果是这样,是否意味着在惰性求值的上下文中不需要尾递归？

UPDATE

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

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

该函数可以很容易地转换为尾递归函数.但是,如果是这样,我们将失去懒惰评估的优势.

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

TL; DR定义函数"tail-recursively"在惰性语言中通常不常用.即使在这些情况下,您也可以获得堆栈溢出(与具有正确尾部调用优化的严格语言相反).

通过使用函数参数的延迟评估(按名称调用),您将失去使用递归表达简单迭代(使用常量空间)的能力.

例如,让我们比较两个版本的长度函数.首先让我们看看非尾递归函数来比较懒惰和非懒惰:

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,+这里是"递归"函数.

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

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).

摘要:

懒惰求值函数最终在其直接实现中使用堆栈,无论它们是否被写为尾递归.

但是,您需要应用各种技巧来编译器以实现堆栈使用的优化.尽管如此,它们并不像严格语言中的尾调用优化那样简单.

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