Skip to main content

99 Scala Problems – 3/99

Problem 3 – Find the Kth element of a list.

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

Return n-th element

As the problem seemed easy and straightforward I wrote first test that checked general case

class P03Test extends FunSuite with Matchers {
  val p03 = new P03[Int]()

  test("that returns nth element") {
    p03.nth(0, List(7, 6, 2, 3, 5, 8)) should be(7)
  }

Implementation was nothing more then, well …, returning the n-th element

class P03[T] {
  def nth(nth: Int, list: List[T]): T = list(nth)
}

Well, that was oddly fast. I knew there must be something more to it.

Corner cases

I’ve added implementation for two corner cases:

1. when n-th argument is greater then list size

test("that fails if nth bigger then size of the list") {
  p03.nth(30, List(7, 6, 2, 3, 5, 8)) should be(None)
}

class P03[T] {
  def nth(nth: Int, list: List[T]): Option[T] = if (nth < list.size) Some(list(nth)) else None
}

2. and when n-th argument value is less then 0

test("that fails if nth smaller then 0") {
  p03.nth(-1, List(7, 6, 2, 3, 5, 8)) should be(None)
}

class P03[T] {
  def nth(nth: Int, list: List[T]): Option[T] =
  if (nth < list.size && nth >= 0) Some(list(nth)) else None
}

Reimplementation

Having problem solved in matter of minutes made me wonder whether this was the aim of the exercise. Implementation was correct, but yet again target of this challenge is to try to learn something new each time. I reckoned I will try to re-implement the solution just using pattern matching. This was what I came up with:


class P03[T] {
  @tailrec
  final def nth(n: Int, list: List[T]): Option[T] = (n, list) match {
    case (0, head :: tail) => Some(head)
    case (_, Nil) => None
    case (x, _) if x < 0 => None
    case (x, head :: tail) => nth(x - 1, tail)
  }
}

Reference implementation

Reference implementation of the problem was


def nthRecursive[A](n: Int, ls: List[A]): A = (n, ls) match {
  case (0, h :: _ ) => h
  case (n, _ :: tail) => nthRecursive(n - 1, tail)
  case (_, Nil ) => throw new NoSuchElementException
}

which I must admit was a shorter version of my solution

Final thoughts

I realised that, at least for all the problems marked as (*) in this challenge, I will try not to used build-in solutions, but will rather look for my own implementation.

On the final note, if you see a better solution to the problem P03, please let me know in comments.

 

Source code for this blog post is available at Github.