Itérateurs

En Go, le mot-clé utilisé pour itérer sur des structures de données spécifiques est for range. Dans les chapitres précédents, nous avons déjà présenté certaines de ses applications. Il ne peut agir que sur quelques structures de données intégrées au langage :

• Tableaux
• Slices
• Chaînes de caractères
• Maps
• Canaux (chan)
• Valeurs entières

Cela rend l'utilisation très peu flexible, sans extensibilité, et ne prend presque pas en charge les types personnalisés. Heureusement, après la mise à jour vers la version Go 1.23, le mot-clé for range prend en charge range over func, rendant ainsi possible la création d'itérateurs personnalisés.

Introduction

Commençons par un exemple pour découvrir les itérateurs. Vous souvenez-vous peut-être de l'exemple de la suite de Fibonacci utilisant des fermetures présenté dans la section sur les fonctions exemple de fermeture pour la suite de Fibonacci. Voici son code d'implémentation :

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

Nous pouvons le transformer en itérateur, comme suit. Vous remarquerez que la quantité de code est réduite :

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

Les itérateurs en Go suivent le style range over func. Nous pouvons les utiliser directement avec le mot-clé for range, ce qui est encore plus pratique qu'auparavant :

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

Le résultat est le suivant :

0
1
1
2
3
5
8
13

Comme indiqué ci-dessus, un itérateur est une fonction de fermeture qui accepte une fonction de rappel en tant que paramètre. Vous pouvez même y voir le terme yield, familier pour ceux qui ont écrit en Python. Il est similaire aux générateurs en Python. Les itérateurs en Go n'ajoutent aucun nouveau mot-clé ni fonctionnalité syntaxique. Dans l'exemple ci-dessus, yield n'est qu'une fonction de rappel, ce n'est pas un mot-clé. Le nom a été choisi par l'équipe officielle pour faciliter la compréhension.

Itérateur de type Push (Pushing Iterator)

Concernant la définition d'un itérateur, nous pouvons trouver l'explication suivante dans la bibliothèque iter :

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

Un itérateur est une fonction qui transmet successivement les éléments d'une séquence à une fonction de rappel, conventionnellement nommée yield.

Ce que nous pouvons en déduire clairement, c'est qu'un itérateur est une fonction qui accepte une fonction de rappel en tant que paramètre. Pendant le processus d'itération, les éléments de la séquence sont transmis un par un à la fonction de rappel yield. Dans l'exemple précédent, nous utilisions l'itérateur de la manière suivante :

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

Selon la définition officielle, l'utilisation de l'itérateur Backward ci-dessus équivaut au code suivant :

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

Le corps de la boucle est la fonction de rappel yield de l'itérateur. Lorsque la fonction retourne true, l'itérateur continue l'itération, sinon il s'arrête.

De plus, la bibliothèque standard iter définit également le type d'itérateur iter.Seq, dont le type est une fonction :

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

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

La fonction de rappel de iter.Seq n'accepte qu'un seul paramètre, donc lors de l'itération, for range n'a qu'une seule valeur de retour, comme suit :

for v := range iter {
  // corps
}

La fonction de rappel de iter.Seq2 accepte deux paramètres, donc lors de l'itération, for range a deux valeurs de retour, comme suit :

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

Bien que la bibliothèque standard n'ait pas défini de Seq avec 0 paramètre, cela est également tout à fait autorisé. Cela équivaut à :

func(yield func() bool)

L'utilisation est la suivante :

for range iter {
  // corps
}

Le nombre de paramètres de la fonction de rappel ne peut être que de 0 à 2. Au-delà, la compilation échouera.

En bref, le corps de la boucle dans for range est la fonction de rappel yield de l'itérateur. Le nombre de valeurs retournées par for range détermine le nombre de paramètres de la fonction yield. À chaque tour d'itération, l'itérateur appelle la fonction yield, c'est-à-dire exécute le code du corps de la boucle, et transmet activement les éléments de la séquence à la fonction yield. Ce type d'itérateur qui transmet activement les éléments est généralement appelé itérateur de type push (pushing iterator). Un exemple typique est le foreach dans d'autres langages, comme en JavaScript :

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

En Go, cela se manifeste par les éléments itérés retournés par range :

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

Dans certains langages (comme Java), cela a un autre nom : traitement de flux de données.

Puisque le code du corps de la boucle est transmis à l'itérateur en tant que fonction de rappel, et qu'il s'agit probablement d'une fonction de fermeture, Go doit faire en sorte qu'une fonction de fermeture se comporte comme un corps de boucle ordinaire lors de l'exécution de mots-clés tels que defer, return, break, goto, etc. Réfléchissons aux situations suivantes.

Par exemple, si nous retournons dans une boucle d'itérateur, comment gérer ce retour dans la fonction de rappel yield ?

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

