Packing symbols using scanLeft

Question

99 scala problems has this question:

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

I have an understanding of the tail-recursive way to solve the above given problem. I was wondering if there was a way to accomplish the above using scanLeft where the intermediate result is the list of common elements?

Answer 1

Here's a solution using foldLeft:

def pack[A](l:List[A]): List[List[A]] = l match {
  case head :: tail =>
    tail.foldLeft(List(List(head))) { (collector:List[List[A]], elem:A) =>
      if (collector.head.head == elem)
        (elem +: collector.head) +: collector.tail
      else
        List(elem) +: collector
    }.reverse
  case _ => List.empty
}

This only works for Lists. A better solution would probably use MultiSets, although finding a Scala implementation is difficult.

Answer 2

A concise but unoptimized version could look like this:

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
for (i <-l.distinct) yield l.filter(_ == i)

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