3

99个scala问题有这个问题：

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

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 完成上述操作，其中中间结果是公共元素的列表？

4

5 回答 5

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 实现，但可能会使用更好的解决方案。

于 2012-12-12T17:38:48.607 回答
1

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

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))
于 2014-06-17T13:14:13.700 回答
1

开始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's Option#unlessbuilder 结合使用：

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

细节：

  • Unfold 使用一个内部状态，在我们的例子中用listto split初始化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)），该跨度完全符合该要求。
  • 我们不断迭代相同的步骤，直到内部列表为空，在这种情况下，我们unfold通过返回来告诉 ing 我们已经完成None。
于 2018-10-14T07:41:36.063 回答
0

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 前置使其纯功能化
  • 制作正确的返回类型
于 2012-12-12T17:34:11.267 回答
0

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

例如

scala> List(1,2,3,4).scanLeft(">"){case (last, x) => last + x}
res7: List[String] = List(>, >1, >12, >123, >1234)
于 2012-12-13T00:03:29.643 回答