Reverse list Scala

Question

Given the following code:

import scala.util.Random

object Reverser {

  // Fails for big list
  def reverseList[A](list : List[A]) : List[A] = {
    list match {
      case Nil => list
      case (x :: xs) => reverseList(xs) ::: List(x)
    }
  }

  // Works
  def reverseList2[A](list : List[A]) : List[A] = {
    def rlRec[A](result : List[A], list : List[A]) : List[A] = {
      list match {
        case Nil => result
        case (x :: xs) => { rlRec(x :: result, xs) }
      }
    }
    rlRec(Nil, list)
  }

  def main(args : Array[String]) : Unit = {
    val random = new Random
    val testList = (for (_ <- 1 to 2000000) yield (random.nextInt)).toList
    // val testListRev = reverseList(testList) <--- Fails
    val testListRev = reverseList2(testList)
    println(testList.head)
    println(testListRev.last)
  }
}

Why the first version of the function fails (for big inputs), while the second variant works . I suspect it's something related to tail recursion, but I am not very sure . Can somebody please give me "for dummies" explanation ?

Solution 1

Ok let me try tail recursion for dummies

If you follow what has to be done with reverseList, you will get

reverseList(List(1,2,3, 4))
reverseList(List(2,3,4):::List(1)
(reverseList(List(3,4):::List(2)):::List(1)   
((reverseList(List(4):::List(3)):::List(2)):::List(1)
Nil:::List(4):::List(3):::List(2):::List(1)
List(4,3,2,1)

With rlRec, you have

rlRec(List(1,2,3,4), Nil)
rlRec(List(2,3,4), List(1))
rlREc(List(3,4), List(2,1))
rlRec(List(4), List(3,2,1))
rlRec(Nil, List(4,3,2,1))
List(4,3,2,1)

The difference is that in first case, the rewriting keeps getting longer. You have to remember thing to do after the last recursive call to reverseList will have completed: elements to add to the result. The stack is used to remember that. When this goes too far, you get a stack overflow. On the opposite, with rlRec, the rewriting has the same size all along. When the last rlRec completes, the result is available. There is nothing else to do, nothing to remember, no need for the stack. The key is that in rlRec, the recursive call is return rlRec(something else) while in reverseList it is return f(reverseList(somethingElse)), with f beging _ ::: List(x). You need to remember you will have to call f (which implies remembering x too) ( return not needed in scala, just added for clarity. Also note that val a = recursiveCall(x); doSomethingElse() is the same as doSomethingElseWith(recursiveCall(x)), so it is not a tail call)

When you have a recursive tail call

def f(x1,...., xn)
    ...
    return f(y1, ...yn)
    ...

there is actually no need to remember the context of the first f for when the second one will return. So it can be rewritten

def f(x1....xn)
start:
    ...
    x1 = y1, .... xn = yn
    goto start
    ...

That is what the compiler does, hence you avoid the stack overflow.

Of course, function f needs to have a return somewhere which is not a recursive call. That is where the loop created by goto start will exit, just as it is where the recursive calls series stops.

Solution 2

Function is called tail recursive when it call itself as it's last action. You can check if the function is tail recursive by adding @tailrec annotation.

Solution 3

You can make your tail-recursive version as simple as the non-tail-recursive version by using a default argument to give an initial value for the results:

def reverseList[A](list : List[A], result: List[A] = Nil) : List[A] = list match {
  case Nil => result
  case (x :: xs) => reverseList(xs, x :: result)
}

Although you can use this in the same way as the others, i.e. reverseList(List(1,2,3,4)), unfortunately you're exposing an implementation detail with the optional result parameter. Currently there doesn't seem to be a way to hide it. This may or may not worry you.

Solution 4

As others have mentioned, tail-call elimination avoids growing the stack when it is not needed. If you're curious about what the optimization does, you can run

scalac -Xprint:tailcalls MyFile.scala

...to show the compiler intermediate representation after the elimination phase. (Note that you can do this after any phase, and you can print the list of phases with scala -Xshow-phases.)

For instance, for your inner, tail-recursive function rlRec, it gives me:

def rlRec[A >: Nothing <: Any](result: List[A], list: List[A]): List[A] = {
  <synthetic> val _$this: $line2.$read.$iw.$iw.type = $iw.this;
  _rlRec(_$this,result,list){
    list match {
      case immutable.this.Nil => result
      case (hd: A, tl: List[A])collection.immutable.::[A]((x @ _), (xs @ _)) => _rlRec($iw.this, {
        <synthetic> val x$1: A = x;
        result.::[A](x$1)
      }, xs)
    }
  }
}

Nevermind there synthetic stuff, what matters is that _rlRec is a label (even though it looks like a function), and the "call" to _rlRec in the second branch of the pattern-matching is going to be compiled as a jump in bytecode.

Solution 5

The first method is not tail recursive. See:

case (x :: xs) => reverseList(xs) ::: List(x)

The last operation invoked is :::, not the recursive call reverseList. The other one is tail recursive.

View more solutions

Comments

[Ben]

The Scala List class features a method called reverse_::: that does almost exactly this. The docs describe what it does like so: "Adds the elements of a given list in reverse order in front of this list". Suddenly, that "extra" argument is a feature! We can do someList reverse_::: Nil to reverse it, or someList reverse_::: otherList to reverse someList onto the front of otherList. It's often the case that with a little "rebranding", the extra argument you add to a function in order to support tail recursion (called an accumulator) actually generalises the purpose of your method.