Итераторы

Итератор (Iterator) - это не коллекция, а скорее способ поочередного доступа к элементам коллекции. Есть две основные операции у итератора - это next и hasNext. Вызов метода it.next() на итераторе it вернет следующий элемент и изменит его состояние. Повторный вызов next на том же итераторе выведит следующий элемент идущий после ранее возвращённого. Если больше нет элементов для возврата, вызов команды next кинет исключение NoSuchElementException. Вы можете узнать, есть ли еще элементы для возврата с помощью метода hasNext у Итератора.

Самый простой способ “обойти” все элементы, возвращаемые итератором it - это использование циклов с while-loop:

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

У итераторов в Scala есть аналоги большинству методов, которые вы можете найдти в классах Traversable, Iterable и Seq. Например, метод “foreach”, который на итераторе выполняет процедуру на каждом элементе, возвращаемого итератором. Используя foreach, описанный выше цикл можно сократить до:

it foreach println

Как всегда, “for выражения” могут быть использованы в качестве альтернативного синтаксиса для выражений, включающих в себя foreach, map, ` WithFilter и flatMap`, поэтому еще одним способом вывести все элементы, возвращаемые итератором, будет:

for (elem <- it) println(elem)

Существует важное различие между методом foreach на итераторах и тем же методом на traversable коллекциях: При вызове метода foreach на итераторе, итератор остается в конце, указывая что все элементы закончились. Поэтому очередной вызов next на томже самом итераторе выбросит исключение NoSuchElementException. В отличие от этого, при обращении к коллекции, команда foreach оставляет количество элементов в коллекции неизменным (если только переданная функция не добавляет элементов, но это крайне не желательно, так как может привести к неожиданным результатам).

Другие общие операции между Iterator и Iterable, имеют одни и те же свойства. Например, итераторы предоставляют метод map, который возвращает новый итератор:

scala> val it = Iterator("a", "number", "of", "words")
it: Iterator[java.lang.String] = <iterator>
scala> it.map(_.length)
res1: Iterator[Int] = <iterator>
scala> it.hasNext
res2: Boolean = true
scala> res1 foreach println
1
6
2
5
scala> it.hasNext
res4: Boolean = false

Как видите, после вызова функции it.map итератор it не остановился в конце, в отличии от res1.foreach который проходит через весь итератор, после чего it остается в самом конце.

Другой пример - метод dropWhile, который можно использовать для поиска первых элементов итератора, соответствующих условию. Например, чтобы найти первое слово в итераторе выше, которое содержит хотя бы два символа, можно было бы написать:

scala> val it = Iterator("a", "number", "of", "words")
it: Iterator[java.lang.String] = <iterator>
scala> it dropWhile (_.length < 2)
res4: Iterator[java.lang.String] = <iterator>
scala> res4.next()
res5: java.lang.String = number

Обратите внимание еще раз, что сам итераторit был изменен вызовом dropWhile: теперь он указывает на второе слово number в списке. Фактически, it и результат res4 возвращаемый послеdropWhile возвращают одну и туже последовательность элементов.

Чтобы избежать такое поведение, как вариант можно использовать duplicate (дублировать используемый итератор), вызывая методы на разных итераторах. Каждый из двух итераторов будет обрабатывать точно такие же элементы, как и тот, из которого состоит итераторатор it:

scala> val (words, ns) = Iterator("a", "number", "of", "words").duplicate
words: Iterator[String] = <iterator>
ns: Iterator[String] = <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

Оба итератора работают независимо друг от друга: продвижение одного не влияет на другого, так что каждый из них может быть модифицирован независимо от другого. Может создаться впечатление что итератор подвергается двойному обходу над элементами, но это не так, результат достигается за счет внутреннего буферизации. Как обычно, базовый итератор it не пригоден для прямого использования и должен быть исключен из дальнейших операций.

Обобщая вышесказанное, итераторы ведут себя как коллекции, если после вызова метода на них сам итератор больше не вызывается. В библиотеке коллекции Scala это достигается явным образом с помощью абстракции IterableOnce, который является общим суперкласом для Iterable и Iterator. У IterableOnce[A] только два метода: iterator: Iterator[A] и knownSize: Int.

