Ninety-Nine Scala Problems: Problem 09 - Pack consecutive duplicates of list elements into sublists.

Problem09.scala

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

// P09 (**) Pack consecutive duplicates of list elements into sublists.
// If a list contains repeated elements they should be placed in separate sublists.
// Example:

// scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

object Problem09 {
  def main(args: Array[String]) {
    val values = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
    println(pack(values))
  }

  def span[T](values: List[T])(predicate: T => Boolean) : (List[T], List[T]) = 
    spanTail(Nil, values) { predicate }

  def spanTail[T](matched: List[T], remaining: List[T])(predicate: T => Boolean) : (List[T], List[T]) = 
    remaining match {
      case x :: xs if (predicate(x)) => spanTail(x :: matched, xs) { predicate }
      case _                         => (matched, remaining)
    }

  // def pack[T](values: List[T]) : List[List[T]] = 
  //   values match {
  //     case Nil     => Nil
  //     case x :: xs => 
  //       val (repeats, remaining) = values span { _ == x }
  //       repeats :: pack(remaining)
  //   }

  def pack[T](values: List[T]) : List[List[T]] = 
    packTail(Nil, values)

  def packTail[T](packed: List[List[T]], remaining: List[T]) : List[List[T]] = 
    remaining match {
      case Nil     => packed
      case x :: xs => 
        val (repeats, leftovers) = span(remaining) { value : T => value == x }
        packTail(packed ::: repeats :: Nil, leftovers)
    }
}