My Avatar

Shilong ZHAO

[s 99] p11 modified run Length encoding

2020-06-24 00:00:00 +0200

In case you have any questions or suggestions, you can leave comments HERE . Thanks!

Modified run-length encoding.

Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N, E) terms. Example:

scala> encodeModified(List(‘a, ‘a, ‘a, ‘a, ‘b, ‘c, ‘c, ‘a, ‘a, ‘d, ‘e, ‘e, ‘e, ‘e)) res0: List[Any] = List((4,’a), ‘b, (2,’c), (2,’a), ‘d, (4,’e))

def pack[T](lists: List[List[T]], list: List[T]): List[List[T]] = list match {
    case Nil => lists
    case _ => {
        val (l, r) = list span (_ == list.head)
        pack(lists :+ l, r)

pack(List[List[Symbol]](), List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))

def encodeModified[T](list: List[T]): List[Any] = 
    pack(List[List[T]](), list).map(l => if (l.size > 1) (l.size, l.head) else l.head)

encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))

// encodeModified2, use the Either type
def encodeModified2[T](list: List[T]): List[Either[(Int, T), T]] = 
    pack(List[List[T]](), list).map(l => l match {
        case e if (e.size > 1) => Left((e.size, e.head))
        case e => Right(e.head)

encodeModified2(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))