Kotlin中无限序列的递归定义 [英] Recursive definition of infinite sequence in Kotlin

问题描述

我正在试验Kotlin序列，尤其是较复杂的序列，这些序列不是对先前值的简单计算.

I'm experimenting with the Kotlin sequences and particular the more complicated ones that are not simple calculations on the previous value.

我想定义的一个例子是所有质数的序列.

One example I'd like to define is a sequence of all prime numbers.

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

An easy way to define the next prime is the next integer that is not divisible by any of the previous primes in the sequence.

在Scala中，这可以翻译为:

In Scala this can be translated to:

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中无法做到这一点.

I'm having trouble translating this to Kotlin. In scala it works because you can pass function that returns a sequence that will be lazily evaluated but I can't do the same in 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()

但这显然不起作用，因为该函数会立即求值并导致无限递归.

But that obviously doesn't work because the function is evaluated straight away and leads to an infinite recursion.

推荐答案

此处的关键点是实现Sequence转换，以便保留其第一项，并且从 lazily 转换尾部.原始的Sequence尾巴指向其他位置.也就是说，只有在请求商品时才进行转换.

The key point here is to implement a Sequence transformation so that its first item remains and the tail is lazily transformed from the original Sequence tail to something else. That is, the transformation is done only when the item is requested.

首先，让我们实现延迟序列串联，其行为类似于简单串联，但是对正确的操作数进行延迟计算:

First, let's implement lazy sequence concatenation, which behaves like simple concatenation but the right operand is evaluated lazily:

public infix fun <T> Sequence<T>.lazyPlus(otherGenerator: () -> Sequence<T>) =
        object : Sequence<T> {
            private val thisIterator: Iterator<T> by lazy { [e-mail]() }
            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时，即第一个序列结束时，才会调用otherGenerator.

Laziness of otherIterator does all the trick: otherGenerator will be called only when otherIterator is accessed, that is, when the first sequence finishes.

现在，让我们写一个Eratosthenes筛子的递归变体:

Now, let's write a recursive variant of the sieve of 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.

Note that lazyPlus allowed us to lazily make another recursive call of primesFilter in the tail of the sequence.

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

After that, the whole sequence of primes can be expressed as

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秒内发出.

---

Though this approach isn't very fast. Evaluation of 10,000 primes takes a few seconds, however, the 1000th prime is emitted in about 0.1 second.

这篇关于Kotlin中无限序列的递归定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！