Итераторы

В Go ключевое слово for range используется для итерации по встроенным структурам данных:

Массивы
Срезы
Строки
map
Каналы
Целые значения

Это негибко и не расширяемо для пользовательских типов. Однако после обновления Go 1.23 ключевое слово for range поддерживает range over func, что делает возможными пользовательские итераторы.

Знакомство

Рассмотрим пример. В разделе о функциях был пример замыкания для вычисления чисел Фибоначчи:

func Fibonacci(n int) func() (int, bool) {
  a, b, c := 1, 1, 2
  i := 0
  return func() (int, bool) {
    if i >= n {
      return 0, false
    } else if i < 2 {
      f := i
      i++
      return f, true
    }

    a, b = b, c
    c = a + b
    i++

    return a, true
  }
}

Преобразуем его в итератор:

func Fibonacci(n int) func(yield func(int) bool) {
  a, b, c := 0, 1, 1
  return func(yield func(int) bool) {
    for range n {
      if !yield(a) {
        return
      }
      a, b = b, c
      c = a + b
    }
  }
}

Итераторы в Go используют стиль range over func. Можно использовать ключевое слово for range:

func main() {
    n := 8
  for f := range Fibonacci(n) {
    fmt.Println(f)
  }
}

Вывод:

Итератор — функция замыкания, принимающая функцию обратного вызова в качестве параметра. Можно заметить ключевое слово yield, знакомое пользователям Python. Итераторы Go похожи на генераторы Python. Go не добавляет новых ключевых слов — yield просто функция обратного вызова, а не ключевое слово. Официальное название выбрано для удобства понимания.

Push-итераторы

Определение итератора в библиотеке iter:

An iterator is a function that passes successive elements of a sequence to a callback function, conventionally named yield.
Итератор — функция, передающая последовательные элементы последовательности функции обратного вызова, обычно называемой yield.

Итератор — функция, принимающая функцию обратного вызова. Во время итерации элементы последовательно передаются функции yield.

Использование итератора:

for f := range Fibonacci(n) {
    fmt.Println(f)
}

Согласно официальному определению, это эквивалентно:

Fibonacci(n)(func(f int) bool {
    fmt.Println(f)
    return true
})

Тело цикла — функция обратного вызова yield. При возврате true итератор продолжает итерацию, иначе останавливается.

В стандартной библиотеке iter определены типы итераторов iter.Seq:

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

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

iter.Seq принимает один параметр, поэтому for range имеет одно возвращаемое значение:

for v := range iter {
  // body
}

iter.Seq2 принимает два параметра, поэтому for range имеет два возвращаемых значения:

for k, v := range iter {
  // body
}

Хотя стандартная библиотека не определяет Seq с 0 параметрами, это допустимо:

func(yield func() bool)

Использование:

for range iter {
  // body
}

Количество параметров функции обратного вызова — от 0 до 2, больше не допускается.

Тело цикла for range — функция обратного вызова yield. Количество возвращаемых значений for range соответствует количеству параметров yield. На каждой итерации итератор вызывает yield, выполняя код цикла и передавая элементы. Такие итераторы называются push-итераторами (pushing iterator). Типичный пример — foreach в других языках, например JavaScript:

javascript

let arr = [1, 2, 3, 4, 5];
arr
  .filter((e) => e % 2 === 0)
  .forEach((e) => {
    console.log(e);
  });

В Go это выражается через range:

for index, value := range iterator() {
  fmt.Println(index, value)
}

В некоторых языках (например, Java) это называется обработкой потока данных.

Поскольку код цикла — функция обратного вызова, возможно замыкание. Go должен обрабатывать defer, return, break, goto в замыкании как в обычном цикле.

Например, возврат в цикле итератора:

for index, value := range iterator() {
    if value > 10 {
        return
  }
  fmt.Println(index, value)
}

Невозможно напрямую вернуть из функции обратного вызова — это только остановит итератор:

iterator()(func(index int, value int) bool {
  if value > 10 {
    return false
  }
  fmt.Println(index, value)
})

Использование defer в цикле итератора:

for index, value := range iterator() {
    defer fmt.Println(index, value)
}

Невозможно напрямую использовать defer в функции обратного вызова — это вызовет отложенный вызов после завершения:

