3
\$\begingroup\$

I'm a long-time Java programmer, but recently I decided to give Kotlin a try. So far, I'm loving the language features, it feels much more expressive than what I'm used to. As practice, I wrote this function that produces a repeatable sequence of prime numbers (i.e. the sequence can be iterated multiple times, and will make use of results from past iterations to speed up future iterations). It feels pretty solid to me, but I'm wondering how it would look to a Kotlin veteran - are there language features that I'm not taking full advantage of, or conventions that I should be following?

One question I have in particular is regarding top-level function vs. subclass; here I chose to implement a top-level function primeSequence(): Sequence<Long> that returns an object, but I could have just about as easily implemented a class PrimeSequence : Sequence<Long>. Is there a good rule of thumb for when to use one or the other?

fun primeSequence(): Sequence<Long> = object: Sequence<Long> {
    private val knownPrimes: MutableList<Long> = arrayListOf(2L, 3L)

    private fun Long.isMultipleOf(n: Long) = (this%n == 0L)
    
    private fun Long.isPrime() = knownPrimes
            .takeWhile { it*it <= this }
            .none { this.isMultipleOf(it) }

    override fun iterator(): Iterator<Long> = object: Iterator<Long> {
        private var lastPrime: Long? = null

        override fun hasNext() = true

        override fun next(): Long {
            val nextPrime = when(val lastPrime = this.lastPrime) {
                null -> 2L
                2L -> 3L
                else -> {
                    if (knownPrimes.last() > lastPrime ) {
                        knownPrimes[knownPrimes.binarySearch(lastPrime) + 1]
                    } else {
                        val np = generateSequence(lastPrime+2) { it+2 }
                                .first { it.isPrime() }
                        knownPrimes.add(np)
                        np
                    }
                }
            }
            this.lastPrime = nextPrime
            return nextPrime
        }
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I don't like the idea of returning an inline object that inherits Sequence<Long> like this. Kotlin has several features to help you build stuff, including one for sequences.

Using the fantastic power of the sequence builder in Kotlin, which underneath the surface is using a suspendable function internally, we can yield numbers one by one instead of implementing an Iterator.

We can rewrite your code to use an outer object to keep the global state in, and then use a function to generate the sequence.

object Primes {
    private val knownPrimes: MutableList<Long> = mutableListOf(2L, 3L)
    private fun Long.isMultipleOf(n: Long) = (this % n == 0L)

    private fun Long.isPrime() = knownPrimes
            .takeWhile { it * it <= this }
            .none { this.isMultipleOf(it) }

    fun sequence(): Sequence<Long> {
        var lastPrime: Long? = null
        return sequence {
            while (true) {
                val nextPrime = when(val actualLastPrime = lastPrime) {
                    null -> 2L
                    2L -> 3L
                    else -> {
                        if (knownPrimes.last() > actualLastPrime) {
                            knownPrimes[knownPrimes.binarySearch(actualLastPrime) + 1]
                        } else {
                            val np = generateSequence(actualLastPrime + 2) { it+2 }
                                .first { it.isPrime() }
                            knownPrimes.add(np)
                            np
                        }
                    }
                }
                lastPrime = nextPrime
                yield(nextPrime)
            }
        }
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Nice, thanks for the tip! I haven't played around much with coroutines yet. Are they pretty widely used in Kotlin or is it more of a niche thing? \$\endgroup\$
    – Kevin K
    Dec 27, 2020 at 4:35
  • \$\begingroup\$ @KevinK That very much depends on the application, and how well the developer knows about them. However, you don't really need to know much about coroutines in order to use the sequence builder. \$\endgroup\$ Dec 27, 2020 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.