Recursive definition of infinite sequence in Kotlin

Question

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.

Answer 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 { [email protected]() }
            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.