使用scanLeft打包符号

Question

99 scala problems有这个问题：

将列表元素的连续重复包装到子列表中。如果列表包含重复元素，则应将它们放在单独的子列表中。

Example:

scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

我已经了解了解决上述问题的尾递归方法。我想知道是否有办法使用scanLeft完成上述操作，其中中间结果是常用元素列表？

Answer 1

这是使用foldLeft的解决方案：

def pack[A](l:List[A]): List[List[A]] = l match {
  case head :: tail =>
    tail.foldLeft(List(List(head))) { (collector:List[List[A]], elem:A) =>
      if (collector.head.head == elem)
        (elem +: collector.head) +: collector.tail
      else
        List(elem) +: collector
    }.reverse
  case _ => List.empty
}

这仅适用于列表。更好的解决方案可能会使用MultiSets，尽管找到Scala实现很困难。

Answer 2

简洁但未经优化的版本可能如下所示：

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
for (i <-l.distinct) yield l.filter(_ == i)

res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a, 'a, 'a), List('b), List('c, 'c), List('d), List('e, 'e, 'e, 'e))

Answer 3

不，在这种情况下，scanLeft不是合适的方法。 scanLeft将生成一个结果集合，其中列表中的每个值都包含一个元素，加上您提供的初始值。因此，例如在scanLeft上使用List(1,2,3,4)将始终产生具有5个元素的结果

EG

scala> List(1,2,3,4).scanLeft(">"){case (last, x) => last + x}
res7: List[String] = List(>, >1, >12, >123, >1234)

Answer 4

scanLeft对于计算前缀和很有用，但问题并非如此。您可以尝试将其与其他调用结合使用，但我认为这不是解决问题的好方法。

foldLeft似乎对此任务更有用。

def pack[T](list: Seq[T]) = list.foldLeft(new ArrayBuffer[ArrayBuffer[T]])((ret, el) => {
    if (ret.isEmpty || ret.last.head != el)
      ret.append(new ArrayBuffer[T])
    ret.last.append(el)
    ret
  })

好奇的读者留下了两个简单的任务：

• 使用List prepending使其纯粹功能化
• 做出正确的退货类型

Answer 5

从Scala 2.13开始，List现在提供unfold构建器，可以与List::span结合使用：

// val list = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
List.unfold(list) {
  case Nil  => None
  case rest => Some(rest.span(_ == rest.head))
}
// List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

或者，加上Scala 2.13的Option#unless建设者：

List.unfold(list) {
  rest => Option.unless(rest.isEmpty)(rest.span(_ == rest.head))
}

---

细节：

• Unfold使用一个内部状态，在我们的情况下用list初始化以分割List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
• 在每次迭代时，我们span内部状态，以便找到包含相同符号的前缀：l.span(_ == l.head)，这是在第一次迭代l.span(_ == 'a)并给出(List('a, 'a, 'a, 'a),List('b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
• 正如unfold所期望的每次迭代一个元组的Option，其第一部分是要添加到正在构建的列表的新元素（这里是List('a, 'a, 'a, 'a)），其第二部分是内部状态的新值（这里是List('b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)），这个范围恰好适合那个要求。
• 我们继续迭代相同的步骤，直到内部列表为空，在这种情况下，我们告诉unfolding我们通过返回None完成。