Tutoriel pour apprendre le langage Scala par l'exemple


précédentsommairesuivant

10. For en compréhension

Le chapitre précédent a montré que les fonctions d'ordre supérieur comme map, flatmap et filter fournissaient des constructions puissantes pour traiter les listes. Parfois, cependant, le niveau d'abstraction requis par ces fonctions complique la compréhension des programmes.

Pour rendre le code plus facile à saisir, Scala dispose d'une notation spéciale, qui simplifie les motifs courants d'application des fonctions d'ordre supérieur. Cette notation établit un pont entre les ensembles en compréhension(3) (ou en « intension ») des mathématiques et les boucles for des langages impératifs comme C ou Java. Elle ressemble également beaucoup à la notation utilisée pour exprimer les requêtes des bases de données relationnelles.

Comme premier exemple, supposons que nous ayons une liste de personnes avec des champs name et age. Pour afficher les noms de toutes les personnes ayant plus de 20 ans, nous pourrions écrire :

 
Sélectionnez
for (p <- persons if p.age > 20) yield p.name

Cette expression est équivalente à celle-ci, qui utilise les fonctions filter et map :

 
Sélectionnez
persons filter (p => p.age > 20) map (p => p.name)

Le for en compréhension ressemble à la boucle for des langages impératifs, sauf qu'elle construit une liste du résultat de toutes ses itérations.

Généralement, un for en compréhension est de la forme :

 
Sélectionnez
for ( s ) yield e

s est une suite de générateurs, de définitions et de filtres. Un générateur est de la forme val x e, où e est une expression renvoyant une liste. Le générateur lie x aux valeurs des éléments successifs de la liste. Une définition est de la forme val x = e et introduit le nom x qui désignera la valeur de e dans le reste de la compréhension. Un filtre est une expression f de type Boolean - il supprime toutes les liaisons pour lesquelles f vaut false. La séquence s commence toujours par un générateur - s'il y en a plusieurs, les derniers varient plus rapidement que les premiers.

La séquence s peut également être placée entre accolades au lieu d'être entre parenthèses. Dans ce cas, les points-virgules qui séparent les générateurs, les définitions et les filtres peuvent être omis.

Voici deux exemples montrant l'utilisation des for en compréhensions. Reprenons d'abord un exemple du chapitre précédent : à partir d'un nombre n entier positif, nous voulons trouver toutes les paires (i, j) telles que j < i < n et i + j est premier. Ce problème se résout de la façon suivante avec un for en compréhension :

 
Sélectionnez
1.
2.
3.
for { i <- List.range(1, n)
      j <- List.range(1, i)
 if isPrime(i+j) } yield {i, j}

Ce code est, sans conteste, bien plus clair que la solution précédente qui utilisait map, flatMap et filter. Comme second exemple, calculons le produit scalaire de deux vecteurs xs et ys :

 
Sélectionnez
sum(for ((x, y) <- xs zip ys) yield x * y)

10-1. Le problème des N reines

Les compréhensions sont particulièrement utiles pour résoudre des problèmes combinatoires. Prenons, par exemple, le problème bien connu des huit reines (ou sans doute devrait-on écrire des huit dames ; aux échecs, on parle plutôt de dames en français) : sur un échiquier classique, nous voulons placer huit dames de telle sorte qu'aucune d'elles ne puisse en capturer une autre (une dame ne peut capturer une pièce que si elle est sur la même ligne, la même colonne ou la même diagonale). Nous allons donc développer une solution à ce problème, en le généralisant aux échiquiers de taille quelconque. Le problème est donc de placer n dames sur un échiquier de n × n cases.

Pour le résoudre, vous noterez que nous devons placer une dame sur chaque ligne. Nous pourrions donc placer les dames sur les lignes successives en vérifiant à chaque fois que la dame que l'on vient de placer ne peut pas être capturée par l'une des dames déjà placées. Au cours de cette recherche, il peut arriver qu'une dame placée sur la ligne k soit en échec dans toutes les colonnes de cette ligne pour les dames placées aux lignes 1 à k-1. En ce cas, il faut mettre fin à cette partie de la recherche afin de continuer avec une autre configuration des dames dans les colonnes 1 à k-1.

Ceci suggère donc un algorithme récursif. Supposons que l'on ait déjà produit toutes les solutions pour placer k-1 dames sur un échiquier de n × n cases. Chacune de ces solutions peut être représentée par une liste de k-1 numéros de colonnes (qui peuvent varier de 1 à n). Nous traitons ces listes de solutions partielles comme des piles où le numéro de colonne de la dame située sur la ligne k-1 est le premier de la liste, suivi du numéro de colonne de la dame dans la ligne k-2, etc. L'élément au fond de la pile est le numéro de colonne de la dame placée sur la première ligne. Toutes ces solutions sont regroupées dans une liste de listes, dont chaque élément est une solution.

