Как сгруппировать повторяющуюся последовательность переменной длины в Scala

У меня есть набор целых чисел, которые повторяются в шаблоне:

val repeatingSequence = List(1,2,3,1,2,3,4,1,2,1,2,3,4,5)

Я хотел бы разделить этот список, когда шаблон повторяется; в этом случае, когда последовательность возвращается к 1:

val groupedBySequence = List(List(1,2,3), List(1,2,3,4), List(1,2), List(1,2,3,4,5))

Обратите внимание, что я группирую, когда последовательность возвращается к 1, но последовательность может быть произвольной длины. Мой коллега и я решили эту проблему, добавив дополнительный метод под названием «groupWhen».

class IteratorW[A](itr: Iterator[A]) {
  def groupWhen(fn: A => Boolean): Iterator[Seq[A]] = {
    val bitr = itr.buffered
    new Iterator[Seq[A]] {
      override def hasNext = bitr.hasNext
      override def next = {
        val xs = collection.mutable.ListBuffer(bitr.next)
        while (bitr.hasNext && !fn(bitr.head)) xs += bitr.next
        xs.toSeq
      }
    }
  }
}
implicit def ToIteratorW[A](itr: Iterator[A]): IteratorW[A] = new IteratorW(itr)

> repeatingSequence.iterator.groupWhen(_ == 1).toSeq
List(List(1,2,3), List(1,2,3,4), List(1,2), List(1,2,3,4,5))

Однако мы оба чувствуем, что в библиотеке коллекций скрывается более элегантное решение.


scala scala-collections
person Matt Hughes    schedule 23.07.2011    source источник
comment
Какую версию Scala вы используете?   -  person erisco    schedule 23.07.2011
comment
Каким должен быть результат List(2).iterator.groupWhen(_ == 1)?   -  person Thomas Jung    schedule 23.07.2011
comment
Томас Юнг - я думаю, что это должно вернуть пустой список. В этом примере нет группы, начинающейся с 1, поэтому ее следует отбросить.   -  person Matt Hughes    schedule 24.07.2011

Ответы (3)


arrow_upward
9
arrow_downward

Учитывая итератор itr, это поможет:

val head = iter.next()
val out = (
  Iterator continually {iter takeWhile (_ != head)}
  takeWhile {!_.isEmpty}
  map {head :: _.toList}
).toList
person Kevin Wright    schedule 23.07.2011
comment
Хороший способ борьбы с takeWhile с потерей значения заголовка (issues.scala-lang.org/browse /SI-3581). И если вы отбросите окончательный toList, он будет работать на бесконечном итераторе. - person mpilquist; 23.07.2011
comment
Что, если iter.hasNext == false? - person huynhjl; 23.07.2011
comment
huynhjl - действительно, для этого вам понадобится явная проверка, хотя я не хотел отвлекать от основной логики :) - person Kevin Wright; 24.07.2011

arrow_upward
2
arrow_downward

Как известно, фолд может все... ;)

  val rs = List(1,2,3,1,2,3,4,1,2,1,2,3,4,5)
  val res = (rs++List(1)).foldLeft((List[List[Int]](),List[Int]()))((acc,e) => acc match {
    case (res,subl) => {
      if (e == 1) ((subl.reverse)::res,1::Nil) else (res, e::subl)
    }
  })
  println(res._1.reverse.tail)

Пожалуйста, рассматривайте это как заявку на запутанный конкурс Scala, а не как реальный ответ.

person Kim Stebel    schedule 23.07.2011

arrow_upward
2
arrow_downward

Вот не совсем элегантное решение, которое я придумал, используя span:

def groupWhen[A](fn: A => Boolean)(xs: List[A]): List[List[A]] = {
  xs.span(!fn(_)) match {
    case (Nil, Nil) => Nil
    case (Nil, z::zs) => groupWhen(fn)(zs) match {
      case ys::yss => (z::ys) :: yss
      case Nil => List(List(z))
    }
    case (ys, zs) => ys :: groupWhen(fn)(zs)
  }
}

scala> groupWhen[Int](_==1)(List(1,2,3,1,2,3,4,1,2,3,4,5))
res39: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 3, 4), List(1, 2, 3, 4, 5))

scala> groupWhen[Int](_==1)(List(5,4,3,2,1,2,3,1,2,3,4,1,2,3,4,5))
res40: List[List[Int]] = List(List(5, 4, 3, 2), List(1, 2, 3), List(1, 2, 3, 4), List(1, 2, 3, 4, 5))
person Nate Nystrom    schedule 23.07.2011