如何折叠 Scala 迭代器并获得延迟计算的序列作为结果？

Question

我有一个字符串迭代器，其中每个字符串可以是"H"(header) 或"D"(detail)。我想将此迭代器拆分为多个块，其中每个块以一个标题开头，并且可以有 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

这是我能找到的最简单的实现（它是通用且懒惰的）：

/** 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. 在这里，但它有下面列出的自己的问题。

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  |

特性：

• (-) 它仅适用于T>:Null类型。我们只需要添加将在最后关闭最后一个集合的元素（null 是完美的，但它限制了我们的类型）。
• (~) 它应该创建与以前版本相同数量的 trsh。我们只是在第一步而不是第二步中创建元组。
• (+) 它不检查 List 的长度（老实说这是很大的收获）。
• (+) 核心是 Ivan Kurchenko 的回答，但没有额外的拳击。

这是 scalafiddle：https ://scalafiddle.io/sf/q8xbQ9N/11