Pour placer la ke dame, nous devons produire toutes les extensions possibles de chacune des solutions précédentes en leur ajoutant une dame supplémentaire. Ceci produit une autre liste de listes solution, cette fois-ci de longueur k. Ce processus se poursuit jusqu'à ce que nous ayons des solutions de la taille n de l'échiquier. Ce principe peut être implémenté de la façon suivante par la fonction placeQueens :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
def queens(n: Int): List[List[Int]] = {
    def placeQueens(k: Int): List[List[Int]] =
        if (k == 0) List(List())
        else for { queens <- placeQueens(k - 1)
                   column <- List.range(1, n + 1)
                   if isSafe(column, queens, 1) } yield column :: queens placeQueens(n)
}

Exercice 10-1-1 : Écrivez la fonction

 
Sélectionnez
def isSafe(col: Int, queens: List[Int], delta: Int): Boolean

qui teste si l'on peut placer sans problème une dame dans la colonne col par rapport aux dames déjà placées. Ici, delta est la différence entre la ligne de la dame à placer et celle de la première dame de la liste.

10-2. Requêtes sur compréhensions

La notation for est équivalente aux opérations classiques des langages de requêtes des bases de données. Supposons, par exemple, que la base de données books soit représentée par une liste de livres où Book est défini de la façon suivante :

 
Sélectionnez
case class Book(title: String, authors: List[String])

Voici une petite base de données d'exemple :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
val books: List[Book] = List(
  Book("Structure and Interpretation of Computer Programs",
       List("Abelson, Harold", "Sussman, Gerald J.")),
  Book("Principles of Compiler Design",
       List("Aho, Alfred", "Ullman, Jeffrey")),
  Book("Programming in Modula-2",
       List("Wirth, Niklaus")),
  Book("Introduction to Functional Programming"),
       List("Bird, Richard")),
  Book("The Java Language Specification",
       List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad")))

Voici comment trouver les titres de tous les livres écrits par Ullman :

 
Sélectionnez
for (b <- books; a <- b.authors if a startsWith "Ullman")
    yield b.title

(Ici, startsWith est une méthode de java.lang.String).

Pour trouver tous les titres ayant « Program » dans leur titre :

 
Sélectionnez
for (b <- books if (b.title indexOf "Program") >= 0)
    yield b.title

Pour trouver les noms de tous les auteurs qui ont écrit au moins deux livres :

 
Sélectionnez
1.
2.
3.
for (b1 <- books; b2 <- books if b1 != b2;
     a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
    yield a1

Cette solution n'est pas parfaite, car les auteurs apparaîtront plusieurs fois dans la liste du résultat. Pour supprimer les auteurs dupliqués, vous pouvez utiliser la fonction suivante :

 
Sélectionnez
1.
2.
3.
def removeDuplicates[A](xs: List[A]): List[A] =
 if (xs.isEmpty) xs
 else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head))

Notez que la dernière expression de removeDuplicates peut s'exprimer à l'aide d'un for en compréhension :

 
Sélectionnez
xs.head :: removeDuplicates(for (x <- xs.tail if x != xs.head) yield x)

10-3. Traduction des for en compréhension

Tout for en compréhension peut s'exprimer en termes des trois fonctions d'ordre supérieur, map, flatMap et filter. Voici le schéma de traduction utilisé par le compilateur Scala :

  • un for en compréhension simple
 
Sélectionnez
for (x <- e) yield e'