iterator()(func(index int, value int) bool {
  defer fmt.Println(index, value)
})

Аналогично для break, continue, goto. Go обрабатывает эти ситуации автоматически. Исходный код: rangefunc/rewrite.go.

Pull-итераторы

Push-итераторы управляются логикой итератора, пользователь пассивно получает элементы. Pull-итераторы управляются пользователем, который активно получает элементы. Обычно pull-итераторы имеют функции next(), stop() для управления началом и завершением итерации. Это может быть замыкание или структура.

scanner := bufio.NewScanner(file)
for scanner.Scan() {
    line, err := scanner.Text(), scanner.Err()
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Println(line)
}

Scanner получает следующую строку через Text(), Scan() определяет завершение итерации. Scanner использует структуру для состояния, а в библиотеке iter pull-итераторы используют замыкания. Функции iter.Pull или iter.Pull2 преобразуют push-итератор в pull-итератор. Разница — количество возвращаемых значений:

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

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

Обе принимают итератор и возвращают функции next() и stop() для управления итерацией:

func next() (V, bool)

func stop()

next возвращает элемент и булево значение валидности. При завершении итерации возвращается нулевое значение и false. stop завершает итерацию. После использования необходимо вызвать stop. Вызов next из нескольких горутин для одного итератора неверен — это не потокобезопасно.

Пример преобразования итератора Фибоначчи в pull-итератор:

func main() {
  n := 10
  next, stop := iter.Pull(Fibonacci(n))
  defer stop()
  for {
    fibn, ok := next()
    if !ok {
      break
    }
    fmt.Println(fibn)
  }
}

Вывод:

Теперь можно управлять итерацией через next и stop. Может показаться, что это излишне — почему не использовать оригинальную версию замыкания:

func main() {
  fib := Fibonacci(10)
    for {
        n, ok := fib()
        if !ok {
            break
        }
        fmt.Println(n)
    }
}

Преобразование: замыкание → итератор → pull-итератор. Использование замыкания и pull-итератора похоже, их идея одинакова. Последний может иметь проблемы с производительностью. Действительно, это излишне,应用场景不多. Однако iter.Pull существует для iter.Seq — преобразования push-итераторов в pull-итераторы. Если нужен pull-итератор, реализация push-итератора для преобразования требует оценки сложности и производительности. В примере с Фибоначчи это круговой путь. Единственное преимущество — соответствие официальной спецификации итераторов.

Обработка ошибок

При ошибке во время итерации можно передать её функции yield для возврата через for range:

func ScanLines(reader io.Reader) iter.Seq2[string, error] {
  scanner := bufio.NewScanner(reader)
  return func(yield func(string, error) bool) {
    for scanner.Scan() {
      if !yield(scanner.Text(), scanner.Err()) {
        return
      }
    }
  }
}

TIP

Итератор ScanLines одноразовый — после закрытия файла повторное использование невозможно.

Второе возвращаемое значение — error. Использование:

for line, err := range ScanLines(file) {
    if err != nil {
        fmt.Println(err)
        break
    }
    fmt.Println(line)
}

Обработка ошибок как обычно. Для pull-итераторов:

next, stop := iter.Pull2(ScanLines(file))
defer stop()
for {
    line, err, ok := next()
    if err != nil {
        fmt.Println(err)
        break
    } else if !ok {
        break
    }
    fmt.Println(line)
}

При панике используйте recover:

defer func() {
    if err := recover(); err != nil {
        fmt.Println("panic:", err)
        os.Exit(1)
    }
}()

for line, err := range ScanLines(file) {
    if err != nil {
        fmt.Println(err)
        break
    }
    fmt.Println(line)
}

Стандартная библиотека

Многие стандартные библиотеки поддерживают итераторы, наиболее полезные — slices и maps.

slices.All

func All[Slice ~[]E, E any](s Slice) iter.Seq2[int, E]

slices.All преобразует срез в итератор:

func main() {
  s := []int{1, 2, 3, 4, 5}
  for i, n := range slices.All(s) {
    fmt.Println(i, n)
  }
}

Вывод:

slices.Values

func Values[Slice ~[]E, E any](s Slice) iter.Seq[E]

slices.Values преобразует срез в итератор без индекса:

