Posted in Kotlin

Kotlin Sequences

Kotlin sequences are an ordered collection of elements that are potentially unbounded in size. The values are evaluated lazily. They are great at representing collection where the size isn’t known in advance like reading lines from a file. Java 8 and Scala both have the concept of streams which is the same idea, Kotlin has chosen to use sequence to avoid naming conflicts when running on a Java 8 jvm.

The api documentation is here

I haven’t seen a lot of example usage so here a couple of examples that I am keeping for reference.

Simple Arithmetic and Geometric Progressions

val nums = generateSequence(1) {it + 1} // sequence starting at 1 incrementing by 1
val powersOf2 = generateSequence(1) {it * 2} // sequence of powers of 2

// Take creates a new sequence (so values are not yet evaluated)
// toList() causes the 10 elements in the sequence to be evaluated
println(nums.take(10).toList()) // prints [1,2,3,4,5,6,7,8,9,10]

Map and Filters

Map, fold and filter functions can be applied like for any other collection and are only evaluated when the value is evaluated

val squares = generateSequence(1) {it + 1}.map {it * it}
val oddSquares = squares.filter {it % 2 != 0}

println(oddSquares.take(5).toList()) // prints [1, 9, 25, 49, 81]

Mapping Java Readers to a Sequence

val reader:java.io.BufferedReader = ...
val lines = generateSequence {reader.readLine()}.takeWhile {it != null}

Gives you a nice little collection that you can you forEach, map or fold operations on but you don’t have to read the whole file into memory upfront.

Advanced Examples

Kotlin lazy evaluation of values is a bit limited in that evaluation can only be done on the previous element in the sequence. It’s fine if the next element is a simple computation on the previous element but can be quite difficult if you need to know a number of previous elements.

Fibonacci Sequence

The Fibonacci numbers is a sequence of numbers where the next value is found by adding together the previous to values. An easy way to do this in Kotlin is to start with a sequence of Pairs that represent the two previous values so its available to next element calculation. Then apply a map to the sequence to only have the first element in each Pair as the resulting sequence.

val fibonacci = generateSequence(1 to 1) {it.second to it.first+it.second}.map {it.first}
println(fibonacci.take(10).toList()) // prints [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Primes

A prime is defined as a number that is only divisible by 1 and itself (not including 1) and all numbers can be defined as a product of their primes.

To implement this as a sequence of primes a clean way is to define the next prime as the next integer that is not divisible by any of the previous numbers in the stream. This could be solved using the Pairs approach as the fibonacci example but here is alternative recursive style approach.

Option 1 – Pairs Approach

val primes = generateSequence(2 to generateSequence(3) {it + 2}) {
  val currSeq = it.second.iterator()
  val nextPrime = currSeq.next()
  nextPrime to currSeq.asSequence().filter { it % nextPrime != 0}
}.map {it.first}
println(primes.take(10).toList()) // prints [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Option 2 – Recursive Approach

The recursive approach might seem a bit overkill for this example but it does provide a useful lazy plus operator for other problems.

Define a plus operator on the Sequence that allows adding a sequence generator function that lazily evaluated. This allows the calculation for the next element of the sequence to be recursively defined without being eagerly evaluated. This function is not specific to the primes example and can be used for any similar case.

public operator fun <T> Sequence<T>.plus(otherGenerator: () -> Sequence<T>) =
  object : Sequence<T> {
    private val thisIterator: Iterator<T> by lazy { this@plus.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()
    }
  }

So now to get all primes you can define a recursively defined sequence where the a number is prime if it is not divisible by any previous prime in the sequence.

fun primesFilter(from: Sequence<Int>): Sequence<Int> = from.iterator().let {
  val current = it.next()
  sequenceOf(current) + { primesFilter(it.asSequence().filter { it % current != 0 }) }
}

val primes = primesFilter(generateSequence(2) {it + 1})
println(primes.take(10).toList()) // prints [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s