Iterators

An iterator is not a collection, but rather a way to access the elements of a collection one by one. The two basic operations on an iterator it are next and hasNext. A call to it.next() will return the next element of the iterator and advance the state of the iterator. Calling next again on the same iterator will then yield the element one beyond the one returned previously. If there are no more elements to return, a call to next will throw a NoSuchElementException. You can find out whether there are more elements to return using Iterator’s hasNext method.

The most straightforward way to “step through” all the elements returned by an iterator it uses a while-loop:

while (it.hasNext)
  println(it.next())

while it.hasNext do
  println(it.next())

Iterators in Scala also provide analogues of most of the methods that you find in the Iterable and Seq classes. For instance, they provide a foreach method which executes a given procedure on each element returned by an iterator. Using foreach, the loop above could be abbreviated to:

it.foreach(println)

As always, for-expressions can be used as an alternate syntax for expressions involving foreach, map, withFilter, and flatMap, so yet another way to print all elements returned by an iterator would be:

for (elem <- it) println(elem)

for elem <- it do println(elem)

There’s an important difference between the foreach method on iterators and the same method on iterable collections: When called on an iterator, foreach will leave the iterator at its end when it is done. So calling next again on the same iterator will fail with a NoSuchElementException. By contrast, when called on a collection, foreach leaves the number of elements in the collection unchanged (unless the passed function adds or removes elements, but this is discouraged, because it may lead to surprising results).

The other operations that Iterator has in common with Iterable have the same property. For instance, iterators provide a map method, which returns a new iterator:

scala> val it = Iterator("a", "number", "of", "words")
val it: Iterator[java.lang.String] = <iterator>

scala> it.map(_.length)
val res1: Iterator[Int] = <iterator>

scala> it.hasNext
val res2: Boolean = true

scala> res1.foreach(println)
1
6
2
5

scala> it.hasNext
val res4: Boolean = false

As you can see, after the call to it.map, the it iterator hasn’t advanced to its end, but traversing the iterator resulting from the call to res1.foreach also traverses it and advances it to its end.

Another example is the dropWhile method, which can be used to find the first elements of an iterator that has a certain property. For instance, to find the first word in the iterator above that has at least two characters you could write:

scala> val it = Iterator("a", "number", "of", "words")
val it: Iterator[java.lang.String] = <iterator>

scala> it.dropWhile(_.length < 2)
val res4: Iterator[java.lang.String] = <iterator>

scala> res4.next()
val res5: java.lang.String = number

Note again that it was changed by the call to dropWhile: it now points to the second word “number” in the list. In fact, it and the result res4 returned by dropWhile will return exactly the same sequence of elements.

One way to circumvent this behavior is to duplicate the underlying iterator instead of calling methods on it directly. The two iterators that result will each return exactly the same elements as the underlying iterator it:

scala> val (words, ns) = Iterator("a", "number", "of", "words").duplicate
val words: Iterator[String] = <iterator>
val ns: Iterator[String] = <iterator>

scala> val shorts = words.filter(_.length < 3).toList
val shorts: List[String] = List(a, of)

scala> val count = ns.map(_.length).sum
val count: Int = 14

The two iterators work independently: advancing one does not affect the other, so that each can be destructively modified by invoking arbitrary methods. This creates the illusion of iterating over the elements twice, but the effect is achieved through internal buffering. As usual, the underlying iterator it cannot be used directly and must be discarded.

In summary, iterators behave like collections if one never accesses an iterator again after invoking a method on it. The Scala collection libraries make this explicit with an abstraction IterableOnce, which is a common superclass of Iterable and Iterator. IterableOnce[A] only has two methods: iterator: Iterator[A] and knownSize: Int. If an IterableOnce object is in fact an Iterator, its iterator operation always returns itself, in its current state, but if it is an Iterable, its iterator operation always return a new Iterator. A common use case of IterableOnce is as an argument type for methods that can take either an iterator or a collection as argument. An example is the appending method concat in class Iterable. It takes an IterableOnce parameter, so you can append elements coming from either an iterator or a collection.

All operations on iterators are summarized below.

Operations in class Iterator

Laziness

Unlike operations directly on a concrete collection like List, operations on Iterator are lazy.

A lazy operation does not immediately compute all of its results. Instead, it computes the results as they are individually requested.

So the expression (1 to 10).iterator.map(println) would not print anything to the screen. The map method in this case doesn’t apply its argument function to the values in the range, it returns a new Iterator that will do this as each one is requested. Adding .toList to the end of that expression will actually print the elements.

