Ninety-Nine Scala Problems: Problem 05 - Reverse a list.

Problem05.scala

// From: http://aperiodic.net/phil/scala/s-99/

// P05 (*) Reverse a list.
// Example:
// scala> reverse(List(1, 1, 2, 3, 5, 8))
// res0: List[Int] = List(8, 5, 3, 2, 1, 1)

object Problem05 {
  def main(args: Array[String]) {
    val values = List(1, 1, 2, 3, 5, 8)
    println(reverse(values))
  }	

  // def reverse[T](values: List[T]) : List[T] = 
  //   values match {
  //     case Nil      => List[T]()
  //     case x :: Nil => List[T](x)
  //     case x :: xs  => reverse(xs) ::: List[T](x)
  //   }

  def reverse[T](values: List[T]) : List[T] = 
    reverseTail(Nil, values)

  def reverseTail[T](seen: List[T], remaining: List[T]) : List[T] = 
    remaining match {
      case Nil      => seen
      case x :: Nil => x :: seen
      case x :: xs  => reverseTail(x :: seen, xs)
    }
}