CODEWITHSUNDEEP
scalafor-looppattern-matching
user2336315
user2336315

Reputation: 16067

Scala - Pattern Matching and For loop issue

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 ?

Upvotes: 3

Views: 3760

Answers (5)

facebook-100001836197736
facebook-100001836197736

Reputation: 40

Another method is using map:

def decode[A](l: List[(Int, A)]): List[A] = {
  val l1: List[List[A]] = l map { e =>
    List.fill(e._1)(e._2)
  }
  l1.flatten
}

Upvotes: 0

maxmc
maxmc

Reputation: 4216

Here is a slightly modified version of Brian's answer. Decomposing the tuple makes the code even more readable:

def decode[A](xs: List[(Int, A)]) : List[A] = xs match {
   case Nil => Nil
   case (count, letter) :: xs => List.fill(count)(letter) ::: decode(xs)
}

Upvotes: 0

Brian
Brian

Reputation: 20285

The other answers are perfectly fine but I think generating the decoded lists with List.fill requires less syntax and is easier to understand compared to the for-yield expression.

def decode[A](xs: List[(Int, A)]) : List[A] = xs match {
   case Nil => Nil
   case x :: xs => List.fill(x._1)(x._2) ::: decode(xs)
}

Output:

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)

Upvotes: 2

Michał Kosmulski
Michał Kosmulski

Reputation: 10020

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)
  }
}

Upvotes: 4

Shadowlands
Shadowlands

Reputation: 15074

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

Upvotes: 4

Related Questions