Il est impossible de simplement utiliser return dans la fonction de rappel, car cela arrêterait seulement l'itération sans atteindre l'effet de retour souhaité :

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

Autre exemple, l'utilisation de defer dans une boucle d'itérateur :

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

Il n'est pas possible d'utiliser directement defer dans la fonction de rappel, car cela entraînerait un appel différé à la fin de la fonction de rappel :

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

Les autres mots-clés comme break, continue, goto sont similaires. Heureusement, Go a déjà géré ces situations pour nous, nous n'avons qu'à les utiliser. Nous n'avons pas besoin de nous en soucier pour le moment. Si vous êtes intéressé, vous pouvez consulter le code source dans rangefunc/rewrite.go.

Itérateur de type Pull (Pulling Iterator)

Un itérateur de type push (pushing iterator) est contrôlé par l'itérateur lui-même, où l'utilisateur reçoit passivement les éléments. À l'inverse, un itérateur de type pull (pulling iterator) est contrôlé par l'utilisateur, qui récupère activement les éléments de la séquence. En général, les itérateurs de type pull ont des fonctions spécifiques comme next() et stop() pour contrôler le début ou la fin de l'itération. Il peut s'agir d'une fermeture ou d'une structure.

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

Comme indiqué ci-dessus, Scanner utilise la méthode Text() pour obtenir la ligne suivante du fichier et la méthode Scan() pour indiquer si l'itération est terminée. C'est également un mode d'itérateur de type pull. Scanner utilise une structure pour enregistrer l'état, tandis que les itérateurs de type pull définis dans la bibliothèque iter utilisent des fermetures pour enregistrer l'état. Nous pouvons utiliser les fonctions iter.Pull ou iter.Pull2 pour convertir un itérateur de type push standard en itérateur de type pull. La différence entre iter.Pull et iter.Pull2 est que ce dernier a deux valeurs de retour, avec les signatures suivantes :

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

Elles acceptent toutes deux un itérateur en tant que paramètre et retournent deux fonctions next() et stop() pour contrôler la poursuite et l'arrêt de l'itération.

func next() (V, bool)

func stop()

next retourne l'élément itéré et une valeur booléenne indiquant si la valeur actuelle est valide. Lorsque l'itération se termine, la fonction next retourne la valeur zéro de l'élément et false. La fonction stop termine le processus d'itération. Lorsque l'appelant n'utilise plus l'itérateur, il doit utiliser la fonction stop pour terminer l'itération. Soit dit en passant, il est erroné que plusieurs goroutines appellent la fonction next du même itérateur, car il n'est pas concurrentiellement sûr.

Voici un exemple qui transforme l'itérateur de Fibonacci précédent en itérateur de type pull :

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

Résultat :

0
1
1
2
3
5
8
13
21
34

Ainsi, nous pouvons contrôler manuellement la logique d'itération via les fonctions next et stop. Vous pourriez penser que cela est superflu. Si c'est le cas, pourquoi ne pas utiliser directement la version originale avec fermeture ? Elle permet également de contrôler l'itération. L'utilisation de la fermeture est la suivante :

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

Processus de conversion : fermeture → itérateur → itérateur de type pull. L'utilisation des fermetures et des itérateurs de type pull est similaire, leur philosophie est la même. Ce dernier peut entraîner des pénalités de performances en raison de divers traitements. Pour être honnête, cela semble effectivement superflu et les scénarios d'application sont limités. Cependant, iter.Pull existe pour iter.Seq, c'est-à-dire pour convertir les itérateurs de type push en itérateurs de type pull. Si vous souhaitez simplement un itérateur de type pull, envisagez la complexité et les performances de votre propre implémentation avant de créer un itérateur de type push pour le convertir. Comme dans l'exemple de la suite de Fibonacci, cela revient à tourner en rond pour revenir au point de départ. Le seul avantage est peut-être la conformité aux normes d'itérateurs officielles.

Gestion des erreurs

Que faire en cas d'erreur pendant l'itération ? Nous pouvons la transmettre à la fonction yield pour que for range la retourne, permettant à l'appelant de la gérer, comme dans l'exemple d'itérateur de lignes suivant :

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

Il est important de noter que l'itérateur ScanLines est à usage unique. Il ne peut pas être réutilisé après la fermeture du fichier.

Vous pouvez voir que sa deuxième valeur de retour est de type error. Voici comment l'utiliser :

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

Cela fonctionne comme une gestion d'erreur ordinaire. Les itérateurs de type pull fonctionnent de la même manière :

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

En cas de panic, utilisez recover comme d'habitude :

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

Les itérateurs de type pull fonctionnent de la même manière, nous ne le démontrerons pas ici.

