Recursive definition of infinite sequence in Kotli

问题:

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.

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 

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.

In Kotlin I tried

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.

回答1:

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()
            }
        }

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

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 })
        }
    }

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())
}

---

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.

回答2:

You can place the Sequence<Int> concatenation inside of a Sequence<Sequence<Int>> generator and then flatten it to a Sequence<Int> again:

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 })

Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

It seems a bit slow though. What you probably want is to cache each result in a list and build off of it instead of recalculating the primes recursively. e.g.:

fun primes() = with(arrayListOf(2, 3)) {
    asSequence() + sequence(last() + 2) { it + 2 }
            .filter { all { prime -> it % prime != 0 } }
            .map { it.apply { add(it) } }
}

回答3:

My current answer is not to use a recursive function. I can get still get an infinite sequence of primes by modelling the sequence as a pair of values with the first the prime number and the second the current filtered sequence. I then apply the map to only select the first element.

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}