Описание пакета iter языка программирования Go

Пакет iter предоставляет базовые определения и операции, связанные с итераторами по последовательностям.
Tags:

Итераторы

type (
	Seq[V any]     func(yield func(V) bool)
	Seq2[K, V any] func(yield func(K, V) bool)
)

Seq2 представляет последовательность пар значений, традиционно ключ-значение или индекс-значение.

Yield возвращает true, если итератор должен продолжить с следующим элементом последовательности, и false, если он должен остановиться.

Например, maps.Keys возвращает итератор, который производит последовательность ключей карты m, реализованную следующим образом:

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K] {
	return func(yield func(K) bool) {
		for k := range m {
			if !yield(k) {
				return
			}
		}
	}
}

Дополнительные примеры можно найти в блоге Go: Range Over Function Types.

Функции итераторов чаще всего вызываются в цикле range, как в следующем примере:

func PrintAll[V any](seq iter.Seq[V]) {
	for v := range seq {
		fmt.Println(v)
	}
}

Конвенции именования

Функции и методы итераторов называются в зависимости от последовательности, по которой они проходят:

// All возвращает итератор по всем элементам в s.
func (s *Set[V]) All() iter.Seq[V]

Метод итератора на типе коллекции традиционно называется All, потому что он итерирует последовательность всех значений в коллекции.

Для типа, содержащего несколько возможных последовательностей, имя итератора может указывать, какая последовательность предоставляется:

// Cities возвращает итератор по основным городам страны.
func (c *Country) Cities() iter.Seq[*City]

// Languages возвращает итератор по официальным языкам страны.
func (c *Country) Languages() iter.Seq[string]

Если итератор требует дополнительной конфигурации, конструкторная функция может принимать дополнительные аргументы конфигурации:

// Scan возвращает итератор по парам ключ-значение с min ≤ key ≤ max.
func (m *Map[K, V]) Scan(min, max K) iter.Seq2[K, V]

// Split возвращает итератор по (возможно, пустым) подстрокам s,
// разделенным sep.
func Split(s, sep string) iter.Seq[string]

Когда существует несколько возможных порядков итерации, имя метода может указывать на этот порядок:

// All возвращает итератор по списку от начала к концу.
func (l *List[V]) All() iter.Seq[V]

// Backward возвращает итератор по списку от конца к началу.
func (l *List[V]) Backward() iter.Seq[V]

// Preorder возвращает итератор по всем узлам синтаксического дерева
// под (и включая) указанный корень, в глубину, в порядке preorder,
// посещая родительский узел перед его дочерними узлами.
func Preorder(root Node) iter.Seq[Node]

Одноразовые итераторы

Большинство итераторов предоставляют возможность пройти по всей последовательности: при вызове итератор выполняет любую необходимую настройку для начала последовательности, затем вызывает yield для последовательных элементов последовательности и затем очищает перед возвратом. Повторный вызов итератора снова проходит по последовательности.

Некоторые итераторы нарушают это правило, предоставляя возможность пройти по последовательности только один раз. Эти “одноразовые итераторы” обычно сообщают значения из потока данных, который нельзя перемотать назад для начала. Повторный вызов итератора после ранней остановки может продолжить поток, но повторный вызов после завершения последовательности не вернет никаких значений. Документационные комментарии для функций или методов, возвращающих одноразовые итераторы, должны документировать этот факт:

// Lines возвращает итератор по строкам, прочитанным из r.
// Он возвращает одноразовый итератор.
func (r *Reader) Lines() iter.Seq[string]

Извлечение значений

Функции и методы, которые принимают или возвращают итераторы, должны использовать стандартные типы Seq или Seq2, чтобы обеспечить совместимость с циклами range и другими адаптерами итераторов. Стандартные итераторы можно рассматривать как “push-итераторы”, которые передают значения в функцию yield.

Иногда цикл range не является наиболее естественным способом потребления значений последовательности. В этом случае Pull преобразует стандартный push-итератор в “pull-итератор”, который можно вызвать для извлечения одного значения за раз из последовательности. Pull запускает итератор и возвращает пару функций — next и stop, которые возвращают следующее значение из итератора и останавливают его соответственно.

Например:

// Pairs возвращает итератор по последовательным парам значений из seq.
func Pairs[V any](seq iter.Seq[V]) iter.Seq2[V, V] {
	return func(yield func(V, V) bool) {
		next, stop := iter.Pull(seq)
		defer stop()
		for {
			v1, ok1 := next()
			if !ok1 {
				return
			}
			v2, ok2 := next()
			// Если ok2 равно false, v2 должно быть
			// нулевым значением; yield одна последняя пара.
			if !yield(v1, v2) {
				return
			}
			if !ok2 {
				return
			}
		}
	}
}

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

