Ninety-Nine Scala Problems: Problem 07 - Flatten a nested list structure.

Problem07.scala

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

// P07 (**) Flatten a nested list structure.
// Example:
// scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
// res0: List[Any] = List(1, 1, 2, 3, 5, 8)

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

  // def flatten(values: List[Any]) : List[Any] = 
  //   values match {
  //     case Nil                => Nil
  //     case (x: List[_]) :: xs => flatten(x) ::: flatten(xs)
  //     case x :: xs            => x :: flatten(xs)
  //   }

  def flatten(values: List[Any]) : List[Any] = 
    flattenTail(Nil, values)

  def flattenTail(seen: List[Any], remaining: List[Any]) : List[Any] = 
    remaining match {
      case Nil                => seen
      case (x: List[_]) :: xs => flattenTail(seen ::: flatten(x), xs)
      case x :: xs            => flattenTail(seen ::: List(x), xs)
    }
}