Тренды

Обзор итераторов в Go

03.03.2024

Введение

В Go 1.22 ожидается появление расширений оператора for-range как для функций типа int (range-over-int), так и для функций-итераторов (range-over-func). Кроме того, продолжается работа по достижению консенсуса насчет библиотеки итераторов и корутин.

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

Ниже указан статус каждой функции по состоянию на 5 декабря 2023 года:

range-over-int: будет добавлена в Go 1.22
range-over-func: будет добавлена в Go 1.22 в рамках GOEXPERIMENT=rangefunc (ожидается продолжение пересмотра)
iterator library (библиотека итераторов): будет добавлена в Go 1.22 в рамках GOEXPERIMENT=rangefunc (в настоящее время продолжаются попытки достичь консенсуса по спецификации)
coroutines (корутины): будут добавлены во внутренний пакет в Go 1.22 (решение о внешнем API пока не принято)

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

Зачем нужны итераторы в Go?

Команда Go очень консервативна в отношении добавления в язык новых возможностей, даже тех, которые считаются само собой разумеющимися в других “модных” (популярных) языках. В чем же уникальность итераторов?

Обеспечение согласованности

Циклы for-range можно использовать для итерации по определенным встроенным типам, но другие типы не так интуитивно понятны. bufio представляет несколько шаблонов итерации.

// bufio.Reader
r := bufio.NewReader(...)
for {
    line, _ , err := r.ReadLine()
    if err != nil {
        break
    }
    // какие-либо действия 
}


// bufio.Scanner
scanner := bufio.NewScanner(...)
for scanner.Scan() {
    line := scanner.Text()
    // какие-либо действия
}

Разработка на основе дженериков

Дженерики позволяют определять пользовательские типы контейнеров, но нет никаких рекомендаций по итерации. Можно ли сказать, что приведенный ниже API является идиоматическим или нет?

tree := radix.NewTree[int]()
for ptr := tree.Traverse(); ptr.HasNext(); ptr = ptr.Next() {
    // какие-либо действия
}

Возможность повторного использования, композиции и повышения производительности

Написание циклов по ходу работы для фильтрации или преобразования данных в типах контейнеров — обычное дело в кодовых базах Go.

var even []int 
for _, n := range ints {
    if n % 2 == 0 {
        even = append(even, n)
    }
}

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

Итераторы в Go 1.22

Обзор

Рассмотрим спецификацию итераторов в Go 1.22 с установкой GOEXPERIMENT=rangefunc, начиная с определения типа для итератора с индивидуальными возвращаемыми значениями.

// Seq - это итератор по последовательностям отдельных значений.
// При вызове seq(yield) seq вызывает yield(v) для каждого значения v 
// в последовательности, останавливаясь раньше, если yield возвращает false.
type Seq[V any] func(yield func(V) bool)

Итератор — это функция высшего порядка, которая принимает аргумент функции (yield) с сигнатурой func(V) bool. Вот ключевые особенности этой функции.

Итератор (функция Seq) управляет итерацией.
Итератор передает каждое значение обратно вызывающей функции, вызывая yield (итератор также направляет поток управления обратно к вызывающей функции, вызывая yield).
Вызывающая функция (или цикл for-range) определяет, как каждое значение будет обработано в функции yield.
Вызывающая функция может остановить итерацию раньше времени, вернув false из yield.

Синтаксический сахар

Функции Seq можно использовать в операторах for-range.

mySeq := func(yield func(n int) bool) { ... }

for v := range mySeq {
    // какие-либо действия с v
}

Компилятор переписывает циклы, как показано ниже (см. rewrite.go).

mySeq(func(n int) bool {
    if breakCondition {
        return false // прерывание
    }
    // какие-либо действия с n
    return true // продолжение
})

Возвращаемое значение yield эквивалентно continue (true) и break (false) соответственно внутри цикла for-range.

Реализация пользовательского итератора

Теперь у нас есть список требований для реализации итератора:

Реализовать сигнатуру Seq.
Управлять итерацией последовательности значений.
Передавать каждое значение вызывающей функции через yield.
Возвращать значение раньше, если yield возвращает false.

Реализуем итератор All, который возвращает все элементы из пользовательского типа slice (среза) secret.Ints.

package secret

// Int - это секретный int, который может быть скрыт (не виден).
type Int struct {
    Val     int
    Visible bool
}

type Ints []Int

Согласно первому требованию, надо корректно реализовать сигнатуру Seq.

func (ii Ints) All(yield func(Int) bool) { ... }

Теперь нужно перейти к управлению итерацией элементов среза, то есть выполнить цикл по ним.

func (ii Ints) All(yield func(Int) bool) {
    for _, n := range ii { ... }
}

