Iteradores

Em Go, a palavra-chave usada para iterar sobre estruturas de dados específicas é for range. Nos capítulos anteriores, já introduzimos algumas de suas aplicações. Ela só pode ser usada em algumas estruturas de dados integradas da linguagem:

• arrays
• slices
• strings
• map
• chan
• valores inteiros

Dessa forma, o uso é muito inflexível e sem extensibilidade, com quase nenhum suporte para tipos personalizados. No entanto, felizmente, após a atualização para a versão go1.23, a palavra-chave for range passou a suportar range over func, tornando possível a criação de iteradores personalizados.

Conhecendo

Vamos conhecer os iteradores através de um exemplo. Vocês se lembram do exemplo de closure para calcular a sequência de Fibonacci apresentado na seção de funções? Seu código de implementação é o seguinte:

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
  }
}

Podemos transformá-lo em um iterador, como mostrado abaixo. Podemos ver que a quantidade de código diminuiu um pouco:

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
    }
  }
}

Os iteradores de Go são do estilo range over func. Podemos usá-los diretamente com a palavra-chave for range, o que é mais conveniente do que antes:

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

Saída:

0
1
1
2
3
5
8
13

Como mostrado acima, um iterador é uma função closure que aceita uma função de callback como parâmetro. Você pode até ver a palavra yield no código. Quem já programou em Python deve estar familiarizado com ela, pois é muito semelhante aos geradores do Python. Os iteradores de Go não adicionaram nenhuma palavra-chave ou recurso de sintaxe novo. No exemplo acima, yield é apenas uma função de callback, não uma palavra-chave. O nome foi escolhido oficialmente para facilitar o entendimento.

Iteradores do Tipo Push

Sobre a definição de iteradores, podemos encontrar a seguinte explicação na biblioteca iter:

An iterator is a function that passes successive elements of a sequence to a callback function, conventionally named yield.

Um iterador é uma função que passa elementos sucessivos de uma sequência para uma função de callback, convencionalmente chamada de yield.

Podemos entender claramente que um iterador é uma função que aceita uma função de callback como parâmetro e, durante a iteração, passa os elementos da sequência um a um para a função de callback yield. No exemplo anterior, usamos o iterador da seguinte forma:

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

De acordo com a definição oficial, o uso do iterador Backward no exemplo acima é equivalente a este código:

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

O corpo do loop é a função de callback yield do iterador. Quando a função retorna true, o iterador continua a iteração; caso contrário, ele para.

Além disso, a biblioteca padrão iter também define o tipo de iterador iter.Seq, que é do tipo função:

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

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

A função de callback de iter.Seq aceita apenas um parâmetro, então durante a iteração for range há apenas um valor de retorno:

for v := range iter {
  // body
}

A função de callback de iter.Seq2 aceita dois parâmetros, então durante a iteração for range há dois valores de retorno:

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

Embora a biblioteca padrão não defina um Seq com 0 parâmetros, isso também é totalmente permitido, equivalente a:

func(yield func() bool)

O uso seria assim:

for range iter {
  // body
}

O número de parâmetros da função de callback só pode ser de 0 a 2; mais do que isso não compilará.

Em resumo, o corpo do loop em for range é a função de callback yield do iterador. O for range retorna quantos valores, a função yield terá esses parâmetros de entrada. Em cada rodada de iteração, o iterador chama a função yield, ou seja, executa o código no corpo do loop, passando ativamente os elementos da sequência para a função yield. Esse tipo de iterador que passa ativamente os elementos é geralmente chamado de iterador do tipo push (pushing iterator). Um exemplo típico é o foreach em outras linguagens, como em JavaScript:

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

Em Go, a manifestação é que os elementos iterados são retornados por range:

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

Em algumas linguagens (como Java), há outro nome para isso: processamento de fluxo de dados.

Como o código no corpo do loop é passado para o iterador como uma função de callback, e provavelmente é uma função closure, o Go precisa fazer com que uma função closure se comporte como um segmento de código de loop comum ao executar palavras-chave como defer, return, break, goto. Vamos considerar algumas situações.

Por exemplo, ao retornar dentro de um loop de iterador, como lidar com esse return na função de callback yield?

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

Não é possível simplesmente fazer return na função de callback, pois isso apenas faria a iteração parar, sem alcançar o efeito de retorno:

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