func main() {
  s := []int{1, 2, 3, 4, 5}
  for n := range slices.Values(s) {
    fmt.Println(n)
  }
}

Вывод:

slices.Chunk

func Chunk[Slice ~[]E, E any](s Slice, n int) iter.Seq[Slice]

slices.Chunk возвращает итератор, передающий срезы по n элементов:

func main() {
  s := []int{1, 2, 3, 4, 5}
  for chunk := range slices.Chunk(s, 2) {
    fmt.Println(chunk)
  }
}

Вывод:

[1 2]
[3 4]
[5]

slices.Collect

func Collect[E any](seq iter.Seq[E]) []E

slices.Collect собирает итератор в срез:

func main() {
  s := []int{1, 2, 3, 4, 5}
  s2 := slices.Collect(slices.Values(s))
  fmt.Println(s2)
}

Вывод:

[1 2 3 4 5]

maps.Keys

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K]

maps.Keys возвращает итератор ключей map. С slices.Collect можно собрать в срез:

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  keys := slices.Collect(maps.Keys(m))
  fmt.Println(keys)
}

Вывод:

[three one two]

map неупорядочен, вывод нефиксирован.

maps.Values

func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V]

maps.Values возвращает итератор значений map:

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  keys := slices.Collect(maps.Values(m))
  fmt.Println(keys)
}

Вывод:

[3 1 2]

maps.All

func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V]

maps.All преобразует map в итератор:

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  for k, v := range maps.All(m) {
    fmt.Println(k, v)
  }
}

Обычно используется с другими функциями обработки потока данных.

maps.Collect

func Collect[K comparable, V any](seq iter.Seq2[K, V]) map[K]V

maps.Collect собирает итератор map в map:

func main() {
  m := map[string]int{"one": 1, "two": 2, "three": 3}
  m2 := maps.Collect(maps.All(m))
  fmt.Println(m2)
}

Функция collect обычно используется как завершающая функция обработки потока данных.

Цепочные вызовы

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

sortedSlices := slices.Sorted(slices.Values(s))

Итераторы Go используют замыкания, поэтому возможны только вложенные вызовы функций, что ухудшает читаемость при длинных цепочках. Можно реализовать цепочные вызовы через структуры.

Демонстрация

Простой пример цепочных вызовов с Filter, Map, Find, Some:

package iterx

import (
  "iter"
  "slices"
)

type SliceSeq[E any] struct {
  seq iter.Seq2[int, E]
}

func (s SliceSeq[E]) All() iter.Seq2[int, E] {
  return s.seq
}

func (s SliceSeq[E]) Filter(filter func(int, E) bool) SliceSeq[E] {
  return SliceSeq[E]{
    seq: func(yield func(int, E) bool) {
      i := 0
      for k, v := range s.seq {
        if filter(k, v) {
          if !yield(i, v) {
            return
          }
          i++
        }
      }
    },
  }
}

func (s SliceSeq[E]) Map(mapFn func(E) E) SliceSeq[E] {
  return SliceSeq[E]{
    seq: func(yield func(int, E) bool) {
      for k, v := range s.seq {
        if !yield(k, mapFn(v)) {
          return
        }
      }
    },
  }
}

func (s SliceSeq[E]) Fill(fill E) SliceSeq[E] {
  return SliceSeq[E]{
    seq: func(yield func(int, E) bool) {
      for i, _ := range s.seq {
        if !yield(i, fill) {
          return
        }
      }
    },
  }
}

func (s SliceSeq[E]) Find(equal func(int, E) bool) (_ E) {
  for i, v := range s.seq {
    if equal(i, v) {
      return v
    }
  }
  return
}

func (s SliceSeq[E]) Some(match func(int, E) bool) bool {
  for i, v := range s.seq {
    if match(i, v) {
      return true
    }
  }
  return false
}

func (s SliceSeq[E]) Every(match func(int, E) bool) bool {
  for i, v := range s.seq {
    if !match(i, v) {
      return false
    }
  }
  return true
}

func (s SliceSeq[E]) Collect() []E {
  var res []E
  for _, v := range s.seq {
    res = append(res, v)
  }
  return res
}

func (s SliceSeq[E]) Sort(cmp func(x, y E) int) []E {
  collect := s.Collect()
  slices.SortFunc(collect, cmp)
  return collect
}

