Skip to main content

99 Scala Problems Challenge – 2/99

Problem 2 – Find the last but one element of a list

P02 (*) Find the last but one element of a list.
Example:
scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5

Empty list and one element list scenario

I’ve started with a test which stated, that both empty and one-element list should return None.


class P02Test extends FunSuite with Matchers {

  val p02 = new P02[Int]()

  test("that returns none for empty list") {
    p02.penultimate(List()) should be(None)
  }

  test("that returns none for one-element list") {
    p02.penultimate(List(5)) should be(None)
  }
}

And implementation was simple enough to fit the requirements

class P02[T] {
  def penultimate(list: List[T]): Option[T] = None
}

 

One more element

Next natural test was scenario when list was of size == 2

	   
test("that returns first element of two-elements list") {
  p02.penultimate(List(5, 7)) should be(Some(5))
}

Knowing what I’ve learned from problem P01, I used pattern matching

    
def penultimate(list: List[T]): Option[T] = list match {
  case Nil => None
  case head :: Nil => None
  case head :: tail => Some(head)
}    

 

Final test

    
test("that returns last but one element of list with size > 2") {
  p02.penultimate(List(8, 9, 1, 5, 7, 3)) should be(Some(7))
}

Change in the implementation was simpler then I’ve imagined. Last matching case was divided into two, where the last one was calling recursively penultimate function

  
def penultimate(list: List[T]): Option[T] = list match {
  case Nil => None
  case head :: Nil => None
  case lastButOne :: last :: Nil => 	 Some(lastButOne)
  case head :: tail => penultimate(tail)
}

 

Few words about tail recursion

My final solution is using a recursive call. Normally calling function recursively might lead to stack overflow. With each recursive call, current calculations must be put on the stack, which has its limits.
However if you look at it, you can see that recursive call is in a tail position.

Tail recursion. A recursive function is tail recursive if the final result of the recursive call is the final result of the function itself. If the result of the recursive call must be further processed (say, by adding 1 to it, or consing another element onto the beginning of it), it is not tail recursive.
haskell.org

Scala can detect this self-recursion during compilation and eliminate it. On the bytecode level, instead of recursive calls we end up with while loops. This process is mostly refereed to as tail-elimination

Since Scala 2.8 there is an annotation scala.annotation.tailrec. This annoation will make compiler to yiel whenever he can not eliminate recursive call on annotated function. I thought, why not to give it a try.

I’ve annotated my function with tailrec and as it turned out, compiler yield an error!

Error:(8, 7) could not optimize @tailrec annotated method penultimate: it is neither private nor final so can be overridden

Error was self-explaintionary. I’ve added final keyword to function definition

  
	@tailrec
	final def penultimate(list: List[T]): Option[T] = list match {
    	case Nil => None
    	case head :: Nil => None
    	case lastButOne :: last :: Nil => Some(lastButOne)
    	case head :: tail => penultimate(tail)
	}

Solution is working and now is guarded by the compiler to be tail-eliminated.

Comparing to reference solution

The reference solution to the problem was

  
	def penultimateRecursive[A](ls: List[A]): A = ls match {
    	case h :: _ :: Nil => h
    	case _ :: tail     => penultimateRecursive(tail)
    	case _             => throw new NoSuchElementException
  }

1. Again as in problem P01 they’ve used exceptions instead of returning Option
2. Beside that, implementation was pretty much the same

 

Source code for this blog post is available at Github.

  • Firstly, I’m really glad you are doing this sreies, there seems to always be some little nugget of information in your posts.Now I know this post is about head and tail but I thought it would be worth mentioning the way of reversing access to a list using a range.def list = [1, 2, 3, 4]assert [4, 3, 2, 1] == list[-1..0] // just as tail() it works for lists with size() > 0