Scala：查找列表中的所有链

Question

假设我有一个项目列表：

Seq(A, B, B, B, B, G, G, S, S, S, B, A, G)

我想找到所有链并得到它们的序列，如下所示：

Seq(Seq(A), Seq(B, B, B, B), Seq(G, G), Seq(S, S, S), Seq(B), Seq(A), Seq(G))

我想保持秩序，使用自定义比较函数来判断两个对象是否是"same"。我在想折叠或扫描可能是我需要的，但我很难想出确切的情况。我正在使用 Scala。

编辑：我已经修改了那个类似问题的答案以获得这个：

def collapse(input: Seq[Stmt]): Seq[Seq[Stmt]] = {
    val (l, r) = input.span(_.getClass == input.head.getClass)
    l :: collapse(r)
}

Answer 1

更清洁的解决方案：

  def pack[T](input: List[T]): List[List[T]] =
    input.foldRight(Nil : List[List[T]]) ((e, accu) => accu match {
      case Nil => List(List(e))
      case curList@(h :: t) if e == h => List(e) :: curList
      case curList@(h :: t) => List(List(e)) ::: curList
  })

没有使用任何库函数（丑陋）：

  def pack[T](input: List[T]): List[List[T]] = {
    def packWithPrevious(remaining: List[T])(previous: List[T]): List[List[T]] =
      remaining match {
        case List() => List(previous)
        case head :: tail =>
          val nextIter = packWithPrevious(tail)(_)
          previous match {
            case List() => nextIter(List(head))
            case prevHead :: _ =>
              if (head != prevHead)
                previous :: nextIter(List(head))
              else
                nextIter(head :: previous)
          }
      }
    packWithPrevious(input)(List())
  }

scala> val s = List('A', 'B', 'B', 'B', 'B', 'G', 'G', 'S', 'S', 'S', 'B', 'A', 'G')
s: List[Char] = List(A, B, B, B, B, G, G, S, S, S, B, A, G)

scala> pack(s)
res2: List[List[Char]] = List(List(A), List(B, B, B, B), List(G, G), List(S, S, S), List(B), List(A), List(G))

来源：https://github.com/izmailoff/scala-s-99/blob/master/src/main/scala/s99/p09/P09.scala

测试：https://github.com/izmailoff/scala-s-99/blob/master/src/test/scala/s99/p09/P09Suite.scala

Answer 2

考虑以下解决方案：

seq.foldLeft(List(List(seq.head))) { case (acc,item)=> 
  if(acc.head.head==item) (item::acc.head)::acc.tail else List(item)::acc  
}.reverse

seq 可能为空，所以：

seq.foldLeft(List(seq.headOption.toList)) { case (acc,item)=> 
  if(acc.head.head==item) (item::acc.head)::acc.tail else List(item)::acc  
}.reverse

Answer 3

我认为 groupBy 在这里会有帮助，但我的解决方案有点尴尬：

val seq = Seq("A", "B", "B", "B", "B", "G", "G", "S", "S", "S", "B", "A", "G")
val parts = {
  var lastKey: Option[(Int, String)] = None
  seq.groupBy(s => {
    lastKey = lastKey.map((p: (Int, String)) =>
      if (p._2.equalsIgnoreCase(s)) p else (p._1 + 1, s)) orElse Some((0, s))
    lastKey.get
  }).toSeq.sortBy(q => q._1).flatMap(q => q._2)
}

（使用 equalsIgnoreCase 作为比较函数的示例）

Answer 4

与现有答案类似，但我发现直接在 foldLeft 中使用部分函数作为干净的解决方案：

val s = Seq("A", "B", "B", "B", "B", "G", "G", "S", "S", "S", "B", "A", "G")

s.foldLeft(Seq[Seq[String]]()) {
  case (Seq(), item) => Seq(Seq(item))
  case (head::tail, item) if head.contains(item) => (item +: head) +: tail
  case (seq, item) => Seq(item) +: seq
}.reverse

res0: Seq[Seq[String]] = List(List(A), List(B, B, B, B), List(G, G), List(S, S, S), List(B), List(A), List(G))

Scala：查找列表中的所有链

Scala: find all chains in a list

functional-programming

scala

list

sequence

fold