My take on 99 problems in Scala (first 22)

A while ago I saw 99 problems in Prolog they looked really good and I started trying to solve them in Scala. Now, thanks to Tony Morris I found that there's a Scala version!
Nice stuff to get your skills up to shape. It helped me to improve my understanding of folds, maps, flatMaps, zips, etc. Also I learned new pattern matching techniques (tuples and guards).
You must really give the exercises a shot!
Here are my solutions:




package exercises

object NinetyNine {
  //P01
  def last[A](xs: List[A]): A = xs match {
    case x :: Nil => x
    case x :: xs => last(xs)
    case Nil => throw new NoSuchElementException
  }

  //P02
  def penultimate[A](xs: List[A]): A = xs match {
    case x :: y :: Nil => x
    case x :: xs => penultimate(xs)
    case _ => throw new NoSuchElementException
  }

  //P03
  def nth[A](i: Int, xs: List[A]): A = xs match {
    case x :: xs => if (i == 0) x else nth(i - 1, xs)
    case _ => throw new NoSuchElementException
  }

  def nth2[A](i: Int, xs: List[A]): A = xs match {
    case x :: xs if (i == 0) => x
    case x :: xs if (i > 0) => nth(i - 1, xs)
    case _ => throw new NoSuchElementException
  }

  //P04
  def length[A](xs: List[A]): Int = xs match {
    case x :: xs => 1 + length(xs)
    case Nil => 0
  }

  //Although straight recursion is fun, using folds is more effective
  // folds are abstractions for recursion over data structures

  //P04
  def length1[A](xs: List[A]): Int = xs.foldLeft(0)((a, b) => a + 1)

  //P05
  def reverse[A](xs: List[A]): List[A] = xs.foldLeft(Nil: List[A])((a, b) => b :: a)

  //P06
  def isPalindrome[A](xs: List[A]): Boolean = reverse(xs) == xs

  //P07
  def flatten[A](xs: List[List[A]]): List[A] = xs.foldRight(Nil: List[A])(
    (xs, acc) => xs match {
      case ys: List[A] => ys ::: acc
      case y: A => y :: acc
    })

  //P08
  def compress[A](xs: List[A]): List[A] =
    xs.foldRight(List[A]())((y, ys) =>
      if (ys != Nil && ys.head == y) ys else y :: ys)

  //P09
  def pack[A](xs: List[A]): List[List[A]] = xs match {
    case Nil => Nil
    case _ => xs.takeWhile(_ == xs.head) :: pack(xs.dropWhile(_ == xs.head)) //can use span too, see P13
  }

  //P10
  def encode[A](xs: List[A]): List[(Int, A)] =
    pack(xs).map(y => (y.length, y.head))

  //P11
  def encodeModified[A](xs: List[A]): List[Any] =
    pack(xs).map(
      y => if (y.length == 1) y.head else (y.length, y.head))

  //Type safe version
  def encodeModifiedTypSafe[A](xs: List[A]): List[Either[A, (Int, A)]] =
    pack(xs).map(
      y =>
        if (y.length == 1) Left(y.head)
        else Right(y.length, y.head))

  //P12
  def decode[A](xs: List[(Int, A)]): List[A] = {
    def expand(i: Int, a: A): List[A] = if (i == 0) Nil else a :: expand(i - 1, a)
    flatten(xs.foldRight(List[List[A]]())((y, ys) => expand(y._1, y._2) :: ys))
  }
  //is better with flatMap
  def decode1[A](xs: List[(Int, A)]): List[A] =
    xs.flatMap(ny => List.make(ny._1, ny._2))

  //P13
  def encodeDirect[A](xs: List[A]): List[(Int, A)] = xs match {
    case Nil => Nil
    case _ => {
      val ys = xs.span(_ == xs.head)
      (ys._1.length, xs.head) :: encodeDirect(ys._2)
    }
  }

  //P14
  def duplicate[A](xs: List[A]): List[A] =
    xs.foldRight(Nil: List[A])((y, ys) => y :: y :: ys)
  //is better with flatMap
  def duplicate1[A](xs: List[A]): List[A] = xs.flatMap(y => y :: y :: Nil)

  //P15
  def duplicateN[A](n: Int, xs: List[A]): List[A] =
    xs.foldRight(Nil: List[A])((y, ys) => (1 to n).toList.map(_ => y) ::: ys)
  //is better with flatMap
  def duplicateN1[A](n: Int, xs: List[A]): List[A] =
    xs.flatMap(y => List.make(n, y))

  //P16
  def drop[A](n: Int, xs: List[A]): List[A] =
    xs.zipWithIndex.filter(_._2 % n != 0).map(_._1)

  //P17
  def split[A](n: Int, xs: List[A]): (List[A], List[A]) =
    xs.splitAt(n) // or (xs.take(n),xs.drop(n))

  //ok, that was too easy, let's try recursion
  def splitRec[A](n: Int, xs: List[A]): (List[A], List[A]) =
    (n, xs) match {
      case (0, _) => (Nil, xs)
      case (_, y :: ys) => {
        val rec = splitRec(n - 1, ys)
        (y :: rec._1, rec._2)
      }
      case (_, Nil) => (xs, Nil)
    }

  //P18
  def slice[A](s: Int, e: Int, xs: List[A]): List[A] =
    xs.slice(s, e) // or xs.drop(s).take(e-s)

  //with recursion
  def sliceRec[A](s: Int, e: Int, xs: List[A]): List[A] =
    (s, e, xs) match {
      case (0, 0, xs) => Nil
      case (0, _, y :: ys) => y :: sliceRec(0, e - 1, ys)
      case (_, _, y :: ys) => sliceRec(s - 1, e - 1, ys)
    }

  //P19
  def rotate[A](n: Int, xs: List[A]): List[A] = {
    val s = split((if (n > 0) n else n + xs.length), xs)
    s._2 ::: s._1
  }

  //P20
  def removeAt[A](n: Int, xs: List[A]): (List[A], A) = {
    val (heads, tails) = split(n, xs)
    (heads ::: tails.tail, tails.head)
  }

  //P21
  def insertAt[A](e: A, n: Int, xs: List[A]): List[A] = {
    val (heads, tails) = split(n, xs)
    heads ::: e :: tails
  }
  //with recursion
  def insertRecAt[A](e: A, n: Int, xs: List[A]): List[A] =
    (n, xs) match {
      case (0, ys) => e :: ys
      case (_, y :: ys) => y :: insertRecAt(e, n - 1, ys)
    }

  //P22
  def range[A](s: Int, e: Int): List[Int] = (s to e).toList

  //I don't think is the purpose of the exercise! Again, let's try recursion
  def rangeRec(s: Int, e: Int): List[Int] = if (e - s == 0) e :: Nil else s :: rangeRec(s + 1, e)

  //recursion and pattern matching with guards
  //a little more readable
  def rangeRecPm(s: Int, e: Int): List[Int] = (e - s) match {
    case x if (x > 0) => s :: rangeRecPm(s + 1, e)
    case x if (x == 0) => e :: Nil
    case _ => error("Invalid range")
  }

}


[EDIT: fixed problem 20 ]