使用Scala运行长度编码

Question

给定一些元素的列表,其中一些元素重复多次,我需要生成一个带有元组的新列表,其中每个元组包含元素在一行中重复的次数和元素本身.

例如,给定

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)

这是我此时的最佳尝试.我觉得我遗失了一些非常基本的东西,请帮我理解一下

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

在分析了问题所在之后,在我看来,在我递归调用时func(ys),ys没有足够的信息来计算元素的数量.说我们正在处理List(1,1,1,2).好的,所以, y是1,z现在1和(1::(2::Nil))是zs.按照上面的逻辑,下次调用会丢失1次被看到2次的事实.

问题可能是我没有以正确的方式思考问题.我想到的是"沿着列表走,直到你发现这个元素与前面的元素不同,此时,计算一个元素的出现次数并使其成为元组")

我认识到在上面的场景中(在我的代码中)问题是,当数字实际上是相同的(1,1)时,我们已经看到一个数字的事实并没有反映在任何地方.但是,鉴于我还没有准备好组成一个元组,请问在哪里可以做到

在回答这个问题时,请坚持案例结构.我意识到可能有其他更好,更清洁的方法来解决这个问题,我想更好地理解我在这里做错了什么

Answer 1

你走在正确的轨道上.问题是你不能在这里逐步建立结果列表 - 你必须从递归调用中获得的列表中删除头部并检查是否需要添加新的对或增加最后一个的计数一:

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

请注意y嵌套匹配模式中的反引号- 这是避免仅定义名为的新变量所必需的y.