Как сложить итератор Scala и получить лениво вычисленную последовательность как результат?

Question

У меня есть итератор строк, где каждая строка может быть либо "H" (заголовок), либо "D" (подробно). Я хочу разделить этот итератор на блоки, где каждый блок начинается с одного заголовка и может содержать от 0 до многих деталей.

Я знаю, как решить эту проблему, загружая все в память. Например, код ниже:

Seq("H","D","D","D","H","D","H","H","D","D","H","D").toIterator
  .foldLeft(List[List[String]]())((acc, x) => x match {
    case "H" => List(x) :: acc
    case "D" => (x :: acc.head) :: acc.tail })
  .map(_.reverse)
  .reverse

возвращает 5 блоков - List(List(H, D, D, D), List(H, D), List(H), List(H, D, D), List(H, D)) - что я и хочу.

Однако вместо List[List[String]] в результате я хочу либо Iterator[List[String]], либо некоторую другую структуру, которая позволяет мне лениво оценивать результат, и не загружает весь ввод в память, если весь итератор в потребляемом , я хочу загрузить в память только блок, потребляемый за один раз (например: когда я вызываю iterator.next).

Как я могу изменить приведенный выше код для достижения желаемого результата?

РЕДАКТИРОВАТЬ: Мне это нужно, в частности, Scala 2.11, поскольку среда, которую я использую, придерживается его. Рад также принимать ответы для других версий.

Answer 1

Если вы используете Scala 2.13.x, тогда вы можете создать новый Iterator, развернув поверх оригинального Iterator.

import scala.collection.mutable.ListBuffer

val data = Seq("H","D","D","D","H","D","H","H","D","D","H","D").iterator

val rslt = Iterator.unfold(data.buffered){itr =>
  Option.when(itr.hasNext) {
    val lb = ListBuffer(itr.next())
    while (itr.hasNext && itr.head == "D")
      lb += itr.next()
    (lb.toList, itr)
  }
}

:

rslt.next()   //res0: List[String] = List(H, D, D, D)
rslt.next()   //res1: List[String] = List(H, D)
rslt.next()   //res2: List[String] = List(H)
rslt.next()   //res3: List[String] = List(H, D, D)
rslt.next()   //res4: List[String] = List(H, D)
rslt.hasNext  //res5: Boolean = false

Answer 2

Вот самая простая реализация, которую я смог найти (это обобщенно c и ленивый):

/** takes 'it' and groups consecutive elements 
 *  until next item that satisfy 'startGroup' predicate occures. 
 *  It returns Iterator[List[T]] and is lazy 
 *  (keeps in memory only last group, not whole 'it'). 
*/
def groupUsing[T](it:Iterator[T])(startGroup:T => Boolean):Iterator[List[T]] = {
  val sc = it.scanLeft(List.empty[T]) {
    (a,b) => if (startGroup(b)) b::Nil else b::a
  }

  (sc ++ Iterator(Nil)).sliding(2,1).collect { 
    case Seq(a,b) if a.length >= b.length => a.reverse
  }
}

используйте это так:

val exampleIt = Seq("H1","D1","D2","D3","H2","D4","H3","H4","D5","D6","H5","D7").toIterator
groupUsing(exampleIt)(_.startsWith("H"))
// H1 D1 D2 D3 / H2 D4 / H3 / H4 D5 D6 / H5 D7

вот спецификация:

X | GIVEN            | EXPECTED     |
O |                  |              | empty iterator
O | H                | H            | single header
O | D                | D            | single item (not header)
O | HD               | HD           |
O | HH               | H,H          | only headers
O | HHD              | H,HD         |
O | HDDDHD           | HDDD,HD      |
O | DDH              | DD,H         | heading D's have no Header as you can see.
O | HDDDHDHDD        | HDDD,HD,HDD  |

scalafiddle с тестами и дополнительными комментариями: https://scalafiddle.io/sf/q8xbQ9N/11

(если ответ полезен, проголосуйте, пожалуйста. Я потратил на это слишком много времени :) )

ВТОРАЯ РЕАЛИЗАЦИЯ:

Вы предлагаете версию , в которой не используется sliding. Вот оно, но у него есть свои проблемы, перечисленные ниже.

def groupUsing2[T >: Null](it:Iterator[T])(startGroup:T => Boolean):Iterator[List[T]] = {
  type TT = (List[T], List[T])
  val empty:TT = (Nil, Nil)
  //We need this ugly `++ Iterator(null)` to close last group.
  val sc = (it ++ Iterator(null)).scanLeft(empty) {
    (a,b) => if (b == null || startGroup(b)) (b::Nil, a._1) else (b::a._1, Nil)
  }

  sc.collect { 
    case (_, a) if a.nonEmpty => a.reverse
  }
}

Черты:

• (-) Работает только для T>:Null типов. Нам просто нужно добавить элемент, который закроет последнюю коллекцию в конце (null идеально, но он ограничивает наш тип).
• (~) он должен создать такое же количество tr sh, как и в предыдущей версии. Мы просто создаем кортежи на первом шаге вместо второго.
• (+) он не проверяет длину списка (и это, честно говоря, большой выигрыш).
• (+) В ядре это ответ Ивана Курченко, но без лишнего бокса.

Вот скаляшка: https://scalafiddle.io/sf/q8xbQ9N/11

Answer 3

Я думаю, что scanLeft операция может помочь в этом случае, если вы хотите использовать Scala 2.11 версию.

Я хотел бы найти следующее решение, но я боюсь, что оно выглядит более сложнее, чем оригинал:

def main(args: Array[String]): Unit = {
    sealed trait SequenceItem
    case class SequenceSymbol(value: String) extends SequenceItem
    case object Termination extends SequenceItem

    /**
      * _1 - HD sequence in progress
      * _2 - HD sequences which is ready
      */
    type ScanResult = (List[String], List[String])
    val init: ScanResult = Nil -> Nil

    val originalIterator: Iterator[SequenceItem] = Seq("H","D","D","D", "H","D", "H", "H","D","D", "H","D")
      .toIterator.map(SequenceSymbol)

    val iteratorWithTermination: Iterator[SequenceItem] = originalIterator ++ Seq(Termination).toIterator
    val result: Iterator[List[String]] = iteratorWithTermination
      .scanLeft(init) {
        case ((progress, _), SequenceSymbol("H")) =>  List("H") -> progress
        case ((progress, _), SequenceSymbol("D")) => ("D" :: progress) -> Nil
        case ((progress, _), Termination) => Nil -> progress
      }
      .collect {
        case (_, ready) if ready.nonEmpty => ready
      }
      .map(_.reverse)

    println(result.mkString(", "))
  }

Добавлены типы, например, для удобства чтения. Надеюсь, что это поможет!