A consequence of this is that a method like map or filter won’t necessarily apply its argument function to all the input elements. The expression (1 to 10).iterator.map(println).take(5).toList would only print the values 1 to 5, for instance, since those are only ones that will be requested from the Iterator returned by map.

This is one of the reasons why it’s important to only use pure functions as arguments to map, filter, fold and similar methods. Remember, a pure function has no side-effects, so one would not normally use println in a map. println is used to demonstrate laziness as it’s not normally visible with pure functions.

Laziness is still valuable, despite often not being visible, as it can prevent unneeded computations from happening, and can allow for working with infinite sequences, like so:

def zipWithIndex[A](i: Iterator[A]): Iterator[(Int, A)] =
  Iterator.from(0).zip(i)

Buffered iterators

Sometimes you want an iterator that can “look ahead”, so that you can inspect the next element to be returned without advancing past that element. Consider for instance, the task to skip leading empty strings from an iterator that returns a sequence of strings. You might be tempted to write the following

def skipEmptyWordsNOT(it: Iterator[String]) =
  while (it.next().isEmpty) {}

def skipEmptyWordsNOT(it: Iterator[String]) =
  while it.next().isEmpty do ()

But looking at this code more closely, it’s clear that this is wrong: The code will indeed skip leading empty strings, but it will also advance it past the first non-empty string!

The solution to this problem is to use a buffered iterator. Class BufferedIterator is a subclass of Iterator, which provides one extra method, head. Calling head on a buffered iterator will return its first element but will not advance the iterator. Using a buffered iterator, skipping empty words can be written as follows.

def skipEmptyWords(it: BufferedIterator[String]) =
  while (it.head.isEmpty) { it.next() }

def skipEmptyWords(it: BufferedIterator[String]) =
  while it.head.isEmpty do it.next()

Every iterator can be converted to a buffered iterator by calling its buffered method. Here’s an example:

scala> val it = Iterator(1, 2, 3, 4)
val it: Iterator[Int] = <iterator>

scala> val bit = it.buffered
val bit: scala.collection.BufferedIterator[Int] = <iterator>

scala> bit.head
val res10: Int = 1

scala> bit.next()
val res11: Int = 1

scala> bit.next()
val res12: Int = 2

scala> bit.headOption
val res13: Option[Int] = Some(3)

Note that calling head on the buffered iterator bit does not advance it. Therefore, the subsequent call bit.next() returns the same value as bit.head.

As usual, the underlying iterator must not be used directly and must be discarded.

The buffered iterator only buffers the next element when head is invoked. Other derived iterators, such as those produced by duplicate and partition, may buffer arbitrary subsequences of the underlying iterator. But iterators can be efficiently joined by adding them together with ++:

scala> def collapse(it: Iterator[Int]) = if (!it.hasNext) Iterator.empty else {
      |  var head = it.next
      |  val rest = if (head == 0) it.dropWhile(_ == 0) else it
      |  Iterator.single(head) ++ rest
      |}
def collapse(it: Iterator[Int]): Iterator[Int]

scala> def collapse(it: Iterator[Int]) = {
      |  val (zeros, rest) = it.span(_ == 0)
      |  zeros.take(1) ++ rest
      |}
def collapse(it: Iterator[Int]): Iterator[Int]

scala> collapse(Iterator(0, 0, 0, 1, 2, 3, 4)).toList
val res14: List[Int] = List(0, 1, 2, 3, 4)

scala> def collapse(it: Iterator[Int]) = if !it.hasNext then Iterator.empty else
      |  var head = it.next
      |  val rest = if head == 0 then it.dropWhile(_ == 0) else it
      |  Iterator.single(head) ++ rest
      |
def collapse(it: Iterator[Int]): Iterator[Int]

scala> def collapse(it: Iterator[Int]) =
      |  val (zeros, rest) = it.span(_ == 0)
      |  zeros.take(1) ++ rest
      |
def collapse(it: Iterator[Int]): Iterator[Int]

scala> collapse(Iterator(0, 0, 0, 1, 2, 3, 4)).toList
val res14: List[Int] = List(0, 1, 2, 3, 4)

In the second version of collapse, the unconsumed zeros are buffered internally. In the first version, any leading zeros are dropped and the desired result constructed as a concatenated iterator, which simply calls its two constituent iterators in turn.