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转换,使其第一个项目保持不变,并将尾部从原始尾部延迟转换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被访问时才会被调用,也就是说,当第一个序列完成时.

现在,让我们写一个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秒内发出.