Использование стандартной библиотеки

Некоторые пакеты в стандартной библиотеке предоставляют API на основе итераторов, наиболее заметными из которых являются пакеты maps и slices. Например, maps.Keys возвращает итератор по ключам карты, в то время как slices.Sorted собирает значения итератора в срез, сортирует их и возвращает срез. Чтобы итерировать по отсортированным ключам карты, можно использовать следующий код:

for _, key := range slices.Sorted(maps.Keys(m)) {
	...
}

Мутация

Итераторы предоставляют только значения последовательности, но не прямой способ их изменения. Если итератор хочет предоставить механизм для изменения последовательности во время итерации, обычное решение — определить тип позиции с дополнительными операциями и затем предоставить итератор по позициям.

Например, реализация дерева может предоставить:

// Positions возвращает итератор по позициям в последовательности.
func (t *Tree[V]) Positions() iter.Seq[*Pos]

// Pos представляет позицию в последовательности.
// Он действителен только во время вызова yield, в который он передается.
type Pos[V any] struct { ... }

// Value возвращает значение в курсоре.
func (p *Pos[V]) Value() V

// Delete удаляет значение в этой точке итерации.
func (p *Pos[V]) Delete()

// Set изменяет значение v в курсоре.
func (p *Pos[V]) Set(v V)

И затем клиент может удалить boring значения из дерева, используя:

for p := range t.Positions() {
	if boring(p.Value()) {
		p.Delete()
	}
}

Этот подход позволяет итератору предоставлять механизм для изменения последовательности во время итерации, сохраняя при этом чистоту итератора как такового.

Функции

func Pull

func Pull[V any](seq Seq[V]) (next func() (V, bool), stop func())

Pull преобразует последовательность итератора в стиле “push” seq в итератор в стиле “pull”, доступный через две функции next и stop.

Next возвращает следующее значение в последовательности и булево значение, указывающее, является ли значение действительным. Когда последовательность завершена, next возвращает нулевое значение V и false. Вызов next после достижения конца последовательности или после вызова stop является допустимым. Эти вызовы будут продолжать возвращать нулевое значение V и false.

Stop завершает итерацию. Его нужно вызвать, когда вызывающий не заинтересован в следующих значениях, и next еще не сигнализировал о завершении последовательности (с возвратом false). Вызов stop несколько раз и после того, как next уже вернул false, является допустимым. Обычно вызывающие должны использовать “defer stop()”.

Ошибкой является вызов next или stop из нескольких горутин одновременно.

Если итератор вызывает панику во время вызова next (или stop), то next (или stop) сам вызывает панику с тем же значением.

func Pull2

func Pull2[K, V any](seq Seq2[K, V]) (next func() (K, V, bool), stop func())

Pull2 преобразует последовательность итератора в стиле “push” seq в итератор в стиле “pull”, доступный через две функции next и stop.

Next возвращает следующую пару в последовательности и булево значение, указывающее, является ли пара действительной. Когда последовательность завершена, next возвращает пару нулевых значений и false. Вызов next после достижения конца последовательности или после вызова stop является допустимым. Эти вызовы будут продолжать возвращать пару нулевых значений и false.

Stop завершает итерацию. Его нужно вызвать, когда вызывающий не заинтересован в следующих значениях, и next еще не сигнализировал о завершении последовательности (с возвратом false). Вызов stop несколько раз и после того, как next уже вернул false, является допустимым. Обычно вызывающие должны использовать “defer stop()”.

Ошибкой является вызов next или stop из нескольких горутин одновременно.

Если итератор вызывает панику во время вызова next (или stop), то next (или stop) сам вызывает панику с тем же значением.

Типы

type Seq

type Seq[V any] func(yield func(V) bool)

Seq — это итератор по последовательностям отдельных значений. Когда вызывается как seq(yield), seq вызывает yield(v) для каждого значения v в последовательности, останавливаясь раньше, если yield возвращает false. Подробнее см. в документации пакета iter.

type Seq2

type Seq2[K, V any] func(yield func(K, V) bool)

Seq2 — это итератор по последовательностям пар значений, наиболее часто ключ-значение. Когда вызывается как seq(yield), seq вызывает yield(k, v) для каждой пары (k, v) в последовательности, останавливаясь раньше, если yield возвращает false. Подробнее см. в документации пакета iter.