func (s SliceSeq[E]) SortStable(cmp func(x, y E) int) []E {
  collect := s.Collect()
  slices.SortStableFunc(collect, cmp)
  return collect
}

func Slice[S ~[]E, E any](s S) SliceSeq[E] {
  return SliceSeq[E]{seq: slices.All(s)}
}

Примеры использования:

Обработка значений

func main() {
  s := []string{"apple", "banana", "cherry"}
  all := iterx.Slice(s).Map(strings.ToUpper).All()
  for i, v := range all {
    fmt.Printf("index: %d, value: %s\n", i, v)
  }
}

Вывод:

index: 0, value: APPLE
index: 1, value: BANANA
index: 2, value: CHERRY

Поиск значения

func main() {
  s := []int{1, 2, 3, 4, 5}
  result := iterx.Slice(s).Find(func(i int, e int) bool {
    return e == 3
  })
  fmt.Println(result)
}

Вывод:

Заполнение среза

func main() {
  s := []int{1, 2, 3, 4, 5}
  result := iterx.Slice(s).Fill(6).Collect()
  fmt.Println(result)
}

Вывод:

[6 6 6 6 6]

Фильтрация элементов

func main() {
  s := []int{1, 2, 3, 4, 5}
  filter := iterx.Slice(s).Filter(func(i int, e int) bool {
    return e%2 == 0
  }).All()
  for i, v := range filter {
    fmt.Printf("Index: %d, Value: %d\n", i, v)
  }
}

Вывод:

Index: 0, Value: 2
Index: 1, Value: 4

К сожалению, Go пока не поддерживает краткие анонимные функции, как стрелочные функции в JavaScript, Rust, Java, иначе цепочные вызовы были бы лаконичнее.

Производительность

Поскольку Go обрабатывает итераторы, их производительность ниже, чем у нативного цикла for range. Сравним производительность:

Нативный цикл for
Push-итератор
Pull-итератор

Тестовый код для среза длиной 1000:

package main

import (
  "iter"
  "slices"
  "testing"
)

var s []int

const n = 10000

func init() {
  for i := range n {
    s = append(s, i)
  }
}

func testNaiveFor(s []int) {
  for i, n := range s {
    _ = i
    _ = n
  }
}

func testPushing(s []int) {
  for i, n := range slices.All(s) {
    _ = i
    _ = n
  }
}

func testPulling(s []int) {
  next, stop := iter.Pull2(slices.All(s))
  for {
    i, n, ok := next()
    if !ok {
      stop()
      return
    }
    _ = i
    _ = n
  }
}

func BenchmarkNaive_10000(b *testing.B) {
  for range b.N {
    testNaiveFor(s)
  }
}

func BenchmarkPushing_10000(b *testing.B) {
  for range b.N {
    testPushing(s)
  }
}

func BenchmarkPulling_10000(b *testing.B) {
  for range b.N {
    testPulling(s)
  }
}

Результаты:

goos: windows
goarch: amd64
pkg: golearn
cpu: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
BenchmarkNaive_10000
BenchmarkNaive_10000-16           492658              2398 ns/op               0 B/op          0 allocs/op
BenchmarkPushing_10000
BenchmarkPushing_10000-16         315889              3707 ns/op               0 B/op          0 allocs/op
BenchmarkPulling_10000
BenchmarkPulling_10000-16           2016            574509 ns/op             440 B/op         14 allocs/op
PASS
ok      golearn 4.029s

Push-итераторы незначительно медленнее нативного for range. Pull-итераторы медленнее почти на два порядка. Учитывайте это при использовании.

Заключение

Как и дженерики, итераторы Go вызывают споры. Некоторые считают, что итераторы добавляют сложность, противореча философии простоты Go. Код с замыканиями итераторов сложно отлаживать и читать.

Обсуждения итераторов:

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

Итераторы ​

Знакомство ​

Push-итераторы ​

Pull-итераторы ​

Обработка ошибок ​

Стандартная библиотека ​

Цепочные вызовы ​

Демонстрация ​

Производительность ​

Заключение ​

Итераторы

Знакомство

Push-итераторы

Pull-итераторы

Обработка ошибок

Стандартная библиотека

Цепочные вызовы

Демонстрация

Производительность

Заключение