99 Scala Problems 09 - Pack consecutive duplicates of list elements into sublists

The problem¶

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

Initial thoughts¶

This is similar to problem 08 but has an important difference: the result will be a list of lists. When dealing with multi-level structures like these, it is very easy to get lost, so I expect to find a recursive solution with a lot of cases or complex pattern guards.

The recursive solution¶

The tail recursive solution is easier to write than the standard recursive one. The resulting list we are building is a List[List[A]], while the remainder is just a plain list List[A].

The first case is straightforward. The second case extracts an element from the list and, if the result is empty of the result doesn't contain that element, appends a new list. Pay attention: we have to check res.last.head since res is a list of lists. So res.last is the last list we put into res and its head is the repeated element. Obviously the same thing is accomplished by checking res.last.last, since this algorithm packs together equal values. The third case covers the situation in which the extracted element is already in the last list or res, so we have to modify the latter. To do this we separate res in res.init and res.last, append h to res.last (res.last:::List(h)) and merge again the two pieces.

def pack[A](l: List[A]):List[List[A]] = {
    def _pack(res: List[List[A]], rem: List[A]):List[List[A]] = rem match {
        case Nil => res
        case h::tail if (res.isEmpty || res.last.head != h) => _pack(res:::List(List(h)), tail)
        case h::tail => _pack(res.init:::List(res.last:::List(h)), tail)
    }
    _pack(List(),l)
}

A very simpler solution, however, comes from the span() method of List objects. This method "splits this list into a prefix/suffix pair according to a predicate."

In other words, span() selects the elements of the list (preserving order) that satisfy a given function until it finds an element for which the function returns false. This is exactly what we need to pack consecutive duplicate elements. The strategy is to pack all elements with the same value of the list head element, then store this list and recursively call span() on the remaining list.

def pack[A](l: List[A]):List[List[A]] = {
    def _pack(res: List[List[A]], rem: List[A]):List[List[A]] = rem match {
        case Nil => res
        case ls => {
            val (s: List[A], r: List[A]) = rem span { _ == rem.head }
            _pack(res:::List(s), r)
        }
    }
    _pack(List(), l)
}

The function I pass to span() is simply { _ == rem.head } since the method gives the function each element in the list.

Final considerations¶

This problem helped me enhance my knowledge of pattern guards and Scala anonymous functions. The solution with span() includes a pattern match that leads to a block expression, which was somehow a syntactical blind guess for me, but ended up being perfectly valid.

Feedback¶

The GitHub issues page is the best place to submit corrections.