是否可以使用延续使foldRight尾递归? [英] Is it possible to use continuations to make foldRight tail recursive?

问题描述

以下博客文章显示了如何在F#中<可以使用连续传递样式将c0>设置为尾递归.

The following blog article shows how in F# foldBack can be made tail recursive using continuation passing style.

在Scala中，这意味着:

In Scala this would mean that:

def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
  l match {
    case x :: xs => f(x, foldBack(xs, acc)(f))
    case Nil => acc
  }
} 

通过执行以下操作，可以使

成为尾递归:

can be made tail recursive by doing this:

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    l match {
      case x :: xs => loop(xs, (racc => k(f(x, racc))))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

不幸的是，对于长列表，我仍然会出现堆栈溢出.循环是尾部递归和优化的，但是我想堆栈堆积只是移到了延续调用中.

Unfortunately, I still get a stack overflow for long lists. loop is tail recursive and optimized but I guess the stack accumulation is just moved into the continuation calls.

为什么这不是F#的问题?还有什么方法可以解决Scala的问题?

Why is this not a problem with F#? And is there any way to work around this with Scala?

编辑:这是一些显示堆栈深度的代码:

Edit: here some code that shows depth of stack:

def showDepth(s: Any) {
  println(s.toString + ": " + (new Exception).getStackTrace.size)
}

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    showDepth("loop")
    l match {
      case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

foldCont(List.fill(10)(1), 0)(_ + _)

此打印:

loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10

推荐答案

问题是延续函数(racc => k(f(x, racc)))本身.应该为整个业务进行尾调优化，但并非如此.

The problem is the continuation function (racc => k(f(x, racc))) itself. It should be tailcall optimized for this whole business to work, but isn't.

Scala无法对任意的尾部调用进行尾部调用优化，只能对其进行转换(例如，当函数调用自身而不是其他某些函数时)的循环进行优化.

Scala cannot make tailcall optimizations for arbitrary tail calls, only for those it can transform into loops (i.e. when the function calls itself, not some other function).

这篇关于是否可以使用延续使foldRight尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！