se traduit en :

 
Sélectionnez
e.map(x => e' )
  • un for en compréhension
 
Sélectionnez
for (x <- e if f; s) yield e'

f est un filtre et s une suite (éventuellement vide) de générateurs ou de filtres se traduit en :

 
Sélectionnez
for (x <- e.filter(x => f); s) yield e'

puis le processus de traduction se poursuit avec cette nouvelle expression

  • un for en compréhension
 
Sélectionnez
for (x <- e; y <- e' ; s) yield e''

s est une suite (éventuellement vide) de générateurs ou de filtres se traduit en :

 
Sélectionnez
e.flatMap(x => for (y <- e' ; s) yield e'' )

puis le processus de traduction se poursuit avec cette nouvelle expression.

Si nous reprenons les « paires d'entiers sont la somme est un nombre premier » :

 
Sélectionnez
1.
2.
3.
4.
for { i <- range(1, n)
    j <- range(1, i)
    if isPrime(i+j)
} yield {i, j}

Voici que l'on obtient en traduisant cette expression :

 
Sélectionnez
1.
2.
3.
4.
5.
range(1, n)
  .flatMap(i =>
      range(1, i)
        .filter(j => isPrime(i+j))
        .map(j => (i, j)))

Inversement, il serait également possible d'exprimer les fonctions map, flatMap et filter à l'aide de for en compréhension :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
object Demo {
    def map[A, B](xs: List[A], f: A => B): List[B] =
        for (x <- xs) yield f(x)

    def flatMap[A, B](xs: List[A], f: A => List[B]): List[B] =
        for (x <- xs; y <- f(x)) yield y

    def filter[A](xs: List[A], p: A => Boolean): List[A] =
        for (x <- xs if p(x)) yield x
}

Sans surprise, la traduction du for en compréhension dans le corps de Demo.map produira un appel à la méthode map de la classe List. De même, Demo.flatMap et Demo.filter seront traduites, respectivement, par les méthodes flatMap et filter de la classe List.

Exercice 10-3-1 : Définissez la fonction suivante à l'aide de for :

 
Sélectionnez
def flatten[A](xss: List[List[A]]): List[A] =
 (xss :\ (Nil: List[A])) ((xs, ys) => xs ::: ys)

Exercice 10-3-2 : Traduisez :

 
Sélectionnez
for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
for (b <- books if (b.title indexOf "Program") >= 0) yield b.title

en fonctions d'ordre supérieur.

10-4. Boucles for

Les for en compréhension ressemblent aux boucles for des langages impératifs, sauf qu'ils produisent une liste de résultats. Parfois, nous n'avons pas besoin de cette liste, mais nous voulons quand même bénéficier de la souplesse des générateurs et des filtres dans nos parcours des listes. Ceci est possible grâce à une variante de la syntaxe de for en compréhension, qui permet d'exprimer des boucles for :

 
Sélectionnez
for ( s ) e

Cette construction est identique à la syntaxe standard des for en compréhension, mais sans le mot-clé yield. La boucle s'exécute en appliquant l'expression e à chaque élément produit par la suite de générateurs et de filtres s.

Le code suivant, par exemple, affiche tous les éléments d'une matrice représentée par une liste de listes :

 
Sélectionnez
1.
2.
3.
4.
for (xs <- xss) {
    for (x <- xs)
    print(x + "\t") println()
}

La traduction des boucles for en méthodes d'ordre supérieur de la classe List est similaire à la traduction des for en compréhension, mais elle est plus simple. Là ou les for en compréhension se traduisent en map et flatMap, les boucles for se traduisent dans chaque cas en foreach.

10-5. Généralisation de for

Nous avons vu que la traduction des for en compréhension n'a besoin que des méthodes map, flatMap et filter : il est donc possible d'appliquer la même notation aux générateurs qui produisent des objets autres que des listes. Ces objets ont simplement besoin de disposer de ces trois méthodes essentielles.

La bibliothèque standard de Scala fournit plusieurs autres abstractions supportant ces trois méthodes et, avec elles, les for en compréhension. Nous en présenterons quelques-unes dans les chapitres qui suivent. En tant que programmeur, vous pouvez également utiliser ce principe pour que les for en compréhension puissent s'appliquer à vos propres types - il suffit qu'ils disposent des méthodes map, flatMap et filter.

Il y a de nombreux cas où ceci peut s'avérer utile : pour les interfaces des bases de données, les arborescences XML ou les valeurs optionnelles, notamment.

Attention : rien ne garantit automatiquement que le résultat de la traduction d'un for en compréhension sera correctement typé. Pour vous en assurer, les types de map, flatMap et filter doivent essentiellement être similaires aux types de ces méthodes dans la classe List.

Pour préciser, supposons que vous ayez une classe paramétrée C[A] pour laquelle vous voulez autoriser les for en compréhension. La classe C devrait donc définir map, flatMap et filter avec les types suivants :

 
Sélectionnez
1.
2.
3.
def map[B](f: A => B): C[B]
def flatMap[B](f: A => C[B]): C[B]
def filter(p: A => Boolean): C[A]

Il serait intéressant que le compilateur Scala impose statiquement ces types en exigeant, par exemple, que tout type disposant des compréhensions implémente un trait standard avec ces méthodes(4) (). Le problème est que ce trait standard devrait rendre abstrait l'identité de la classe C en utilisant, par exemple, C comme un paramètre de type. Ce paramètre serait un constructeur de types qui serait appliqué à plusieurs types différents dans les signatures des méthodes map et flatMap. Malheureusement, le système de typage de Scala est trop faible pour exprimer cette possibilité, car il ne peut gérer que les paramètres de type qui sont des types totalement appliqués.


précédentsommairesuivant
Un ensemble ou une liste en compréhension (on dit parfois « en intension » en logique) se définit par une propriété permettant de déterminer ses éléments ; par exemple, une liste d'entiers pairs peut se définir à partir d'une liste d'entiers quelconques dont on ne garde que ceux qui sont divisibles par 2. Cette forme de définition s'oppose à une liste ou un ensemble en extension, qui énumèrent les éléments de l'ensemble ou de la liste. (NdT)
En Haskell, un langage disposant de la même fonctionnalité, cette abstraction est appelée « monade avec zéro ».

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 ni 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.