title: Is it possible to use continuations to make foldRight tail recursive?
body: <p>The following <a href="http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/" rel="noreferrer">blog article</a> shows how in F# <code>foldBack</code> can be made tail recursive using continuation passing style.</p>
  
  <p>In Scala this would mean that: </p>
  
  <pre><code>def foldBack[T,U](l: List[T], acc: U)(f: (T, U) =&gt; U): U = {
    l match {
      case x :: xs =&gt; f(x, foldBack(xs, acc)(f))
      case Nil =&gt; acc
    }
  } 
  </code></pre>
  
  <p>can be made tail recursive by doing this:</p>
  
  <pre><code>def foldCont[T,U](list: List[T], acc: U)(f: (T, U) =&gt; U): U = {
    @annotation.tailrec
    def loop(l: List[T], k: (U) =&gt; U): U = {
      l match {
        case x :: xs =&gt; loop(xs, (racc =&gt; k(f(x, racc))))
        case Nil =&gt; k(acc)
      }
    }
    loop(list, u =&gt; u)
  } 
  </code></pre>
  
  <p>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. </p>
  
  <p>Why is this not a problem with F#? And is there any way to work around this with Scala?</p>
  
  <p><em>Edit</em>: here some code that shows depth of stack:</p>
  
  <pre><code>def showDepth(s: Any) {
    println(s.toString + ": " + (new Exception).getStackTrace.size)
  }
  
  def foldCont[T,U](list: List[T], acc: U)(f: (T, U) =&gt; U): U = {
    @annotation.tailrec
    def loop(l: List[T], k: (U) =&gt; U): U = {
      showDepth("loop")
      l match {
        case x :: xs =&gt; loop(xs, (racc =&gt; { showDepth("k"); k(f(x, racc)) }))
        case Nil =&gt; k(acc)
      }
    }
    loop(list, u =&gt; u)
  } 
  
  foldCont(List.fill(10)(1), 0)(_ + _)
  </code></pre>
  
  <p>This prints:</p>
  
  <pre><code>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
  </code></pre>