Implement Iterable in an immutable LinkedList in Kotlin

Question

I'm trying to understand the functional programming paradigm so I'm playing around with an immutable linked list. I've created a Bag with some utility functions and now I want to iterate through the collection. I want to implement an Iterable:

sealed class Bag<out A> : Iterable<A> {
    companion object {
        fun <A> of(vararg aa: A): Bag<A> {
            val tail = aa.sliceArray(1 until aa.size)
            return if (aa.isEmpty()) Nil else Cons(aa[0], of(*tail))
        }

        /**
         * Returns the tail of the bag
         */
        fun <A> tail(bag: Bag<A>): Bag<A> =
            when (bag) {
                is Cons -> bag.tail
                is Nil -> throw IllegalArgumentException("Nil cannot have a tail")
            }

        /**
         * Add an item to the beginning
         */
        fun <A> add(bag: Bag<A>, elem: A): Bag<A> =
            Cons(elem, bag)

        fun <A> isEmpty(bag: Bag<A>): Boolean =
            when (bag) {
                is Nil -> true
                is Cons -> false
            }
    }

    class BagIterator<A> : Iterator<A> {

        override fun hasNext(): Boolean {
            TODO("Not yet implemented")
        }

        override fun next(): A {
            TODO("Not yet implemented")
        }

    }
}

object Nil : Bag<Nothing>() {
    override fun iterator(): Iterator<Nothing> =
        BagIterator()


}

data class Cons<out A>(val head: A, val tail: Bag<A>) : Bag<A>() {
    override fun iterator(): Iterator<A> =
        BagIterator()
}

Now I'm stuck with hasNext() and next() implementations. I'm not even sure if this approach works. Can I implement Iterable this way?

Answer 1

Note that an Iterator is a mutable thing. next must mutate the iterator's current state. Its signature does not allow you to "return a new Iterator with a different state". So if you wanted to do that, sad news for you :( This is because the way that iteration is supposed to happen is (this is roughly what a for loop translates to):

val iterator = something.iterator()
while (iterator.hasNext()) {
    val elem = iterator.next()
    ...
}

Now knowing that, we can store a var current: Bag<A>:

// in Bag<A>
class BagIterator<A>(var current: Bag<A>) : Iterator<A> {
    override fun hasNext(): Boolean = current !is Nil

    override fun next(): A {
        val curr = current
        return when (curr) {
            is Nil -> throw NoSuchElementException()
            is Cons -> curr.also {
                current = it.tail
            }.head
        }
    }
}

override fun iterator(): Iterator<A> = BagIterator(this)

And the Nil and Cons types can have empty bodies.

If you don't like this, blame the standard library designers :) You can always write your own Iterator<A> interface, but of course you can't use the for loop with your Bag if you do that. You can write your own forEach extension function though.