Перевод/заметки Ranging over functions in Go 1.23
В Go 1.23 добавлена новая возможность ranging over functions (итераторы), согласно этому предложению. Есть хорошое описание в официальном блоге Go от августа.
Предыстория - оригинальный for-range
Все Go-программисты знают и любят старый добрый for ... := range цикл; будь то перебор элементов слайса, рун строки или пар ключ/значение мапы - это универсальный инструмент, и мало какая программа обходится без него.
for i, elem := range mySlice {
// use index i or element elem somehow
}
Однако до сих пор использование операторов for-range было ограничено лишь небольшим количеством конструкций в языке Go: массивами, слайсами, строками, мапами и каналами.
Итерация по int
Первое изменение - это range над целыми числами. Вот базовый пример того, как это выглядит:
for i := range 5 {
fmt.Println(i)
}
Этот код в точности эквивалентен:
for i := 0; i < 5; i++ {
fmt.Println(i)
}
Программа выведет числа 0, 1, 2, 3, 4, каждое в отдельной строке. Стоит отметить, что значение после ключевого слова range не обязательно должно быть константой, а присваивание значений необязательно.
for range n {
// do something
}
Это всего лишь сокращение для очень распространённого цикла (for (i:= 0; i < n; i++)). Как заметил Russ Cox, примерно половина циклов, которые он видел, можно преобразовать в эту форму “range over int”. Сюда же относятся и бенчмарки в Go, где основной цикл можно представить в следующем виде:
for range b.N {
// run the benchmarked code
}
Range over functions - мотивация
С тех пор как в языке программирования Go в версии 1.18 были введены дженерики, программисты начали активно создавать общие контейнеры и абстрактные структуры данных. Дженерики дают возможность эффективно и удобно отделить структуру данных от типов хранимых элементов, что раньше было невозможно без использования пустых интерфейсов.
Однако при разработке пользовательских контейнеров возникал один важный вопрос: как выполнять итерацию по их элементам? В то время как Go поддерживает итерацию по встроенным контейнерам, таким как слайсы и мапы, для пользовательских контейнеров эта функция была недоступна, что заставляло программистов изобретать специальные методы итерации.
В качестве конкретного примера рассмотрим гипотезу, что программисты Lisp были правы, и ассоциативные списки являются лучшей структурой данных. Используя дженерики, мы можем реализовать в Go простой ассоциативный список, основанный на слайсе:
type AssocList[K comparable, V any] struct {
lst []pair[K, V]
}
type pair[K comparable, V any] struct {
key K
value V
}
func (al *AssocList[K, V]) Add(key K, value V) {
al.lst = append(al.lst, pair[K, V]{key, value})
}
Мы можем создать ассоциативный список и заполнить его:
al := &AssocList[int, string]{}
al.Add(10, "ten")
al.Add(20, "twenty")
al.Add(5, "five")
При наличии такой структуры данных возникает логичный вопрос: как эффективно перебрать все ее элементы? Мы могли бы воспользоваться обходным путем и перебрать все элементы вручную, однако это потребовало бы раскрытия внутренних деталей реализации. Что, если в будущем мы захотим повторно реализовать ассоциативные списки без использования слайсов?
Остаётся только один вариант — разработать собственный API для итерации, что-то вроде метода Next(). До сих пор программисты Go занимались именно этим, и, как и следовало ожидать, было предложено множество различных решений. С выходом Go 1.23 мы наконец можем остановиться на едином, идиоматическом подходе.
В этой статье я покажу, как использовать range-over-functions для создания итератора для AssocList. В следующем разделе мы обсудим, как он работает. Мы начнём с добавления метода в AssocList с определённой сигнатурой. Хотя это может быть и отдельная функция, для такого контейнера, как AssocList, метод выглядит более естественным:
func (al *AssocList[K, V]) All() iter.Seq2[K, V] {
return func(yield func(K, V) bool) {
for _, p := range al.lst {
if !yield(p.key, p.value) {
return
}
}
}
}
Seq2 - вспомогательный тип, определенный в новом пакете iter стандартной библиотеки:
type Seq[V any] func(yield func(V) bool)
type Seq2[K, V any] func(yield func(K, V) bool)
Мы можем использовать новый метод All следующим образом:
func main() {
al := &AssocList[int, string]{}
al.Add(10, "ten")
al.Add(20, "twenty")
al.Add(5, "five")
for k, v := range al.All() {
fmt.Printf("key=%v, value=%v\n", k, v)
}
}
// Prints:
//
// key=10, value=ten
// key=20, value=twenty
// key=5, value=five
Магия! Мы просто итерируем наш контейнер с помощью стандартного цикла for-range; как это работает?
Range over functions - механика
Во-первых, обратите внимание, что All - это метод, который возвращает функцию. Чтобы быть пригодным для итерации, значение должно быть функцией с одной из этих сигнатур:
func(yield func() bool)
func(yield func(V) bool)
func(yield func(K, V) bool)
Каждая из них представляет собой функцию, принимающую в качестве параметра другую функцию. Параметр функции называется yield по соглашению - само имя не имеет значения. yield может иметь 0, 1 или 2 параметра и возвращает bool.
Количество параметров yield непосредственно отображается на левую часть цикла for-range с максимальным количеством возвращаемых значений, например:
for x, y := range ... // two parameters
for x := range ... // one parameter
for range ... // no parameters
Благодаря новой функциональности итераций, функции цикла for-range будут автоматически преобразовываться компилятором.
Давайте разберемся с этим на примере нашего итератора. Вот преобразование:
Теперь, когда мы рассмотрели определение метода AssocList.All, становится понятно, как работает итерация. В этом методе используется цикл, который перебирает элементы в структуре данных, передавая каждый из них в функцию yield, которую компилятор вставляет в тело исходного цикла range.
Это самый простой пример, поскольку он никак не меняет поток управления. В более сложных случаях компилятор применяет более сложные преобразования; например, break в теле цикла for-range преобразуется в возврат false из функции yield, что приводит к остановке итерации. continue преобразуется в ранний возврат true; еще больше работы требуется для операторов goto, ранних возвратов, паники, defer и так далее. Для получения подробной информации посмотрите на transformation implementing the proposal.
Раннее прекращение итерации
Ранние остановки - существенная особенность range over functions. Вспомните наш метод AssocList.All:
func (al *AssocList[K, V]) All() iter.Seq2[K, V] {
return func(yield func(K, V) bool) {
for _, p := range al.lst {
if !yield(p.key, p.value) {
return
}
}
}
}
Проверка возврата false из yield и его использование для раннего возврата очень важны. Рассмотрим этот цикл:
for k, v := range al.All() {
if strings.HasPrefix(v, "fi") {
fmt.Println("found bad value, aborting!")
break
}
fmt.Printf("key=%v, value=%v\n", k, v)
}
Как уже говорилось, break преобразуется в return false, когда тело цикла преобразуется в функцию yield. Как только мы встретили “bad value”, мы не хотим продолжать итерацию, и поэтому функция итератора тоже должна выйти раньше.
Это крайне важно, поскольку итерация может быть затратной по времени, иметь побочные эффекты (например, чтение из устройств ввода-вывода) или же итератор может быть бесконечным.
Fibonacci numbers
В качестве примера бесконечного итератора напишем генератор чисел Фибоначчи:
func genFib() iter.Seq[int] {
return func(yield func(int) bool) {
a, b := 1, 1
for {
if !yield(a) {
return
}
a, b = b, a+b
}
}
}
Эта функция возвращает iter.Seq, потому что итерация происходит над одиночными значениями. Это означает, что связанный с ней цикл for-range вернет не более одного значения. Вот как мы можем его использовать:
func main() {
for p := range genFib() {
fmt.Println(p)
if p > 1000 {
break
}
}
}
Он будет выводить числа Фибоначчи до тех пор, пока не встретит первое, превышающее 1000. Очевидно, что такой итератор не имеет «конца», поскольку количество чисел Фибоначчи бесконечно.
На самом деле, цикл for в функции, возвращаемой методом genFib, не имеет условия завершения. Он завершается только тогда, когда метод yield возвращает false. Это происходит, когда в условии if p > 1000 срабатывает оператор break.
Рекурсивные итераторы
До сих пор все рассмотренные примеры итераторов были линейными. Это значит, что итератор представлял собой цикл, который последовательно выдавал все значения. Однако существуют и нелинейные схемы итерации. Например, давайте рассмотрим итерацию по двоичному дереву:
type Tree[E any] struct {
val E
left, right *Tree[E]
}
func (t *Tree[E]) Inorder() iter.Seq[E] {
return func(yield func(E) bool) {
t.push(yield)
}
}
func (t *Tree[E]) push(yield func(E) bool) bool {
if t == nil {
return true
}
return t.left.push(yield) && yield(t.val) && t.right.push(yield)
}
Обратите внимание, что в этом коде нет цикла, а итерация осуществляется с помощью рекурсии. Мы используем вспомогательный рекурсивный метод push. Этот метод необходим, поскольку мы хотим, чтобы push возвращал логическое значение. Это значение указывает, должна ли итерация остановиться, и передаётся вверх по стеку вызовов рекурсии. Итерация завершится только тогда, когда yield вернёт false для какого-либо значения.
Вот in-order итератор дерева в действии:
// Create a sample tree:
//
// 10
// / \
// 20 40
// / \
// 30 39
tt := &Tree[int]{
10,
&Tree[int]{
20,
&Tree[int]{30, nil, nil},
&Tree[int]{39, nil, nil}},
&Tree[int]{40, nil, nil},
}
for v := range tt.Inorder() {
fmt.Println(v)
}
// Prints:
// 30
// 20
// 39
// 10
// 40
Дополнительные примеры итераторов
bufio.Scanner - удобный тип для итерации по строкам текста.
Канонический способ итерации по всем строкам stdin:
scanner := bufio.NewScanner(os.Stdin)
for scanner.Scan() {
fmt.Println(scanner.Text())
}
if err := scanner.Err(); err != nil {
fmt.Fprintln(os.Stderr, "reading standard input:", err)
}
Это прекрасный пример особого метода итерации, который был создан разработчиками языка Go задолго до того, как в нём появилась полноценная поддержка итераторов. В этом подходе нет ничего плохого — он понятен и отлично работает. Однако без единого стандарта для итераций существует множество различных способов её реализации, и чтобы узнать, как правильно это сделать, всегда приходится обращаться к документации.
С помощью недавно появившейся функции range-over-functions мы можем написать итератор, который будет работать в цикле. Я продемонстрирую это, не изменяя стандартную библиотеку:
type myScanner struct {
s *bufio.Scanner
}
func newScanner(r io.Reader) *myScanner {
s := bufio.NewScanner(r)
return &myScanner{
s: s,
}
}
func (ms *myScanner) All() iter.Seq[string] {
return func(yield func(string) bool) {
for ms.s.Scan() {
if !yield(ms.s.Text()) {
return
}
}
}
}
func (ms *myScanner) Err() error {
return ms.s.Err()
}
Можно использовать его следующим образом:
scanner := newScanner(os.Stdin)
for line := range scanner.All() {
fmt.Println("got line:", line)
}
if err := scanner.Err(); err != nil {
log.Fatalf("reading stdin: %v", err)
}
Возможно, в будущем в типе Scanner появится метод All.
Еще один пример - это функция для слайсов:
func Backward[E any](x []E) iter.Seq2[int, E] {
return func(yield func(int, E) bool) {
i := len(x) - 1
for i >= 0 && yield(i, x[i]) {
i--
}
}
}
Использование:
func main() {
s := []int{5, 6, 7, 8, 11, 22}
for _, e := range Backward(s) {
fmt.Println(e)
}
}
// Prints:
// 22
// 11
// 8
// 7
// 6
// 5
Однако вам не нужно писать собственную функцию - она уже добавлена в стандартный пакет slices, наряду с некоторыми другими полезными функциями итераторов (ищите в документации).
push vs pull итераторы
Мне нравится эта новая возможность — она значительно упрощает программирование на Go, добавляя при этом лишь небольшую дополнительную сложность. Я начал собирать небольшую коллекцию общих структур данных Go, и большинство пакетов в этой коллекции теперь реализуют итераторы.
Если вы ознакомитесь с предложением и другими документами, связанными с итераторами, то вскоре столкнетесь с терминами «push» и «pull» итераторы. Что же они означают?
Проще говоря, итераторы «push» передают свои значения в функцию, которую они принимают. В этом посте итераторы являются итераторами «push» — они берут функцию yield и, вызывая её, генерируют значения. Возвращаемое значение yield затем используется для определения того, должен ли итератор продолжать генерировать значения или остановиться.
«Pull» итераторы работают несколько иначе. Pull-итератор представляет собой функцию, которую можно вызывать несколько раз, и её сигнатура выглядит примерно так:
func() (value T, cont bool)
Где value — это значение, сгенерированное итератором, которое указывает, готов ли он предоставить больше значений или завершил свою работу.
Поток управления в итераторах push и pull кардинально различается. Итераторы push «управляют» процессом итерации, передавая значения в функцию до тех пор, пока не закончат свою работу или пока их явно не попросят остановиться. Итераторы pull, с другой стороны, управляются извне и должны сохранять свое состояние между вызовами. Оба типа итераторов имеют свои преимущества и могут быть использованы в различных сценариях.
В стандартную библиотеку также была добавлена функция iter.Pull для преобразования итераторов из push в pull.
Комментарии в Telegram-группе!