99 Scala Problems 03 - Find the Kth element of a list
By Leonardo Giordani - Updated 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 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.
Part 3 of the 99 Scala Problems series
Previous articles
- 99 Scala Problems 01 - Find the last element of a list
- 99 Scala Problems 02 - Find the last but one element of a list
Next articles
- 99 Scala Problems 04 - Find the number of elements of a list
- 99 Scala Problems 05 - Reverse a list
- 99 Scala Problems 06 - Find out whether a list is a palindrome
- 99 Scala Problems 07 - Flatten a nested list structure
- 99 Scala Problems 08 - Eliminate consecutive duplicates of list elements
- 99 Scala Problems 09 - Pack consecutive duplicates of list elements into sublists
- 99 Scala Problems 10 - Run-length encoding of a list.
- 99 Scala Problems 11 - Modified run-length encoding
- 99 Scala Problems 12 - Decode a run-length encoded list
- 99 Scala Problems 13 - Run-length encoding of a list (direct solution)
- 99 Scala Problems 14 - Duplicate the elements of a list
- 99 Scala Problems 15 - Duplicate the elements of a list a given number of times
- 99 Scala Problems 16-20