Tutoriel pour apprendre le langage Scala par l'exemple


précédentsommairesuivant

13. Itérateurs

Les itérateurs sont la version impérative des flux. Comme eux, les itérateurs décrivent des listes potentiellement infinies, mais il n'existe pas de structure de données contenant leurs éléments. Les itérateurs permettent plutôt de progresser dans une séquence à l'aide de deux méthodes abstraites, next et hasNext :

 
Sélectionnez
1.
2.
3.
4.
trait Iterator[+A] {
    def hasNext: Boolean
    def next: A
}

La méthode next renvoie les éléments successifs de l'itération tandis que la méthode hasNext indique s'il reste des éléments pouvant être renvoyés par next. Les itérateurs disposent également d'autres méthodes que nous présenterons plus loin.

Voici, par exemple, une application qui affiche le carré de chacun des nombres de 1 à 100 :

 
Sélectionnez
1.
2.
3.
4.
5.
val it: Iterator[Int] = Iterator.range(1, 100)
while (it.hasNext) {
    val x = it.next
    println(x * x)
}

13-1. Méthodes des itérateurs

Outre next et hasNext, les itérateurs ont un grand nombre de méthodes dont la plupart imitent la fonctionnalité correspondante des listes.

append. La méthode append construit un itérateur qui continuera avec l'itérateur indiqué lorsque l'itérateur courant sera terminé.

 
Sélectionnez
1.
2.
3.
4.
def append[B >: A](that: Iterator[B]): Iterator[B] = new Iterator[B] {
    def hasNext = Iterator.this.hasNext || that.hasNext
    def next = if (Iterator.this.hasNext) Iterator.this.next else that.next
}

Les termes Iterator.this.next et Iterator.this.hasNext dans la définition de append appellent les méthodes respectives définies dans la classe Iterator du récepteur. Sans le préfixe Iterator, les appels hasNext et next invoqueraient les méthodes définies dans le résultat de append, ce qui n'est pas ce que l'on recherche.

map, flatMap, foreach. La méthode map construit un itérateur qui renvoie tous les éléments de l'itérateur initial transformés par la fonction f indiquée.

 
Sélectionnez
1.
2.
3.
4.
def map[B](f: A => B): Iterator[B] = new Iterator[B] {
    def hasNext = Iterator.this.hasNext
    def next = f(Iterator.this.next)
}

La méthode flatMap est comme la méthode map, sauf que la fonction de transformation f renvoie un itérateur. Son résultat est l'itérateur produit par la concaténation de tous les itérateurs renvoyés par les appels successifs à f.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] {
    private var cur: Iterator[B] = Iterator.empty
    def hasNext: Boolean =
        if (cur.hasNext) true
        else if (Iterator.this.hasNext) { cur = f(Iterator.this.next); hasNext }
        else false
    def next: B =
        if (cur.hasNext) cur.next
        else if (Iterator.this.hasNext) { cur = f(Iterator.this.next); next }
        else error("next on empty iterator")
}

La méthode foreach est étroitement liée à map, car elle applique une fonction donnée à tous les éléments d'un itérateur. Cependant, elle ne construit pas la liste des résultats.

 
Sélectionnez
def foreach(f: A => Unit): Unit =
    while (hasNext) { f(next) }

filter. La méthode filter construit un itérateur renvoyant tous les éléments de l'itérateur initial qui satisfont le critère donné.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
def filter(p: A => Boolean) = new BufferedIterator[A] {
    private val source = Iterator.this.buffered
    private def skip =
        { while (source.hasNext && !p(source.head)) { source.next } }
    def hasNext: Boolean =
        { skip; source.hasNext }
    def next: A =
        { skip; source.next }
    def head: A =
        { skip; source.head }
}

En fait, filter renvoie des instances d'une sous-classe d'itérateurs « tamponnés ». Un objet BufferedIterator est un itérateur qui a en plus une méthode head qui renvoie l'élément qui aurait été renvoyé par next, mais sans avancer après cet élément. La valeur renvoyée par head sera donc à nouveau renvoyée par le prochain appel à head ou à next. Voici la définition du trait BufferedIterator :

 
Sélectionnez
1.
2.
3.
trait BufferedIterator[+A] extends Iterator[A] {
    def head: A
}

Les méthodes map, flatMap, filter et foreach existant pour les itérateurs, il s'ensuit que les for en compréhension ou les boucles for leur sont également applicables. Le code qui affiche les carrés des nombres compris entre 1 et 100 pourrait donc s'exprimer de la façon suivante :

 
Sélectionnez
for (i <- Iterator.range(1, 100)) println(i * i)

zip. La méthode zip prend un second itérateur en paramètre et renvoie un itérateur formé des paires d'éléments correspondants renvoyés par les deux itérateurs.

 
Sélectionnez
1.
2.
3.
4.
def zip[B](that: Iterator[B]) = new Iterator[(A, B)] {
    def hasNext = Iterator.this.hasNext && that.hasNext
    def next = (Iterator.this.next, that.next)
}

13-2. Construction d'itérateurs

Les itérateurs concrets doivent fournir les implémentations des deux méthodes next et hasNext de la classe Iterator. L'itérateur le plus simple est Iterator.empty qui renvoie toujours une séquence vide :

 
Sélectionnez
1.
2.
3.
4.
5.
object Iterator {
    object empty extends Iterator[Nothing] {
        def hasNext = false
        def next = error("next on empty iterator")
    }

Un itérateur plus intéressant est celui qui énumère tous les éléments d'un tableau. Il est construit par la méthode fromArray, qui est également définie dans l'objet Iterator :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
def fromArray[A](xs: Array[A]) = new Iterator[A] {
    private var i = 0
    def hasNext: Boolean =
        i < xs.length
    def next: A =
        if (i < xs.length) { val x = xs(i); i += 1; x }
        else error("next on empty iterator")
}

Un autre itérateur énumère un intervalle d'entiers. La fonction Iterator.range renvoie un itérateur qui parcourt un intervalle de valeurs entières :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
object Iterator {
    def range(start: Int, end: Int) = new Iterator[Int] {
        private var current = start
        def hasNext = current < end
        def next = {
            val r = current
            if (current < end) current += 1
            else error("end of iterator") r
        }
    }
}

Tous les itérateurs que nous venons de présenter finissent par se terminer. Vous pouvez également définir des itérateurs infinis. L'itérateur suivant, par exemple, renvoie tous les entiers à partir de la valeur value (7) :

 
Sélectionnez
1.
2.
3.
4.
5.
def from(start: Int) = new Iterator[Int] {
    private var last = start - 1
    def hasNext = true
    def next = { last += 1; last }
}

13-3. Utilisation des itérateurs

Voici deux exemples supplémentaires d'utilisation des itérateurs. Le premier affiche tous les éléments d'un tableau xs :

 
Sélectionnez
Iterator.fromArray(xs) foreach (x => println(x))

Ou, avec un for en compréhension :

 
Sélectionnez
for (x <- Iterator.fromArray(xs)) println(x)

Voici un second exemple qui recherche les indices des éléments d'un tableau de double supérieurs à limit :

 
Sélectionnez
1.
2.
3.
4.
5.
import Iterator._
fromArray(xs)
  .zip(from(0))
  .filter(case (x, i) => x > limit)
  .map(case (x, i) => i)

Ou, avec un for en compréhension :

 
Sélectionnez
1.
2.
3.
import Iterator._
for ((x, i) <- fromArray(xs) zip from(0); x > limit)
    yield i

précédentsommairesuivant
À cause de la représentation finie du type int, les nombres reboucleront à 231.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2017 Martin Odersky. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.