scalania13.scala

def encodeDirect[T](ts: Seq[T]): Seq[(Int, T)] = {
  @tailrec
  def go(ts: Seq[T], acc: Seq[(Int, T)]): Seq[(Int, T)] = ts match {
    case Seq() => acc
    case head +: tail =>
      val (same, different) = ts.span(_ == head)
      go(different, acc :+ (same.length, head))
  }
  go(ts, Seq())
}

@tailrec
def nth[T](k: Int, ts: Seq[T]): T = (k, ts) match {
  case (0, t +: ts) => t
  case (k, t +: ts) if k > 0 => nth(k - 1, ts)
  case _ => throw new NoSuchElementException
}