Iteratori

In Go, la parola chiave utilizzata per iterare su strutture dati specifiche è for range. Nei capitoli precedenti sono stati presentati alcuni suoi utilizzi. Può essere applicata solo ad alcune strutture dati built-in del linguaggio:

• Array
• Slice
• Stringhe
• Map
• Channel
• Valori interi

Questo rende l'utilizzo molto flessibile e privo di estensibilità, quasi non supporta i tipi personalizzati. Fortunatamente, dopo l'aggiornamento alla versione Go 1.23, la parola chiave for range supporta range over func, rendendo possibile la creazione di iteratori personalizzati.

Conoscenza

Di seguito è riportato un esempio per comprendere inizialmente gli iteratori. Non so se ricordate l'esempio della risoluzione della sequenza di Fibonacci tramite closure nella sezione sulle funzioni. La sua implementazione è la seguente:

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

Possiamo trasformarlo in un iteratore, come mostrato di seguito. Si può vedere che la quantità di codice è ridotta:

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

L'iteratore in Go è in stile range over func. Possiamo utilizzarlo direttamente con la parola chiave for range, ed è anche più comodo da usare rispetto a prima:

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

Output:

0
1
1
2
3
5
8
13

Come mostrato sopra, un iteratore è una funzione closure che accetta una funzione di callback come parametro. Si può persino vedere la parola yield, familiare a chi ha scritto Python. È simile ai generatori in Python. Gli iteratori Go non aggiungono nuove parole chiave o funzionalità sintattiche. Nell'esempio sopra, yield è solo una funzione di callback, non una parola chiave. Il nome è stato scelto dal team ufficiale per facilitare la comprensione.

Iteratori Push-Style

Per quanto riguarda la definizione di iteratore, possiamo trovare la seguente spiegazione nella libreria iter:

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

Un iteratore è una funzione che passa gli elementi successivi di una sequenza a una funzione di callback, convenzionalmente chiamata yield.

Da ciò possiamo capire chiaramente che un iteratore è una funzione che accetta una funzione di callback come parametro. Durante il processo di iterazione, gli elementi della sequenza vengono passati uno per uno alla funzione di callback yield. Nell'esempio precedente, utilizziamo l'iteratore come segue:

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

Secondo la definizione ufficiale, l'uso dell'iteratore Backward nell'esempio sopra è equivalente al seguente codice:

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

Il corpo del ciclo è la funzione di callback yield dell'iteratore. Quando la funzione restituisce true, l'iteratore continua l'iterazione, altrimenti si ferma.

Inoltre, la libreria standard iter definisce anche il tipo di iteratore iter.Seq, il cui tipo è una funzione:

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

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

La funzione di callback di iter.Seq accetta solo un parametro, quindi durante l'iterazione for range ha solo un valore di ritorno, come segue:

for v := range iter {
  // body
}

La funzione di callback di iter.Seq2 accetta due parametri, quindi durante l'iterazione for range ci sono due valori di ritorno, come segue:

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

Anche se la libreria standard non definisce Seq con 0 parametri, questo è completamente consentito. Equivale a:

func(yield func() bool)

Utilizzo:

for range iter {
  // body
}

Il numero di parametri della funzione di callback può essere solo da 0 a 2. Se sono di più, la compilazione fallirà.

In breve, il corpo del ciclo in for range è la funzione di callback yield dell'iteratore. Quanti valori restituisce for range, tanti parametri di ingresso avrà la funzione yield. Ad ogni iterazione, l'iteratore chiamerà la funzione yield, ovvero eseguirà il codice nel corpo del ciclo, passando attivamente gli elementi della sequenza alla funzione yield. Questo tipo di iteratore che passa attivamente gli elementi è generalmente chiamato iteratore push-style (pushing iterator). Un esempio tipico è foreach in altri linguaggi, come JavaScript:

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

La forma di espressione in Go è rappresentata dagli elementi iterati restituiti da range:

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

In alcuni linguaggi (come Java) ha un altro nome: elaborazione di flussi di dati.

Poiché il codice nel corpo del ciclo viene passato come funzione di callback all'iteratore, e molto probabilmente è una funzione closure, Go deve far sì che una funzione closure si comporti come un normale segmento di codice del ciclo quando esegue parole chiave come defer, return, break, goto. Consideriamo le seguenti situazioni:

Ad esempio, se si ritorna in un ciclo dell'iteratore, come dovrebbe gestire questo return nella funzione di callback yield?

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

