Tutoriel pour apprendre le langage Scala par l'exemple

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 k^e 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 :

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

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.

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 :

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

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

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 :

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 :

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 :

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 :

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 :

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

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

for (x <- e) yield e'

se traduit en :

e.map(x => e' )

• un for en compréhension

for (x <- e if f; s) yield e'

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

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

for (x <- e; y <- e' ; s) yield e''

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

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 » :

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 :

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 :

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 :

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

Exercice 10-3-2 : Traduisez :

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.

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 :

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 :

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.

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 :

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.