Если объект IterableOnce является Iterator, то его операция iterator всегда возвращает себя, в своем текущем состоянии, но если он Iterable, то операция iterator всегда возвращает новый Iterator. Типовой вариант использования IterableOnce - в качестве типа аргумента для методов, которые могут принимать или итератор или коллекцию в качестве аргумента. Примером может служить метод соединения concat в классе Iterable. Он принимает IterableOnce параметр, поэтому вы можете соединять элементы, поступающие или из итератора или коллекции.

Все операции на итераторах собраны в таблице ниже.

Операции на классе Iterator

Ленивость

В отличие от операций непосредственно на конкретных коллекциях типа List, операции на Iterator ленивы.

Ленивая операция не сразу вычисляет результаты. Вместо этого она рассчитывает результаты тогда когда они непосредственно запрашиваются.

Поэтому выражение (1 to 10).iterator.map(println) не выведет ничего на экран. Метод map в данном случае не применяет функцию в аргументе к значениям в диапазоне, вместо этого будет возвращен новый Iterator, который будет выполнять операции тогда когда будет запрошен их результат. Добавление .toList в конец этого выражения фактически вызовет вывод элементов на печать.

Как следствие, такие методы как map или filter не обязательно применят функцию в аргументе ко всем входным элементам. Выражение (1 to 10).iterator.map(println).take(5).toList выводит только значения от 1 до 5, поскольку это те значения, которые запрашиваются у Iterator, возвращаемого из map.

Это одна из причин, того почему важно использовать только чистые функции в качестве аргументов для map, filter, fold и подобных методов. Помните, что чистая функция не имеет побочных эффектов, поэтому println обычно не используется в map. Здесь println используется лишь для демонстрации “ленивости”, которую с чистыми функциями не заметно.

Ленивость ценна, несмотря на то, что часто невидима, так как она может предотвратить ненужные вычисления и позволить работать с бесконечными последовательностями, как в следующем примере:

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

Буферезированные итераторы

Иногда вам нужен итератор, который может “заглянуть вперед”, чтобы вы могли оценить следующий элемент, который будет возвращен без перемещения позиции. Рассмотрим, например, задачу пропуска впереди идущих пустых строк из итератора, который возвращает последовательность строк. У вас может возникнуть соблазн написать следующее

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

Но если присмотреться к этому коду внимательнее, то становится понятно, что такой код не корректен: код действительно пропустит ведущие пустые строки, но он также пропустит первую непустую строку it!

Решение этой проблемы заключается в использовании буферизированного итератора. Класс BufferedIterator базирующийся на классе Iterator предоставляет один дополнительный метод, head. Вызов head на буферизированном итераторе вернет его первый элемент, но не продвинет итератор дальше. С помощью буферизированного итератора можно пропустить пустые слова следующим образом.

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

Каждый итератор может быть преобразован в буферизированный после вызова метода buffered. Например:

scala> val it = Iterator(1, 2, 3, 4)
it: Iterator[Int] = <iterator>
scala> val bit = it.buffered
bit: scala.collection.BufferedIterator[Int] = <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)

Обратите внимание, что вызов метода head на буферизированном итераторе bit не продвигает его вперед. Поэтому последующий вызов bit.next() возвращает то же значение, что и bit.head.

Как обычно, базовый итератор не должен в дальнейшем использоваться напрямую и должен быть исключен из операций.

Буферизированный итератор буферизирует только следующий элемент, когда вызывается head. Другие производные итераторы, например произведенные от вызова duplicate и partition, могут буферизировать любое количество подпоследовательностей дочерних итераторов. Впрочем, итераторы могут быть эффективно объединены используя метод ++:

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)

В первой версии, любые встречаемые нули сбрасываются, а затем строится требуемый результат как объединенный итератор, который в свою очередь просто вызывает два входящих в него итератора. Во втором варианте collapse неиспользованные нули буферизируются внутри.