Bibliothèque standard

De nombreuses bibliothèques standard prennent également en charge les itérateurs. Les plus couramment utilisées sont les bibliothèques slices et maps. Voici quelques fonctionnalités pratiques.

slices.All

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

slices.All convertit un slice en un itérateur de slice :

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

Résultat :

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 convertit un slice en un itérateur de slice, mais sans index :

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

Résultat :

1
2
3
4
5

slices.Chunk

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

La fonction slices.Chunk retourne un itérateur qui transmet des slices de n éléments à l'appelant :

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

Résultat :

[1 2]
[3 4]
[5]

slices.Collect

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

La fonction slices.Collect collecte un itérateur de slice en un slice :

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

Résultat :

[1 2 3 4 5]

maps.Keys

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

maps.Keys retourne un itérateur sur toutes les clés d'une map. Associé à slices.Collect, il peut être directement collecté en un slice :

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

Résultat :

[three one two]

Comme les maps sont non ordonnées, le résultat n'est pas fixe.

maps.Values

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

maps.Values retourne un itérateur sur toutes les valeurs d'une map. Associé à slices.Collect, il peut être directement collecté en un slice :

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

Résultat :

[3 1 2]

Comme les maps sont non ordonnées, le résultat n'est pas fixe.

maps.All

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

maps.All convertit une map en un itérateur 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)
  }
}

En général, on ne l'utilise pas directement ainsi, mais en combinaison avec d'autres fonctions de traitement de flux de données.

maps.Collect

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

maps.Collect collecte un itérateur de map en une map :

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

La fonction Collect est généralement utilisée comme fonction de fin de traitement de flux de données.

Appels en chaîne

Grâce aux fonctions fournies par la bibliothèque standard ci-dessus, nous pouvons les combiner pour traiter des flux de données, par exemple pour trier un flux de données :

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

Les itérateurs en Go utilisent des fermetures, ce qui oblige à imbriquer les appels de fonctions de cette manière. Ils ne permettent pas nativement les appels en chaîne, ce qui peut nuire à la lisibilité lorsque la chaîne d'appels est longue. Cependant, nous pouvons utiliser des structures pour enregistrer les itérateurs, permettant ainsi les appels en chaîne.

Démo

Une démonstration simple d'appel en chaîne est présentée ci-dessous. Elle inclut des fonctionnalités courantes telles que 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) {
      // Réorganiser les index
      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)}
}

Ensuite, nous pouvons utiliser les appels en chaîne pour traiter les données. Voici quelques exemples d'utilisation.

Traitement des valeurs d'éléments

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

Résultat :

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

Recherche d'une valeur spécifique

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

Résultat :

3

Remplissage d'un slice

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

Résultat :

[6 6 6 6 6]

Filtrage d'éléments

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

Résultat :

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

Il est dommage que Go ne prenne pas encore en charge les fonctions anonymes raccourcies, comme les fonctions fléchées en JavaScript, Rust ou Java. Sinon, les appels en chaîne pourraient être encore plus concis et élégants.

Performances

Étant donné que Go effectue de nombreux traitements pour les itérateurs, leurs performances sont certainement inférieures à celles des boucles for range natives. Prenons l'exemple le plus simple d'un parcours de slice pour tester leurs différences de performance, divisé en plusieurs catégories :

• Boucle for native
• Itérateur de type push
• Itérateur de type pull

Voici le code de test, avec un slice de longueur 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)
  }
}

Les résultats des tests sont les suivants :

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

Nous pouvons voir dans les résultats que les itérateurs de type push ne diffèrent pas beaucoup des boucles for range natives, mais les itérateurs de type pull sont presque deux ordres de grandeur plus lents que les deux précédents. Lors de l'utilisation, vous pouvez prendre en compte votre situation réelle.

Conclusion

Comme pour les génériques, les itérateurs en Go sont également controversés. Certains estiment que les itérateurs introduisent trop de complexité, allant à l'encontre de la philosophie de simplicité de Go. Avec ce type de code de fermeture pour les itérateurs, le débogage devient difficile et la lecture encore plus frustrante.

Vous pouvez voir des discussions animées sur les itérateurs à de nombreux endroits :

• Why People are Angry over Go 1.23 Iterators, une évaluation des itérateurs par un développeur étranger, vaut la peine d'être lue
• golang/go · Discussion #56413, une discussion communautaire initiée par rsc, où de nombreuses personnes ont exprimé leur opinion

En considérant rationnellement les itérateurs en Go, ils rendent effectivement l'écriture de code plus pratique, en particulier lors du traitement de types slice, mais ils introduisent également une certaine complexité. La lisibilité du code des itérateurs diminue, mais dans l'ensemble, je pense qu'il s'agit d'une fonctionnalité utile.