Наконец, необходимо передать каждое значение обратно вызывающей функции через yield, завершая работу, когда yield возвращает false.

func (ii Ints) All(yield func(Int) bool) {
    for _, s := range ii {
        if !yield(s) {
            return
        }
    }
}

Так можно написать итератор в Go 1.22. Попробуем это сделать.

ints := secret.Ints{ {1, true}, {2, false}, {3, true} }

for n := range ints.All {
    fmt.Println(n)
}
// {1 true}\n {2 false}\n {3 true}\n

rewrite.go должен преобразовать цикл в нечто вроде следующего:

ints.All(func(n Int) bool {
    fmt.Println(n)
    return true 
})

Дополнительные сигнатуры

Seq2 тоже будет добавлен в Go 1.22. Он работает так же, как и Seq, но выдает не одно, а два значения.

Вот итератор Seq2 для secret.Ints, который возвращает индекс и элемент.

func (ii Ints) AllWithIndex(yield func(int, Int) bool) {
    for i, s := range ii {
        if !yield(i, s) {
            return
        }
    }
}

...

for i, n := range ints.AllWithIndex {
    fmt.Println(i, n)
}
// 0 {1 true}\n 1 {2 false}\n 2 {3 true}\n

Краткое описание итераторов

Проявив немного фантазии, вы можете определить другие итераторы, например ints.ReverseAll или ints.Visible. В репозитории на GitHub есть несколько примеров с использованием списков и деревьев.

Что мы получаем от Seq/Seq2, так это последовательный шаблон проектирования для итерации по последовательности значений в Go. Однако некоторых может не устроить синтаксис или то, как должна функционировать обработка ошибок. Надеемся, что Go 1.23 предложит окончательную спецификацию, которая удовлетворит всех.

Библиотека итераторов

Чтобы сделать итераторы более удобными, в настоящее время обсуждается предложение об усовершенствовании библиотеки итераторов. Цель — добавить в стандартную библиотеку такие функции, как Filter, Map, Zip и Reduce. Вот пример с secret.Ints.

ints := secret.Ints{ {1, true}, {2, false}, {3, true} }

filter := iter.Filter(func(s secret.Int) bool {
    return s.Visible
}, ints.All)

mapped := iter.Map(func(s secret.Int) string {
    return strconv.Itoa(s.Val) + "!"
}, filter)

result := iter.Reduce(nil, func(sum []string, s string) []string {
    return append(sum, s)
}, mapped)

fmt.Println(result) // ["1!", "3!"]

Возможно, это не сразу понятно, но из реализации Filter видно, что данная функция не выделяет срез, а обертывает ints.All (seq).

// Фильтр возвращает итератор по последовательности, включающий
// только те значения v, для которых f(v) истинно.
func Filter[V any](f func(V) bool, seq Seq[V]) Seq[V] {
    return func(yield func(V) bool) {
        for v := range seq {
            if f(v) && !yield(v) {
                return
            }
        }
    }
}

Map работает аналогичным образом. Несмотря на множество цепочек операций, итерация выполняется ровно len(ints). И никаких промежуточных выделений срезов.

Существует цепочка вызовов yield, запускаемая из ints.All, которая оперирует значениями по одному за раз. Map/Reduce не будет видеть значения, не прошедшие условие Filter, что сводит лишнюю работу к минимуму.

Обратите внимание: цепочка вызовов (ints.All(…).Filter(…)) невозможна из-за того, что параметры типа не поддерживаются в методах. Но тем, кто считает синтаксис Reduce уродливым, может быть интересно это предложение, предоставляющее более лаконичные альтернативы.

result := slices.Collect(mapped)

Вывод

Итераторы обещают стать крупнейшим событием в Go со времен введения дженериков. Они могут изменить способ написания кода на Go. Пока еще не все ясно, но, надеюсь, этот пост пролил свет на то, как должны выглядеть итераторы и как может расшириться стандартная библиотека для их поддержки.

Обзор итераторов в Go

Введение

Зачем нужны итераторы в Go?

Обеспечение согласованности

Разработка на основе дженериков

Возможность повторного использования, композиции и повышения производительности

Итераторы в Go 1.22

Обзор

Синтаксический сахар

Реализация пользовательского итератора

Дополнительные сигнатуры

Краткое описание итераторов

Библиотека итераторов

Вывод

Читайте также

Введение в потоки Redis

Python Django: контактная форма с автоматической отправкой Email

Создание компонента Timer с React и Bit

Тесты

Насколько хорошо вы разбираетесь в Node.js?

Насколько хорошо вы разбираетесь в Go?

Насколько хорошо вы знаете С#?