为什么我的 `zipAll` 会出现 OutOfMemoryError 错误以及如何修复它？

Question

我正在尝试编写一个好的zipAll函数——不像 Scala 的函数，而是像 C++ 的函数zip_view：只是 Kotlin 的 zip，其中并行迭代任意数量的序列，长度等于最短。

我想出了：

fun <T> zipAll(vararg seq: Sequence<T>): Sequence<List<T>> {
    return sequence { 
        while (seq.all { it.iterator().hasNext() }) 
            yield(seq.map { it.take(1).first() }) 
    }
}

fun main() {
    val s = sequenceOf(1,2,3)
    val s2 = sequenceOf(3,4,5,6)    
    println(zipAll(s, s2).toList())
}

但Kotlin Playground 给出了（编辑：使用我本地 IntelliJ Idea 中更完整的堆栈跟踪）

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3512)
    at java.base/java.util.Arrays.copyOf(Arrays.java:3481)
    at java.base/java.util.ArrayList.grow(ArrayList.java:237)
    at java.base/java.util.ArrayList.grow(ArrayList.java:244)
    at java.base/java.util.ArrayList.add(ArrayList.java:454)
    at java.base/java.util.ArrayList.add(ArrayList.java:467)
    at kotlin.sequences.SequencesKt___SequencesKt.toList(_Sequences.kt:816)

我究竟做错了什么？

Answer 1

Sequence.iterator()不一定为 的其余部分创建迭代器Sequence。对于可以多次迭代的序列（例如使用 创建的序列）sequenceOf，iterator会为您提供一个全新的迭代器，从序列的开头开始。对于不能多次迭代的序列，iterator第二次调用将抛出异常。

因此，while条件永远不会为假，最终会创建一个无限序列。

您应该跟踪每个序列的迭代器：

fun <T> zipAll(vararg seq: Sequence<T>): Sequence<List<T>> {
    return sequence {
        val iterators = seq.map { it.iterator() }
        while (iterators.all { it.hasNext() })
            yield(iterators.map { it.next() })
    }
}