list - 使用 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) 时，我们已经看到一个数字的事实不会在任何地方反射(reflect)出来。但是，鉴于我还没有准备好组成一个元组，请问在哪里可以做到这一点

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

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 的新变量是必要的。