Scala - Pattern Matching and For loop issue

Question

I'm trying to solve the problem 12 of S-99: Ninety-Nine Scala Problems

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)

I was trying to pattern match the element in the list and then use a for loop to concatenate the char but I've got the following compilation error on line 5 :

type mismatch;  found   : scala.collection.immutable.IndexedSeq[List[A]]  required: List[A]

---

1 def decode[A](xs: List[(Int, A)]) : List[A] = xs match {
2     case Nil => Nil
3     case x :: xs => {
4                    for {
5                       i <- 1 to x._1
6                    }  yield (x._2) :: decode(xs)
7                   }
8 }

Sorry but I begin Scala. Could someone explain why this is happening and how to solve it ?

Answer 1

You are quite close - just a couple of problems. Here is a fixed version I came up with:

def decode[A](xs: List[(Int, A)]) : List[A] = xs match {
   case Nil => Nil
   case x :: xs => (for {
                       i <- 1 to x._1
                    } yield (x._2)).toList ::: decode(xs)
}

The first - and probably most important - thing is the extra parentheses around the for-yield. Without this, you are trying to yield (x._2) :: decode(xs), rather than just (x._2) (to make up for that, the {} around the whole case can be omitted).

Next, the for-yield results in an IndexedSeq rather than a List, so I forced a conversion to List (you could handle this in various ways, this was merely the most expedient).

Finally, concatenating to the List resulting from decode(xs) requires the ::: operator (you can also use ++) rather than :: (which prepends a single entry, not a sub-list).

Answer 2

The main issue is the operator you use for concatenating lists - :: is used only to prepend a single element to a list, so in your code you are trying to prepend the result of the yield (which is itself a sequence) to a List[A] and get type incompatibility as a result. Here is a modified version that will work - it uses operator ++: which can be used to join two sequences together. I also moved the yield to a separate statement, otherwise you would need parentheses around the yield so that ++: works on the complete result of the yield and not on each element (which would again not compile due to types not matching).

def decode[A](xs: List[(Int, A)]) : List[A] = xs match {
  case Nil => Nil
  case x :: xs => {
    val repeatedElems = for {
      i <- 1 to x._1
    }  yield (x._2)
    repeatedElems ++: decode(xs)
  }
}