在 Kotlin 的不可变 LinkedList 中实现 Iterable
Implement Iterable in an immutable LinkedList in Kotlin
我正在尝试理解函数式编程范式,所以我在玩弄一个不可变的链表。我创建了一个带有一些实用函数的 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 吗?
请注意 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
扩展函数。
我正在尝试理解函数式编程范式,所以我在玩弄一个不可变的链表。我创建了一个带有一些实用函数的 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 吗?
请注意 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
扩展函数。