Outro exemplo é usar defer em um loop de iterador:

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

Também não é possível usar defer diretamente na função de callback, pois isso faria a chamada adiada ser executada assim que a função de callback terminasse:

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

O mesmo se aplica a outras palavras-chave como break, continue, goto. Felizmente, o Go já cuidou dessas situações para nós. Podemos apenas usar sem nos preocupar. Se tiver interesse, pode navegar pelo código-fonte em rangefunc/rewrite.go.

Iteradores do Tipo Pull

O iterador do tipo push (pushing iterator) é controlado pelo iterador, e o usuário obtém os elementos passivamente. Por outro lado, o iterador do tipo pull (pulling iterator) é controlado pelo usuário, que ativamente obtém os elementos da sequência. Geralmente, iteradores do tipo pull têm funções específicas como next() e stop() para controlar o início ou fim da iteração. Pode ser uma closure ou uma estrutura:

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

Como mostrado acima, o Scanner usa o método Text() para obter a próxima linha de texto do arquivo e o método Scan() para indicar se a iteração terminou. Este também é um padrão de iterador do tipo pull. O Scanner usa uma estrutura para registrar o estado, enquanto o iterador do tipo pull definido na biblioteca iter usa uma closure para registrar o estado. Através das funções iter.Pull ou iter.Pull2, podemos converter um iterador do tipo push padrão em um iterador do tipo pull. A diferença entre iter.Pull e iter.Pull2 é que o segundo tem dois valores de retorno. Suas assinaturas são:

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())

Ambos aceitam um iterador como parâmetro e retornam duas funções next() e stop(), usadas para controlar a continuação e parada da iteração:

func next() (V, bool)

func stop()

next retorna o elemento iterado e um valor booleano indicando se o valor atual é válido. Quando a iteração termina, a função next retorna o valor zero do elemento e false. A função stop encerra o processo de iteração. Quando o chamador não estiver mais usando o iterador, deve usar a função stop para encerrar a iteração. A propósito, chamar a função next do mesmo iterador em múltiplas goroutines é uma prática errada, pois não é seguro para concorrência.

Vamos demonstrar com um exemplo. Sua função é transformar o iterador de Fibonacci anterior em um iterador do tipo pull:

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

Saída:

0
1
1
2
3
5
8
13
21
34

Assim, podemos controlar manualmente a lógica da iteração através das funções next e stop. Você pode achar que isso é desnecessário. Se for fazer assim, por que não usar diretamente a versão closure original? O controle da iteração seria o mesmo. O uso da closure seria assim:

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

Processo de conversão: closure → iterador → iterador do tipo pull. O uso de closures e iteradores do tipo pull é muito semelhante, a ideia é a mesma. O último ainda pode ter desempenho prejudicado por vários processamentos. Honestamente, isso é realmente desnecessário em muitos casos. Seu cenário de aplicação realmente não é muito comum. No entanto, iter.pull existe para iter.Seq, ou seja, para converter iteradores do tipo push em iteradores do tipo pull. Se você apenas quer um iterador do tipo pull e ainda implementa um iterador do tipo push especificamente para fazer essa conversão, considere a complexidade e o desempenho da sua própria implementação. Como no exemplo da sequência de Fibonacci, demos uma volta e voltamos ao ponto original. A única vantagem pode ser a conformidade com a especificação oficial de iteradores.

Tratamento de Erros

E se ocorrer um erro durante a iteração? Podemos passá-lo para a função yield para que o for range retorne, permitindo que o chamador o trate, como no exemplo do iterador de linhas abaixo:

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

Vale notar que o iterador ScanLines é de uso único. Depois que o arquivo é fechado, não pode ser usado novamente.

Podemos ver que seu segundo valor de retorno é do tipo error. O uso é assim:

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

Isso torna o tratamento igual ao tratamento de erros comum. O mesmo se aplica a iteradores do tipo 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)
}

Se ocorrer um panic, basta usar recovery como de costume:

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)
}

O mesmo se aplica a iteradores do tipo pull, então não vamos demonstrar aqui.

Biblioteca Padrão

Muitas bibliotecas padrão também suportam iteradores. As mais usadas são as bibliotecas padrão slices e maps. Abaixo, apresentamos algumas funções práticas.

