The problem

P03 (*) Find the Kth element of a list. By convention, the first element in the list is element 0.

Example:

scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2

Initial thoughts

I expect the solution to be trivial using the indexing capabilities of List types, such as in any language that supports indexed lists. The functional solution cannot use indexing and shall reduce the list element by element.

The procedural solution

def findKth[A](k:Int, l:List[A]):A = {
    if (k >= 0 && k < l.length) l(k)
    else throw new NoSuchElementException
}

Since indexing out of bounds (in both directions) throws IndexOutOfBoundsException we first check if the index is safe. The logical AND operation is expressed in Scala by &&.

Knowing that a wrong indexing throws an exception we could also catch it and throw the 'right' one. This results in 

def findKth[A](k:Int, l:List[A]):A = {
    try l(k)
    catch {
        case e:IndexOutOfBoundsException => throw new NoSuchElementException
    }
}

which probably states more clearly that the main job of the function is to replace one exception with another one.

The recursive solution

A recursive solution is pretty straightforward. We just repeatedly remove the first element and decrease the given index until it reaches 0. Using a couple of methods from the List type the solution is

def findKth[A](k:Int, l:List[A]):A = k match {
    case 0 => l.head
    case k if k > 0 => findKth(k - 1, l.tail)
    case _ => throw new NoSuchElementException  
}

If however we try to avoid the use of methods, just to see if we may solve it with a pure recursive approach, we need to match two things together, which leads to

def findKth[A](k:Int, l:List[A]):A = (k,l) match {
    case (0, h::_) => h
    case (k, _::tail) if k > 0 => findKth(k - 1, tail)
    case _ => throw new NoSuchElementException
}

The "new" thing here is that we are pattern matching a tuple of values (which is, after all, one value of a given type). Moreover, Scala pattern matching shows us another strength point in that it can match a case and simultaneously operate on the variables (in this case splitting the list).

The first case is the exit case, where the counter reached 0 and the list has an head to return, which is the nth element. Otherwise the first element of the list is removed and the function called with a decremented index. The last line covers the empty list case.

Final considerations

The procedural approach made me learn how to catch exceptions in Scala and how to perform logical comparisons. The recursive solution taught me pattern matching of multiple values.

Feedback

The GitHub issues page is the best place to submit corrections.