Why does this Iterator infinitely loop?

Question

I'm attempting to chain Iterators:

var it = Iterator(1)
it.next
it = Iterator(2) ++ it
it.next
it.hasNext

This infinitely loops on the hasNext as you can see here: https://scastie.scala-lang.org/qbHIVfsFSNO5OYmT4pkutA

If you run this and inspect the stack while it's infinitely looping, it's looping in the concetentation:

        at scala.collection.Iterator$ConcatIterator.merge(Iterator.scala:213)
        at scala.collection.Iterator$ConcatIterator.advance(Iterator.scala:197)
        at scala.collection.Iterator$ConcatIterator.hasNext(Iterator.scala:227)

(This stack is from Scala 2.12.11, but the Scastie link shows same behavior in 2.13.2).

I know that one should never use an iterator after calling a method on it, but this appears like it would work to me. Using the var to point to the "current" Iterator and changing it to point to a new Iterator that appends the remainder of the previous one.

The following slight modification does work:

var it = Iterator(1)
it.next
val x = it
it = Iterator(2) ++ x
it.next
it.hasNext

Scastie link: https://scastie.scala-lang.org/1X0jslb8T3WIFLHamspYAg

This suggests to me that somehow the broken version is creating an Iterator that is appending itself. Any hints as to what is going on here?

No disagreement here. I'm benchmarking this vs. functionally pure code and will pick the latter if possible. Only issue is this is performance critical code so it's a reasonable candidate for mutation under the hood if it runs really fast. Amazing how much confusion there can be in 5 lines of imperative code though... — Jack Koenig, May 15 '20 at 23:14

score 7 · Accepted Answer · answered May 15 '20 at 23:16

7

The argument to the ++ method of Iterator is passed by name. ++ returns a new Iterator that just stores a function which returns it, but doesn't call it until you try to use the appended elements.

So ++ tries to evaluate the argument only when you call it.hasNext, but by that time it is already redefined as the result of ++, so it ends up trying to append it to itself.

In other words vars and by-name parameters don't work together.

So don't reassign Iterator method results to the same variable and give them new names instead:

val it = Iterator(1)
it.next
val it2 = Iterator(2) ++ it
it2.next
it2.hasNext

answered May 15 '20 at 23:16

Kolmar

14,086
1
22
25

1

I had no idea that by-name would capture the actual `var` as opposed to just the object it's pointing to but it makes sense. Thanks! – Jack Koenig May 15 '20 at 23:22
4

@JackKoenig Yes, pass by-name creates a closure, and closures do see changes to `var`s in scope. Consider that for example: `def make(): () => Int = { var i = 0; def result() = { i += 1; i }; result }; val f = make(); println(f(), f(), f())` will print `(1,2,3)` – Kolmar May 15 '20 at 23:32

Why does this Iterator infinitely loop?

1 Answers1