S09

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向で。

// 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))

// tail recursion
def reverse[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => result
    case h :: t => recursive(t, h :: result)
  }
  recursive(xs, Nil)
}

// tail recursion
def removeLast[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => throw new NoSuchElementException
    case h :: Nil => result
    case h :: t => recursive(t, h :: result)
  }
  reverse(recursive(xs, Nil))
}

// tail recursion
def pack[T](xs: List[T]): List[List[T]] = {
  def recursive(rest: List[T], acc: List[List[T]]): List[List[T]] = {
    rest match {
      case Nil => acc
      case h :: t if(acc != Nil && h == acc.last.head) => 
        val nextAcc = List(h :: acc.last) //List[Listt[T]]
        recursive(t, removeLast(acc) ++ nextAcc) // List[List[T]] ++ List[List[T]] => List[List[T]]
      case h :: t =>
        val nextAcc = acc ++ List(List(h))
        recursive(t, nextAcc)
    }
  }
  recursive(xs, Nil)
}

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
println(pack(l)) //=>  List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

解答例
spanっすか。