## 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.