Tail recursion issue

Question

We were experimenting with parallel collections in Scala and wanted to check whether the result was ordered. For that, I wrote a small function on the REPL to do that check on the very large List we were producing:

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

It fails with a stackOverflow (how appropriate for a question here!). I was expecting it to be tail-optimized. What's wrong?

Answer 1

Your algorithm is incorrect. Even with @Kim's improvement, isOrdered(List(4,3,5,4)) returns true.

Try this:

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

(also updated so that signs are correct)

edit: my perferred layout would be this:

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

The quick way if performance isn't a problem would be

def isOrdered(l: List[Int]) = l == l.sorted

Answer 2

isOrdered is not the last call in your code, the & operator is. Try this instead:

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

Answer 3

I think the problem is that you're using the bitwise-and operator (&) in your last case. Since the runtime needs to know the value of the isOrdered call before it can evaluate the &, it can't tail-optimize the function. (That is, there is more code to run--the bitwise-and operation--after isOrdered is called.)

Using && or an if statement may help.

Answer 4

It can't be tail-optimized because you return this: 'x>y & isOrdered(tail)'. It means it will need to keep it on the stack.

Use the @tailrec annotation to force an error when you expect functions to be tail-recursive. It will also explain why it can't be.