Non è possibile semplicemente fare return nella funzione di callback, poiché questo farebbe solo fermare l'iterazione, senza ottenere l'effetto di ritorno:

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

Un altro esempio è l'uso di defer in un ciclo dell'iteratore:

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

Non si può nemmeno usare defer direttamente nella funzione di callback, poiché in questo modo verrebbe chiamato in ritardo alla fine della funzione di callback:

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

Anche le altre parole chiave break, continue, goto sono simili. Fortunatamente, Go ha già gestito queste situazioni per noi. Possiamo semplicemente usarle senza preoccuparcene per ora. Se sei interessato, puoi consultare il codice sorgente in rangefunc/rewrite.go.

Iteratori Pull-Style

L'iteratore push-style (pushing iterator) è controllato dalla logica di iterazione dell'iteratore, con l'utente che riceve passivamente gli elementi. Al contrario, l'iteratore pull-style (pulling iterator) è controllato dall'utente, che recupera attivamente gli elementi della sequenza. In generale, gli iteratori pull-style avranno funzioni specifiche come next(), stop() per controllare l'inizio o la fine dell'iterazione. Possono essere una closure o una struct.

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

Come mostrato sopra, Scanner ottiene la riga successiva del file tramite il metodo Text() e utilizza il metodo Scan() per indicare se l'iterazione è terminata. Questo è anche un modello di iteratore pull-style. Scanner utilizza una struct per registrare lo stato, mentre l'iteratore pull-style definito nella libreria iter utilizza una closure per registrare lo stato. Possiamo convertire un iteratore push-style standard in un iteratore pull-style tramite le funzioni iter.Pull o iter.Pull2. La differenza tra iter.Pull e iter.Pull2 è che quest'ultimo ha due valori di ritorno. Le firme sono le seguenti:

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

Entrambe accettano un iteratore come parametro e restituiscono due funzioni next() e stop(), utilizzate per controllare la continuazione e l'arresto dell'iterazione:

func next() (V, bool)

func stop()

next restituisce l'elemento iterato e un valore booleano che indica se il valore corrente è valido. Quando l'iterazione termina, la funzione next restituisce il valore zero dell'elemento e false. La funzione stop termina il processo di iterazione. Quando il chiamante non utilizza più l'iteratore, deve utilizzare la funzione stop per terminare l'iterazione. A proposito, chiamare la funzione next dello stesso iteratore da più goroutine è errato, poiché non è concurrent-safe.

Di seguito è riportato un esempio che dimostra come trasformare l'iteratore di Fibonacci precedente in un iteratore pull-style:

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

Output:

0
1
1
2
3
5
8
13
21
34

In questo modo possiamo controllare manualmente la logica di iterazione tramite le funzioni next e stop. Potresti pensare che questo sia superfluo. Se vuoi farlo, perché non usare direttamente la versione closure originale? Anche quella può controllare l'iterazione da sola. L'uso della closure è il seguente:

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

Processo di conversione: closure → iteratore → iteratore pull-style. L'uso della closure e dell'iteratore pull-style è quasi lo stesso, hanno la stessa idea. Quest'ultimo subirà anche un deterioramento delle prestazioni a causa di vari trattamenti. Onestamente, questo è davvero superfluo. Le sue situazioni di applicazione non sono molte. Tuttavia, iter.Pull esiste per iter.Seq, ovvero per convertire iteratori push-style in iteratori pull-style. Se vuoi solo un iteratore pull-style, considera la complessità e le prestazioni dell'implementazione di un iteratore push-style per la conversione. Come nell'esempio della sequenza di Fibonacci, si fa un giro e si torna al punto di partenza. L'unico vantaggio è che è conforme alle specifiche ufficiali degli iteratori.

Gestione degli Errori

Cosa fare se si verifica un errore durante l'iterazione? Possiamo passarlo alla funzione yield per farlo restituire da for range, lasciando che il chiamante lo gestisca. Come in questo esempio di iteratore di righe:

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 la pena notare che l'iteratore ScanLines è monouso. Non può essere riutilizzato dopo la chiusura del file.

Si può vedere che il suo secondo valore di ritorno è di tipo error. Utilizzo:

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

La gestione è simile alla normale gestione degli errori. Lo stesso vale per gli iteratori pull-style:

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 si verifica un panic, basta usare recover come al solito:

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

Lo stesso vale per gli iteratori pull-style, non sarà dimostrato qui.

Libreria Standard

