Getting the nth element of a list

A list holds a certain number of elements. The first element is at index 0, and the second element at index 1. If the index is out of range, we get an exception.

We will write a method to find the nth element of a list. This method will return an option. If n is out of bounds, we will return None. Otherwise, we will return Some(elem). Let's look at the code and then a diagram to understand it better:

import scala.annotation.tailrec
object NthElemOfList extends App {
 def nth(list: List[Int], n: Int): Option[Int] = {
  @tailrec
  def nthElem(list: List[Int], acc: (Int, Int)): Option[Int] = list match {
    case Nil => None
    case head :: tail => {
     if (acc._1 == acc._2)     // 1
     Some(head)    
    else
      nthElem(tail, (acc._1 + 1, acc._2))     // 2
   }
   }
  nthElem(list, (0, n))   // 3
 }
 val bigList = 1 to 100000 toList  // 4
 println(nth(List(1, 2, 3, 4, 5, 6), 3).getOrElse("No such elem"))
 println(nth(List(1, 2, 3, 4, 5, 6), 300).getOrElse("No such elem"))
 println(nth(bigList, 2333).getOrElse("No such elem"))
}

Here is a diagrammatic representation of the flow:

Figure: 3.4: Conceptual stack frames

The description of the preceding diagram is as follows:

• Our accumulator is a pair. The first element is a running index and holds the index of the current node, starting from 0. The second element is always fixed at n.
• If index == n, we have found the element. Now, we will return it wrapped in a some. else we increase the running index and recursively call the method again on the tail of the list.
• We wish to hide the accumulator from the client code. Keeping an accumulator is an implementation detail.
• We will test the index with a very big list as @tailrec is in effect, the TCO kicks in and we don't get any stack overflows. Try to rewrite the preceding code without using a pair of element for the accumulator. Compare your version with it and check which one is better.

The following are a few points that we need to ponder:

• Could we simply use acc as Int? Do we really need the pair?
• Try writing the code so that we decrement the accumulator instead of incrementing it.