lazySequence

Language Design
1

We need something like this:

private val fibSeq = lazySequence(1) { i, f ->
    f(i - 1) + f(i - 2)
}

fun fib(i: Int) =
    fibSeq[i - 2]

An example implementation:

interface IndexableSequence<T>: Sequence<T> {
    operator fun get(index: Int): T
}

fun <T> lazySequence(z: T, f: (Int, (Int) -> T) -> T): IndexableSequence<T> =
    object : IndexableSequence<T> {
        val map = mutableMapOf(0 to z)
        
        fun comp(iIn: Int): T {
            val i = max(0, iIn)
            return map[i] ?: f(i, ::comp).also { map[i] = it }
        }
            
        override fun get(index: Int) = comp(index)
        
        override fun iterator(): Iterator<T> =
        	object : Iterator<T> {
                override fun hasNext() = true
				
                private var i = 0
                
                override fun next(): T =
                	comp(i ++)
            }
    }

If something like that already exists, tell me. I don’t know every function inside of the Kotlin standard library.

2

I think you can use your implementation, is there something wrong with it?

Sequences are lazy, so probably the name lazySequence isn’t the best choice. Additionally from your example you don’t much need this object to be a sequence, you just need get(index: Int).

3

Well yes, I can use this but I was talking about having something similar in the stdlib.
I didn’t come up with a better name for it than lazySequence.
Yeah in this specific example, I don’t need it to be a sequence.

4

I don’t think you will find anything better in the stdlib. This is a very specialized util, I can’t think of too many use cases for it.

Also, I think it doesn’t have too much in common with sequences. It seems more like a lazy collection to me.

1 Like