Run length encoding using Scala

Question

Given a list of elements of which some are repeated multiple times, i need to produce a new list with tuples, where each tuple contains number of times an element is repeated in a row and an element itself.

For example, given

println(func(List()))              // should be empty list
println(func(List(1, 1)))          // (2,1) <- 1 is repeated 2 times
println(func(List(1, 1, 2, 1)))    // (2,1)(1,2)(1,1)

This is my best attempt at this point. I feel that i am missing something very basic, please help me understand what

  def func[X](xs: List[X]): List[(Int, X)] = xs match {
    case Nil => Nil
    case y :: ys   => ys match {
      case Nil     => (1, y) :: Nil
      case z :: zs => if (y != z) (ys.prefixLength(_ == ys.head), y) :: func(ys) 
                      else func(ys)
    }
  }

After analyzing what the problem is, it seems to me that at the point when i recursively call func(ys), ys does not have enough information to figure out the count of elements. Say we're dealing with List(1,1,1,2). Ok, so, y is 1, z is 1 and (1::(2::Nil)) is zs. Following my logic above, the fact that 1 was seen 2 times is lost for the next call.

The problem may be that i am not thinking about the problem the right way. What i have in mind is "go along the list until you find that this element is not the same as a previous elements, at which point, count the number of occurrences of an element and make it into the tuple")

I recognize that in the above scenario (in my code) the problem is that when numbers are in fact the same (1,1) the fact that we already saw a number is not reflected anywhere. But where can this be done please, given that i am not yet ready to compose a tuple

In answering this question, please stick to case structure. I realize that there maybe other better, cleaner ways to address this problem, i would like to better understand what i am doing wrong here

Answer 1

You're on the right track. The problem is that you can't just incrementally build the result list here—you'll have to pull the head off the list you get from the recursive call and check whether you need to add a new pair or increment the count of the last one:

def func[X](xs: List[X]): List[(Int, X)] = xs match {
  case Nil => Nil
  case y :: ys => func(ys) match {
    case (c, `y`) :: rest => (c + 1, y) :: rest
    case             rest => (    1, y) :: rest
  }
}

Note the backticks around y in the nested match pattern—this is necessary to avoid just defining a new variable named y.

Answer 2

Here's a simpler solution using span:

def runLength[T](xs: List[T]): List[(Int, T)] = xs match {
  case Nil => List()
  case x :: l => {
    val (front, back) = l.span(_ == x)
    (front.length + 1, x) :: runLength(back)
  }
}