在 Kotlin 的不可变 LinkedList 中实现 Iterable

Question

我正在尝试理解函数式编程范式，所以我在玩弄一个不可变的链表。我创建了一个带有一些实用函数的 Bag，现在我想遍历该集合。我想实现一个 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()
}

现在我受困于 hasNext() 和 next() 实现。我什至不确定这种方法是否有效。我可以这样实现 Iterable 吗？

Answer 1

请注意 Iterator 是可变的。 next 必须改变迭代器的当前状态。它的签名不允许您“return 具有不同状态的新 Iterator”。所以如果你想这样做，对你来说是个坏消息:(这是因为迭代应该发生的方式是（这大致是 for 循环转换成的）：

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

现在知道了，我们可以存储一个 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)

并且 Nil 和 Cons 类型可以有空主体。

如果你不喜欢这个，责怪标准库设计者:)你总是可以写你自己的 Iterator<A> 接口，但是你当然不能在你的代码中使用 for 循环Bag 如果你这样做。不过，您可以编写自己的 forEach 扩展函数。

在 Kotlin 的不可变 LinkedList 中实现 Iterable

Implement Iterable in an immutable LinkedList in Kotlin

kotlin

functional-programming

immutability

immutable-collections