Можно ли использовать продолжения, чтобы сделать хвостовую рекурсию foldRight рекурсивной?

Следующая статья в блоге показывает, как в F # foldBack может быть сделана хвостовой рекурсивной с использованием стиля передачи продолжения.

В Scala это означало бы, что:

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
  }
} 

можно сделать хвостовой рекурсивной, выполнив следующее:

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

К сожалению, Я все еще получаю переполнение стека для длинных списков. Цикл является хвостовым рекурсивным и оптимизированным, но я предполагаю, что накопление стека просто перемещается в вызовы продолжения.

Почему это не проблема с F #? И есть ли способ обойти это с помощью Scala?

Edit : вот код, показывающий глубину стека:

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

10
задан huynhjl 18 December 2011 в 03:26
поделиться