为什么这种可迭代实现会产生堆栈溢出?

Question

我正在尝试为链表实现一个可迭代对象。但是此实现会引发堆栈溢出错误。我在这里做错了什么？

可迭代实现抛出错误，甚至在我调用类上的任何函数之前。

我最初认为，这可能是因为对nodeValue和tailList使用了def而不是val。但这并没有解决问题。

我试图将迭代器更改为循环使用Int而不是LinkedList。我仍然收到同样的错误。 提前感谢！！

trait LinkedList extends Iterable[LinkedList]{
def nodeValue: Int
def tailList: LinkedList
}
class Node(val nodeValue: Int, val tailList: LinkedList) extends LinkedList {
override def iterator: Iterator[LinkedList] = Iterator
.iterate(this: LinkedList)(_.tailList)
.takeWhile(_ != Nil)
}
object Nil extends LinkedList {
def nodeValue= throw new IllegalAccessException("head of Nil")
def tailList = throw new IllegalAccessException("tail of Nil")
override def iterator: Iterator[LinkedList] = Iterator.empty
}
val singleLinkedList = new Node(1,Nil)
val chainedLinkedList = new Node(2,singleLinkedList)
//Printing this first Time
//chainedLinkedList.foreach(println)

输出：

java.lang.StackOverflowError
at scala.collection.AbstractIterable.<init>(LinkedListIterable.sc:50)
at scala.collection.AbstractSeq.<init>(LinkedListIterable.sc:37)
at scala.collection.mutable.AbstractSeq.<init>(LinkedListIterable.sc:44)
at scala.collection.mutable.StringBuilder.<init>(LinkedListIterable.sc:28)
at scala.collection.mutable.StringBuilder.<init>(LinkedListIterable.sc:45)
at scala.collection.mutable.StringBuilder.<init>(LinkedListIterable.sc:50)
at scala.collection.TraversableOnce.mkString(LinkedListIterable.sc:319)
at scala.collection.TraversableOnce.mkString$(LinkedListIterable.sc:318)
at #worksheet#.Node.mkString(LinkedListIterable.sc:6)
at scala.collection.TraversableLike.toString(LinkedListIterable.sc:596)
at scala.collection.TraversableLike.toString$(LinkedListIterable.sc:596)
at #worksheet#.Node.toString(LinkedListIterable.sc:6)
at java.lang.String.valueOf(LinkedListIterable.sc:2990)
at scala.collection.mutable.StringBuilder.append(LinkedListIterable.sc:196)
at scala.collection.TraversableOnce.$anonfun$addString$1(LinkedListIterable.sc:355)
at scala.collection.Iterator.foreach(LinkedListIterable.sc:925)
at scala.collection.Iterator.foreach$(LinkedListIterable.sc:925)
at scala.collection.AbstractIterator.foreach(LinkedListIterable.sc:1413)
at scala.collection.IterableLike.foreach(LinkedListIterable.sc:67)
at scala.collection.IterableLike.foreach$(LinkedListIterable.sc:66)
at #worksheet#.Node.foreach(LinkedListIterable.sc:6)
at scala.collection.TraversableOnce.addString(LinkedListIterable.sc:353)
at scala.collection.TraversableOnce.addString$(LinkedListIterable.sc:349)
at #worksheet#.Node.addString(LinkedListIterable.sc:6)
at scala.collection.TraversableOnce.mkString(LinkedListIterable.sc:319)
at scala.collection.TraversableOnce.mkString$(LinkedListIterable.sc:318)
at #worksheet#.Node.mkString(LinkedListIterable.sc:6)
at scala.collection.TraversableLike.toString(LinkedListIterable.sc:596)
at scala.collection.TraversableLike.toString$(LinkedListIterable.sc:596)
at #worksheet#.Node.toString(LinkedListIterable.sc:6)
at java.lang.String.valueOf(LinkedListIterable.sc:2990)
at scala.collection.mutable.StringBuilder.append(LinkedListIterable.sc:196)
at scala.collection.TraversableOnce.$anonfun$addString$1(LinkedListIterable.sc:355)
at scala.collection.Iterator.foreach(LinkedListIterable.sc:925)
Output exceeds cutoff limit.

更新：

正如@Dima提到的，迭代器迭代容器中的某些值，而不是容器本身。一旦清楚了这一点，我就修改了代码，运行良好，如下所示。

trait LinkedList extends Iterable[Int]{
val nodeValue: Int
val tailList: LinkedList
override def toString(): String = this.mkString(" -> ")
}
class Node(val nodeValue: Int, val tailList: LinkedList) extends LinkedList {
override def iterator: Iterator[Int] = Iterator
.iterate(this: LinkedList)(_.tailList)
.takeWhile(_ != Nil)
.map(_.nodeValue)
}
object Nil extends LinkedList {
lazy val nodeValue= throw new IllegalAccessException("head of Nil")
lazy val tailList = throw new IllegalAccessException("tail of Nil")
override def iterator: Iterator[Int] = Iterator.empty
}
val singleLinkedList = new Node(1,Nil)
val chainedLinkedList = new Node(2,singleLinkedList)
//Printing this first Time
chainedLinkedList.foreach(println)

Answer 1

问题是，通常Iterable.iterator迭代容器中的值，而不是实际的容器节点。

这里发生的情况是，当您在 REPL 中键入new Node(1, Nil)时，它会尝试打印出结果，并调用Node.toString，这是在Iterable上实现的，以循环访问整个容器，并将所有值转换为字符串。

因此，它调用您的iterator，获取next(它认为是什么(元素，并尝试将其转换为字符串。但是你的iterator返回的不是存储在节点中的值，而是节点本身，所以，当toString被调用时，它仍然是同一个Iterable.toString，最终调用相同的iterator，这将返回相同的节点，它会尝试转换为字符串......等。 无限递归。