slices.All

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

slices.All converte um slice em um iterador de slice:

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

Saída:

0 1
1 2
2 3
3 4
4 5

slices.Values

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

slices.Values converte um slice em um iterador de slice, mas sem índice:

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

Saída:

1
2
3
4
5

slices.Chunk

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

A função slices.Chunk retorna um iterador que empurra slices de n elementos para o chamador:

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

Saída:

[1 2]
[3 4]
[5]

slices.Collect

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

A função slices.Collect coleta um iterador de slice em um slice:

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

Saída:

[1 2 3 4 5]

maps.Keys

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

maps.Keys retorna um iterador que itera sobre todas as chaves de um map. Combinado com slices.Collect, pode coletar diretamente em um slice:

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

Saída:

[three one two]

Como maps não são ordenados, a saída não é fixa.

maps.Values

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

maps.Values retorna um iterador que itera sobre todos os valores de um map. Combinado com slices.Collect, pode coletar diretamente em um slice:

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

Saída:

[3 1 2]

Como maps não são ordenados, a saída não é fixa.

maps.All

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

maps.All pode converter um map em um iterador de map:

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

Geralmente não é usado diretamente assim, mas em combinação com outras funções de processamento de fluxo de dados.

maps.Collect

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

maps.Collect pode coletar um iterador de map em um map:

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

A função collect geralmente é usada como função terminal no processamento de fluxo de dados.

Chamadas em Cadeia

Através das funções fornecidas pela biblioteca padrão acima, podemos combiná-las para processar fluxos de dados, como ordenar um fluxo de dados:

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

Os iteradores de Go usam closures, então só podemos aninhar chamadas de função assim. Não há como fazer chamadas em cadeia nativamente. Quando a cadeia de chamadas fica longa, a legibilidade fica comprometida. Mas podemos usar estruturas para registrar o iterador e assim implementar chamadas em cadeia.

demo

Um demo simples de chamadas em cadeia é mostrado abaixo, incluindo funções comuns como Filter, Map, Find, Some, etc:

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) {
      // Reorganiza o índice
      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)}
}

Agora podemos processar através de chamadas em cadeia. Veja alguns casos de uso:

Processar valores de elementos

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)
  }
}

Saída:

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

Encontrar um valor específico

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)
}

Saída:

3

Preencher slice

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

Saída:

[6 6 6 6 6]

Filtrar elementos

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)
  }
}

Saída:

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

Infelizmente, Go ainda não suporta funções anônimas abreviadas, como as arrow functions em JavaScript, Rust e Java. Caso contrário, as chamadas em cadeia poderiam ser ainda mais concisas e elegantes.

Desempenho

Como o Go faz muitos processamentos nos iteradores, seu desempenho certamente é inferior ao loop for range nativo. Vamos testar a diferença de desempenho usando a iteração mais simples de um slice, dividindo em:

• Loop for nativo
• Iterador do tipo push
• Iterador do tipo pull

O código de teste é mostrado abaixo, com slice de comprimento 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)
  }
}

Resultados do teste:

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

Podemos ver pelos resultados que o iterador do tipo push não é muito diferente do loop for range nativo, mas o iterador do tipo pull é quase duas ordens de magnitude mais lento que os dois anteriores. Ao usar, considere sua situação real.

Resumo

Assim como com os genéricos, os iteradores de Go também são controversos. Algumas pessoas argumentam que os iteradores introduzem complexidade excessiva, violando a filosofia de simplicidade do Go. Com muito código closure de iteradores assim, a depuração pode se tornar difícil, e a leitura ainda mais irritante.

Você pode ver discussões acaloradas sobre iteradores em muitos lugares:

• Why People are Angry over Go 1.23 Iterators - Uma avaliação de um desenvolvedor estrangeiro sobre iteradores, vale a pena ler
• golang/go · Discussion #56413 - Discussão na comunidade iniciada por rsc, muitas pessoas expressaram seus pontos de vista

Olhando racionalmente para os iteradores de Go, eles realmente tornam a escrita de código mais conveniente, especialmente ao lidar com tipos de slice. Mas ao mesmo tempo, introduzem alguma complexidade, e a legibilidade do código de iteradores pode ser reduzida. No geral, acredito que esse é realmente um recurso útil.