By Leonardo Giordani Published on

## 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 until 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 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¶

Feel free to use the blog Google+ page to comment the post. The GitHub issues page is the best place to submit corrections.