99 Scala Problems 12 - Decode a run-length encoded list
By Leonardo Giordani - Updated on
The problem¶
P12 (**) Decode a run-length encoded list. Given a run-length code list generated as specified in problem P10, construct its uncompressed version.
Example:
scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
Initial thoughts¶
The problem is simple, being just a reverse version of the last two problems. The target is to build a list from another one, so it should be possible to find both a recursive and a functional solution. The only problem is that we may easily build a list for each element, but we shall end up with a flat list. So flatMap()
from problem 07 will come in play again.
The recursive solution¶
Since I decided to use flatMap()
, which basically acts like map()
but then inserts the resulting list into the target list (indeed flattening it), I have to write a function that converts a (Int, A)
tuple into a List[A]
, where A
is a type of choice.
The only issue in building lists in Scala is that the :::
operator works with two lists, so we have to build a list with the current head to be able to append it.
def decode[A](l: List[(Int, A)]):List[A] = {
def _expand(res: List[A], rem:(Int, A)):List[A] = rem match {
case (0, _) => res
case (n, h) => _expand(res:::List(h), (n -1, h))
}
l flatMap { e => _expand(List(),e) }
}
The last call is a mapping. Each element is mapped into a list by the _expand()
function, while flatMap()
does the flattening job.
The functional solution¶
There is a simpler way that makes use of a function of the List
object. Object and classes are two different entities in Scala, and objects are singletons that encapsulate constructor (and de-constructor) methods.
The fill()
method is documented here, and we are interested now in the one-dimensional version. As you can see from the documentation, this function is curried (see problem 04) and accepts as first parameter the length of the list and as second parameter the element to put into the list itself.
We are just interested in repeating an element this time, so the function invocation is very simple
def decode2[A](l: List[(Int, A)]):List[A] = {
l flatMap { e => List.fill(e._1)(e._2) }
}
Scala tuples may be indexed using the _index
notation, starting from 1 (while lists are indexed from 0). Here, just like in the recursive solution, we have to use flatMap()
to flatten the resulting list.
Final considerations¶
Writing this solution I renewed my knowledge of flatmapping, learned that Scala classes have companion objects, learned how to create lists and how to index tuples.
Feedback¶
The GitHub issues page is the best place to submit corrections.
Part 12 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
- 99 Scala Problems 09 - Pack consecutive duplicates of list elements into sublists
- 99 Scala Problems 10 - Run-length encoding of a list.
- 99 Scala Problems 11 - Modified run-length encoding