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())

Iterators in Scala also provide analogues of most of the methods that you find in the Traversable, 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)

There’s an important difference between the foreach method on iterators and the same method on traversable 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 Traversable have the same property. For instance, iterators provide a map method, which returns a new iterator:

scala> val it = Iterator("a", "number", "of", "words")
it: Iterator[java.lang.String] = non-empty iterator
scala> it.map(_.length)
res1: Iterator[Int] = non-empty iterator
scala> res1 foreach println
1
6
2
5
scala> it.next()
java.util.NoSuchElementException: next on empty iterator

As you can see, after the call to it.map, the it iterator has advanced 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")
it: Iterator[java.lang.String] = non-empty iterator
scala> it dropWhile (_.length < 2)
res4: Iterator[java.lang.String] = non-empty iterator
scala> res4.next()
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
words: Iterator[String] = non-empty iterator
ns: Iterator[String] = non-empty iterator

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

scala> val count = ns.map(_.length).sum
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 TraversableOnce, which is a common superclass of Traversable and Iterator. As the name implies, TraversableOnce objects can be traversed using foreach but the state of that object after the traversal is not specified. If the TraversableOnce object is in fact an Iterator, it will be at its end after the traversal, but if it is a Traversable, it will still exist as before. A common use case of TraversableOnce is as an argument type for methods that can take either an iterator or a traversable as argument. An example is the appending method ++ in class Traversable. It takes a TraversableOnce parameter, so you can append elements coming from either an iterator or a traversable 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)] = Stream.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) {}

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() }

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)
it: Iterator[Int] = non-empty iterator
scala> val bit = it.buffered
bit: scala.collection.BufferedIterator[Int] = non-empty iterator
scala> bit.head
res10: Int = 1
scala> bit.next()
res11: Int = 1
scala> bit.next()
res12: Int = 2
scala> bit.headOption
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
     | }
collapse: (it: Iterator[Int])Iterator[Int]

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

scala> collapse(Iterator(0, 0, 0, 1, 2, 3, 4)).toList
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.