huynhjl - 1 month ago 3
Scala Question

# Is it possible to use continuations to make foldRight tail recursive?

The following blog article shows how in F#

`foldBack`
can be made tail recursive using continuation passing style.

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.

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)(_ + _)
``````

This prints:

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

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.