99 Scala Problems 09 - Pack consecutive duplicates of list elements into sublists
By Leonardo Giordani - Updated on
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.
Part 9 of the 99 Scala Problems series
Previous articles
- 99 Scala Problems 01 - Find the last element of a list
- 99 Scala Problems 02 - Find the last but one element of a list
- 99 Scala Problems 03 - Find the Kth element of a list
- 99 Scala Problems 04 - Find the number of elements of a list
- 99 Scala Problems 05 - Reverse a list
- 99 Scala Problems 06 - Find out whether a list is a palindrome
- 99 Scala Problems 07 - Flatten a nested list structure
- 99 Scala Problems 08 - Eliminate consecutive duplicates of list elements
Next articles
- 99 Scala Problems 10 - Run-length encoding of a list.
- 99 Scala Problems 11 - Modified run-length encoding
- 99 Scala Problems 12 - Decode a run-length encoded list
- 99 Scala Problems 13 - Run-length encoding of a list (direct solution)
- 99 Scala Problems 14 - Duplicate the elements of a list
- 99 Scala Problems 15 - Duplicate the elements of a list a given number of times
- 99 Scala Problems 16-20