kotlin - Kotlin中无限序列的递归定义

Question

我正在试验 Kotlin 序列，特别是更复杂的序列，它们不是对前一个值的简单计算。

我想定义的一个例子是所有素数的序列。

定义下一个素数的一种简单方法是下一个不能被序列中任何先前素数整除的整数。

在 Scala 中，这可以翻译为:

def primeStream(s: Stream[Int]): Stream[Int] = s.head #:: primeStream(s.tail filter(_ % s.head != 0))
val primes = primeStream(Stream.from(2))

// first 20 primes
primes.take(20).toList 

我无法将其翻译成 Kotlin。在 scala 中它可以工作，因为您可以传递返回序列的函数，该序列将被延迟评估，但在 Kotlin 中我不能这样做。

我在 Kotlin 中尝试过

fun primes(seq: Sequence<Int>):Sequence<Int> = sequenceOf(seq.first()) + primes(seq.drop(1).filter {it % seq.first() != 0})
val primes = primes(sequence(2) {it + 1})

primes.take(20).toList()

但这显然行不通，因为该函数会被立即计算并导致无限递归。

Answer 1

这里的关键是要实现一个Sequence转换，让它的第一个item保留下来，而tail是lazily从原来的Sequence转换而来的尾部到别的东西。也就是说，只有在请求项目时才进行转换。

首先，让我们实现惰性序列连接，它的行为类似于简单连接，但正确的操作数是惰性求值的:

public infix fun <T> Sequence<T>.lazyPlus(otherGenerator: () -> Sequence<T>) =
        object : Sequence<T> {
            private val thisIterator: Iterator<T> by lazy { this@lazyPlus.iterator() }
            private val otherIterator: Iterator<T> by lazy { otherGenerator().iterator() }

            override fun iterator() = object : Iterator<T> {
                override fun next(): T =
                        if (thisIterator.hasNext())
                            thisIterator.next()
                        else
                            otherIterator.next()

                override fun hasNext(): Boolean =
                        thisIterator.hasNext() || otherIterator.hasNext()
            }
        }

otherIterator 的惰性可以解决所有问题:otherGenerator 只有在访问 otherIterator 时才会被调用，也就是说，当第一个序列完成时.

现在，让我们编写埃拉托色尼筛的递归变体:

fun primesFilter(from: Sequence<Int>): Sequence<Int> = from.iterator().let {
        val current = it.next()
        sequenceOf(current) lazyPlus {
            primesFilter(it.asSequence().filter { it % current != 0 })
        }
    }

请注意，lazyPlus 允许我们在序列的尾部懒惰地再次递归调用 primesFilter。

之后，整个素数序列可以表示为

fun primes(): Sequence<Int> {
    fun primesFilter(from: Sequence<Int>): Sequence<Int> = from.iterator().let {
        val current = it.next()
        sequenceOf(current) lazyPlus {
            primesFilter(it.asSequence().filter { it % current != 0 })
        }
    }
    return primesFilter((2..Int.MAX_VALUE).asSequence())
}

---

虽然这种方法不是很快。评估 10,000 个素数需要几秒钟，但是，第 1000 个素数会在大约 0.1 秒内发出。