Molte librerie standard supportano anche gli iteratori. Le più comuni sono le librerie standard slices e maps. Di seguito sono presentate alcune funzionalità pratiche.

slices.All

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

slices.All converte una slice in un iteratore di slice:

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

Output:

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 una slice in un iteratore di slice, ma senza indici:

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

Output:

1
2
3
4
5

slices.Chunk

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

La funzione slices.Chunk restituisce un iteratore che invia al chiamante slice con n elementi:

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

Output:

[1 2]
[3 4]
[5]

slices.Collect

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

La funzione slices.Collect raccoglie un iteratore di slice in una slice:

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

Output:

[1 2 3 4 5]

maps.Keys

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

maps.Keys restituisce un iteratore di tutte le chiavi di una map. Può essere combinato con slices.Collect per raccogliere direttamente in una slice:

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

Output:

[three one two]

Poiché le map non sono ordinate, l'output non è fisso.

maps.Values

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

maps.Values restituisce un iteratore di tutti i valori di una map. Può essere combinato con slices.Collect per raccogliere direttamente in una slice:

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

Output:

[3 1 2]

Poiché le map non sono ordinate, l'output non è fisso.

maps.All

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

maps.All può convertire una map in un iteratore di map:

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

Generalmente non si usa direttamente, ma in combinazione con altre funzioni di elaborazione di flussi di dati.

maps.Collect

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

maps.Collect può raccogliere un iteratore di map in una map:

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

La funzione collect viene generalmente utilizzata come funzione finale nell'elaborazione di flussi di dati.

Chiamate a Catena

Tramite le funzioni fornite dalla libreria standard sopra, possiamo combinarle per elaborare flussi di dati, ad esempio ordinare un flusso di dati:

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

Gli iteratori Go utilizzano closure, quindi possono solo annidare chiamate di funzioni in questo modo. Non possono fare chiamate a catena direttamente. Quando la catena di chiamate diventa lunga, la leggibilità sarà scarsa. Ma possiamo implementare chiamate a catena utilizzando una struct per registrare l'iteratore.

Demo

Una semplice demo di chiamata a catena è mostrata di seguito. Include funzionalità comuni come 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) {
      // Riorganizza l'indice
      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)}
}

Poi possiamo elaborare tramite chiamate a catena. Vediamo alcuni casi d'uso:

Elaborazione dei valori degli elementi

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

Output:

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

Ricerca di un valore specifico

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

Output:

3

Riempimento di una slice

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

Output:

[6 6 6 6 6]

Filtraggio degli elementi

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

Output:

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

Purtroppo Go non supporta ancora le funzioni anonime abbreviate, come le funzioni freccia in JavaScript, Rust o Java. Altrimenti, le chiamate a catena potrebbero essere ancora più concise ed eleganti.

Prestazioni

Poiché Go ha elaborato molte cose per gli iteratori, le loro prestazioni sicuramente non sono pari al ciclo for range nativo. Testiamo le differenze di prestazioni con un semplice ciclo su una slice. Ci sono i seguenti casi:

• Ciclo for nativo
• Iteratore push-style
• Iteratore pull-style

Il codice di test è il seguente. La lunghezza della slice di test è 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)
  }
}

I risultati del test sono i seguenti:

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

Dai risultati possiamo vedere che l'iteratore push-style non è molto diverso dal ciclo for range nativo, ma l'iteratore pull-style è quasi due ordini di grandezza più lento dei primi due. Durante l'uso, ognuno dovrebbe considerare in base alla propria situazione.

Conclusione

Simile ai generici, gli iteratori Go sono anche controversi. Alcuni ritengono che gli iteratori introducano troppa complessità, violando la filosofia della semplicità di Go. Con questo tipo di codice closure negli iteratori, il debug potrebbe essere difficile, e la lettura sarebbe ancora più frustrante.

Puoi vedere discussioni accese sugli iteratori in molti luoghi:

• Why People are Angry over Go 1.23 Iterators, una valutazione sugli iteratori di un fratello straniero, vale la pena leggerla
• golang/go · Discussion #56413, una discussione della comunità avviata da rsc, dove molte persone hanno espresso le proprie opinioni

Guardando razionalmente agli iteratori Go, rendono effettivamente la scrittura del codice più comoda, specialmente quando si trattano tipi slice, ma introducono anche una certa complessità. La leggibilità del codice della parte degli iteratori diminuirà. Tuttavia, nel complesso, ritengo che questa sia una funzionalità pratica.