99 Scala Problems 10 - Run-length encoding of a list.
By Leonardo Giordani - Updated on
The problem¶
P10 (*) Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
Example:
scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
Initial thoughts¶
The problem explicitly states "use the result of problem 09" (here) so I think it's time for me to learn how to make and import libraries. The problem itself seems to be rather simple to solve.
The recursive solution¶
Given the availability of the pack()
function from problem 09 the recursive solution just has to walk the packed list and convert each element (a list of equal elements) into a tuple. This is the tail recursive version
import utils.packer
def encode[A](l: List[A]):List[(Int, A)] = {
def _encode(res: List[(Int, A)], rem: List[List[A]]):List[(Int, A)] = rem match {
case Nil => res
case h::tail => _encode(res:::List((h.length, h.head)), tail)
}
_encode(List(), utils.packer.pack(l))
}
Note that I use the utils.packer.pack()
function imported from a package which contains the code developed for problem 09.
To obtain the availability of the pack()
function I first created a package. In Scala a package may be declared with the package
keyword, but the functions cannot be declared at module-level, they have to be converted into methods of an object. So the content of the utils.scala
file is
package utils
object packer {
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, r) = rem span { _ == rem.head }
_pack(res:::List(s), r)
}
}
_pack(List(), l)
}
}
In Scala, an object
is a singleton, and it is used without instancing it. So the pack()
method may be used in this file as packer.pack()
. This file is then compiled with the Scala compiler
$ scalac utils.scala
producing a utils
directory with the following files
$ ls utils
packer$$anonfun$1.class
packer.class
packer$.class
This package may be directly used by any file in the same directory (e.g. through scala program.scala
). If you plan to use it from another directory use the -classpath
switch to include the right directory where the utils
package may be found. (As an UNIX programmer, I hate single-dash Java long options, but they are here to stay)
Mapping¶
Mapping is, just like folding, a functional technique, because it applies a function to the elements of some collection. In Scala, the map()
function of the List
type produces a new list processing each element of the original list with the given function.
The function to process elements is very simple, since it has to pack together the length of the element (which is a list) and its head.
import utils.packer
def encode[A](l: List[A]):List[(Int, A)] = {
utils.packer.pack(l) map { e => (e.length, e.head) }
}
The expression e => (e.length, e.head)
is an anonymous function that maps an element into a tuple.
Final considerations¶
With this problem I met packages for the first time, learned how to compile and add paths through classpath. The functional solution introduced me to mapping.
Feedback¶
The GitHub issues page is the best place to submit corrections.
Part 10 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
Next articles
- 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