Kotlin中无限序列的递归定义
我正在试验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()
但是这显然不起作用，因为函数是直接计算的，并导致无限递归。
这里的关键是要实现一个Sequence转换，使其第一个项目保持不变，并将尾部从原始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器的懒惰完成所有的技巧：只有在访问otherIterator时，也就是第一个序列完成时，才会调用otherIterator 。
现在，让我们写一个Eratosthenes筛的递归变体：
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秒内发射。
您可以将Sequence<Int>串联放置在Sequence<Int> Sequence<Sequence<Int>>生成器内，然后再次将其平坦化为Sequence<Int> ：
fun primes(seq: Sequence<Int>): Sequence<Int> = sequence { seq.take(1) + primes(seq.drop(1).filter { it % seq.first() != 0 }) }.flatMap { it } val primes = primes(sequence(2) { it + 1 })
输出： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
这似乎有点慢。 你可能想要的是将每个结果缓存在一个列表中，并且不是以递归方式重新计算素数。 例如：
fun primes() = with(arrayListOf(2, 3)) { asSequence() + sequence(last() + 2) { it + 2 } .filter { all { prime -> it % prime != 0 } } .map { it.apply { add(it) } } }
我目前的答案是不使用递归函数。 通过将序列建模为一对数值，我可以得到无限的素数序列，其中第一个是质数，第二个是当前的过滤序列。 然后我应用地图来只选择第一个元素。
val primes = sequence(2 to sequence(3) {it + 2}) { val currSeq = it.second val nextPrime = currSeq.first() nextPrime to currSeq.filter { it % nextPrime != 0} }.map {it.first}