Tutoriel pour apprendre le langage Scala par l'exemple

Le type List. Comme les tableaux, les listes sont homogènes, c'est-à-dire que leurs éléments sont tous de même type. Le type d'une liste d'éléments de type T est noté List[T] :

val fruit: List[String] = List("apples", "oranges", "pears")
val nums : List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Int] = List()

Constructeurs de listes. Les listes sont construites à partir des deux constructeurs fondamentaux, Nil et :: (prononcé « cons »). Nil représente une liste vide. L'opérateur :: infixé exprime l'extension d'une liste : x :: xs représente une liste dont le premier élément est x, suivi (des éléments) de la liste xs. Les listes précédentes auraient donc pu également être définies de la façon suivante (en réalité, les définitions précédentes sont du sucre syntaxique masquant les définitions ci-dessous) :

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) :: (0 :: (1 :: (0 :: Nil))) ::
 (0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil

L'opération :: est associative à droite : A :: B :: C est interprété comme A :: (B :: C). Par conséquent, nous pouvons éliminer les parenthèses des définitions précédentes et écrire, par exemple :

val nums = 1 :: 2 :: 3 :: 4 :: Nil

Opérations de base sur les listes. Toutes les opérations sur les listes peuvent s'exprimer à l'aide des trois opérations :

• head renvoie le premier élément d'une liste ;
• tail renvoie la liste formée de tous les éléments sauf le premier ;
• isEmpty renvoie true si et seulement si la liste est vide.

Ces opérations sont définies comme des méthodes sur les objets listes. On les invoque donc à l'aide de la notation pointée habituelle :

empty.isEmpty // renvoie true
fruit.isEmpty // renvoie false
fruit.head // renvoie "apples"
fruit.tail.head // renvoie "oranges"
diag3.head // renvoie List(1, 0, 0)

Les méthodes head et tail ne sont définies que pour des listes non vides. Si elles sont appelées sur une liste vide, elles déclenchent une exception. Comme exemple de traitement des listes, étudions le tri croissant d'une liste de nombres. Un moyen simple d'y parvenir consiste à utiliser un tri par insertion, dont le principe est le suivant : pour trier une liste non vide dont le premier élément est x et le reste xs, on trie xs et on insère l'élément x à la bonne position dans le résultat. Le tri d'une liste vide donne une liste vide. Exprimé en Scala, cela donne :

def isort(xs: List[Int]): List[Int] =
    if (xs.isEmpty) Nil
    else insert(xs.head, isort(xs.tail))

Exercice 9-1-1 : Proposez une implémentation de la fonction insert.

Motifs de listes. En fait, :: est défini comme une case classe dans la bibliothèque standard de Scala. Il est donc possible de décomposer les listes par reconnaissance de motif en utilisant des motifs composés à partir des constructeurs Nil et ::. La méthode isort pourrait donc être écrite de la façon suivante :

def isort(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case x :: xs1 => insert(x, isort(xs1))
}

avec :

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
    case List() => List(x)
    case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
}

Les listes ne sont pas prédéfinies en Scala : elles sont définies par une classe abstraite List qui est fournie avec deux sous-classes :: et Nil. Dans cette section, nous passerons en revue la classe List.

package scala
abstract class List[+A] {

List étant une classe abstraite, nous ne pouvons pas définir les éléments en appelant le constructeur List (par exemple en écrivant new List). La classe a un paramètre de type A covariant, ce qui signifie que List[S] <: List[T] pour tous les types S et T tels que S <: T. Cette classe se trouve dans le paquetage scala, qui contient les principales classes standard de Scala. List définit un certain nombre de méthodes que nous décrirons ci-dessous.

Décomposition des listes. Les trois méthodes de base sont isEmpty, head et tail. Leur implémentation avec la reconnaissance de motif est triviale :

def isEmpty: Boolean = this match {
    case Nil => true case x :: xs => false
}
def head: A = this match {
    case Nil => error("Nil.head")
    case x :: xs => x
}
def tail: List[A] = this match {
    case Nil => error("Nil.tail")
    case x :: xs => xs
}

La fonction length calcule la longueur d'une liste :

def length: Int = this match {
    case Nil => 0
    case x :: xs => 1 + xs.length
}

Exercice 9-2-1 : Écrivez une version récursive terminale de length.

Les deux fonctions suivantes sont les compléments de head et tail :

def last: A
def init: List[A]

xs.last renvoie le dernier élément de la liste xs tandis que xs.init renvoie tous les éléments de xs sauf le dernier. Ces deux fonctions doivent parcourir toute le liste et sont donc moins efficaces que leurs homologues head et tail. Voici l'implémentation de last :

def last: A = this match {
    case Nil => error("Nil.last")
    case x :: Nil => x
    case x :: xs => xs.last
}

L'implémentation de init est analogue.

Les trois fonctions suivantes renvoient un préfixe de la liste, un suffixe ou les deux.

def take(n: Int): List[A] =
    if (n == 0 || isEmpty) Nil else head :: tail.take(n-1)

def drop(n: Int): List[A] =
    if (n == 0 || isEmpty) this else tail.drop(n-1)

def split(n: Int): (List[A], List[A]) = (take(n), drop(n))

(xs take n) renvoie les n premiers éléments de la liste xs ou la liste entière si elle a moins de n éléments. (xs drop n) renvoie tous les éléments de xs sauf les n premiers. Enfin, (xs split n) renvoie une paire formée des listes obtenues par xs take n et xs drop n.

La fonction suivante renvoie l'élément situé à un indice donné, elle est donc analogue à l'indexation des tableaux. Les indices commencent à 0.

def apply(n: Int): A = drop(n).head

En Scala, la méthode apply a une signification spéciale, car tout objet disposant de cette méthode peut se voir appliquer des paramètres comme s'il était une fonction. Pour obtenir le 3^e élément d'une liste xs, par exemple, vous pouvez écrire xs.apply(2) ou xs(2) (n'oubliez pas que les indices commencent à zéro) - la deuxième expression sera traduite dans la première.

Avec take et drop, nous pouvons extraire de la liste initiale des sous-listes d'éléments consécutifs.

Pour extraire la sous-liste xs_m, …, xs_n-1 de la liste xs, il suffit d'écrire :

xs.drop(m).take(n - m)

Combinaison de listes. La fonction suivante combine deux listes en une liste de paires. À partir de deux listes xs = List(x1, ..., xn) et ys = List(y1, ..., yn), l'expression xs zip ys renvoie la liste List((x1, y1), ..., (xn, yn)). Si les deux listes n'ont pas le même nombre d'éléments, la plus longue est tronquée. Voici la définition de zip - vous remarquerez que c'est une méthode polymorphe :

def zip[B](that: List[B]): List[(a,b)] =
    if (this.isEmpty || that.isEmpty) Nil
    else (this.head, that.head) :: (this.tail zip that.tail)

Extension de listes. Comme tout opérateur infixé, :: est également implémenté comme une méthode portant sur un objet qui est, ici, la liste à étendre. Ceci est possible, car les opérateurs se terminant par le caractère : sont traités de façon particulière par Scala : ils sont considérés comme des méthodes de leur opérande droit :

x :: y = y.::(x)

alors que :

x + y = x.+(y)

Notez cependant que les opérandes d'une opération binaire sont, dans tous les cas, évalués de gauche à droite. Par conséquent, si D et E sont des expressions avec d'éventuels effets de bord, D :: E est traduit en {val x = D; E. ::(x)} afin de maintenir l'ordre d'évaluation des opérandes.

Une autre différence des opérateurs se terminant par : est qu'ils sont associatifs à droite alors que les autres sont associatifs à gauche :

x :: y :: z = x :: (y :: z)

alors que :

x + y + z = (x + y) + z

La définition de :: comme méthode de la classe List est la suivante :

def ::[B >: A](x: B): List[B] = new scala.::(x, this)

Notez que :: est défini pour tous les éléments x de type B et les listes de type List[A] tels que B est un type parent de A. Le résultat est une liste d'éléments de type B. Ceci est exprimé par le fait que, dans la signature de ::, le paramètre de type B a pour borne inférieure A.

Concaténation de listes. La concaténation de listes ressemble à :: et est notée :::. Le résultat de (xs ::: ys) est une liste formée de tous les éléments de xs suivis de tous les éléments de ys. ::: se terminant par un caractère :, elle est associative à droite et considérée comme une méthode de son opérande droit. Par conséquent :

xs ::: ys ::: zs  =  xs ::: (ys ::: zs)
                  =  zs.:::(ys).:::(xs)

Voici l'implémentation de la méthode ::: :

def :::[B >: A](prefix: List[B]): List[B] = prefix match {
    case Nil => this
    case p :: ps => this.:::(ps).::(p)
}

Inversion de listes. Une autre opération utile consiste à inverser les listes. C'est ce que fait la méthode reverse de List. Considérons cette implémentation possible :

def reverse[A](xs: List[A]): List[A] = xs match {
    case Nil => Nil
    case x :: xs => reverse(xs) ::: List(x)
}

Cette implémentation a l'avantage d'être simple, mais elle n'est pas très efficace, car elle effectue une concaténation pour chaque élément de la liste. La concaténation prenant un temps proportionnel à la longueur du premier opérande, la complexité de cette version de reverse est donc :

n + (n − 1) + ... + 1 = n(n + 1)/2

où n est la longueur de xs. Peut-on implémenter reverse de façon plus efficace ? Nous verrons plus tard qu'il existe une autre implémentation qui a simplement une complexité linéaire.

Le tri par insertion que nous avons présenté plus haut dans ce chapitre est simple à formuler, mais n'est pas très performant - sa complexité moyenne est en effet proportionnelle au carré de la longueur de la liste à trier. Nous allons donc concevoir un programme pour trier les éléments d'une liste de façon plus efficace. Le tri par fusion (merge sort) est un bon algorithme et fonctionne de la façon suivante.

Si la liste est vide ou n'a qu'un seul élément, elle est déjà triée et l'on renvoie donc cette liste inchangée. Les listes plus longues sont divisées en deux sous-listes contenant chacune la moitié des éléments de la liste initiale. Chaque sous-liste est ensuite triée par un appel récursif à la fonction de tri et les deux sous-listes ainsi triées sont ensuite fusionnées.

Pour une implémentation la plus générale possible du tri par fusion, nous devons préciser le type des éléments à trier, ainsi que la fonction utilisée pour les comparer. Ceci nous amène à l'implémentation suivante :

def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
    def merge(xs1: List[A], xs2: List[A]): List[A] =
        if (xs1.isEmpty) xs2
        else if (xs2.isEmpty) xs1
        else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
        else xs2.head :: merge(xs1, xs2.tail)
    val n = xs.length/2
    if (n == 0) xs
    else merge(msort(less)(xs take n), msort(less)(xs drop n))
}

La complexité de msort est kitxmlcodeinlinelatexdvpO(N \log(N))finkitxmlcodeinlinelatexdvp, où kitxmlcodeinlinelatexdvpNfinkitxmlcodeinlinelatexdvp est la longueur de la liste d'entrée. Pour comprendre pourquoi, il suffit de remarquer que le découpage d'une liste en deux et la fusion de deux listes triées s'effectuent, chacune, dans un temps proportionnel à la longueur des listes passées en paramètre. Chaque appel récursif réduit de moitié le nombre d'éléments en entrée : il y a donc kitxmlcodeinlinelatexdvpO(\log(N))finkitxmlcodeinlinelatexdvp appels récursifs consécutifs avant d'atteindre le cas de base des listes de longueur 1. Cependant, pour les listes plus longues, chaque appel déclenche deux autres appels. Si l'on additionne le tout, on constate donc qu'à chacun des kitxmlcodeinlinelatexdvpO(\log(N))finkitxmlcodeinlinelatexdvp appels, chaque élément des listes initiales participe à une opération de découpage et à une opération de fusion. Chaque appel a donc un coût total proportionnel à kitxmlcodeinlinelatexdvpO(N)finkitxmlcodeinlinelatexdvp. Comme il y a kitxmlcodeinlinelatexdvpO(\log(N))finkitxmlcodeinlinelatexdvp appels, nous obtenant un coût total de kitxmlcodeinlinelatexdvpO(N \log(N))finkitxmlcodeinlinelatexdvp. Ce coût ne dépend pas de la distribution initiale des éléments dans la liste : le coût du pire des cas est donc le même que celui du cas général. Pour cette raison, le tri par fusion est un algorithme intéressant pour trier les listes.

Voici un exemple d'utilisation de msort :

msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))

La définition de msort étant curryfiée, il est facile de la spécialiser par des fonctions de comparaison particulières :

val intSort = msort((x: Int, y: Int) => x < y)
val reverseSort = msort((x: Int, y: Int) => x > y)

Les exemples étudiés jusqu'à présent montrent que les fonctions sur les listes ont souvent des structures similaires. Nous pouvons en effet identifier plusieurs motifs de traitement des listes :

• transformation de chaque élément d'une liste ;
• extraction de tous les éléments satisfaisant un certain critère ;
• combinaisons des éléments d'une liste à l'aide d'un opérateur.

Les langages fonctionnels permettent aux programmeurs d'écrire des fonctions générales qui implémentent ce genre de comportement au moyen de fonctions d'ordre supérieur. Nous allons donc maintenant présenter un ensemble de méthodes d'ordre supérieur fréquemment utilisées et qui sont implémentées comme des méthodes de la classe List.

Transformations dans une liste. Une opération courante consiste à transformer chaque élément d'une liste et à renvoyer la liste des résultats. Pour, par exemple, multiplier chaque élément d'une liste par un facteur donné :

def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
    case Nil => xs
    case x :: xs1 => x * factor :: scaleList(xs1, factor)
}

Ce traitement peut être généralisé par la méthode map de la classe List :

abstract class List[A] {
    ...
    def map[B](f: A => B): List[B] = this match {
        case Nil => this
        case x :: xs => f(x) :: xs.map(f)
    }

On peut donc réécrire scaleList de façon plus concise en utilisant map :

def scaleList(xs: List[Double], factor: Double) =
     xs map (x => x * factor)

Comme autre exemple, étudiez le problème consistant à renvoyer une colonne donnée d'une matrice représentée par une liste de lignes, chaque ligne étant elle-même une liste de colonnes. Ce résultat peut être obtenu grâce à la fonction column suivante :

def column[A](xs: List[List[A]], index: Int): List[A] =
 xs map (row => row(index))

La méthode foreach est apparentée à map. Elle applique une fonction donnée à tous les éléments d'une liste, mais, contrairement à map, ne construit pas la liste des résultats. On l'utilise donc uniquement pour son effet de bord. foreach est définie de la façon suivante :

def foreach(f: A => Unit) {
    this match {
        case Nil => ()
        case x :: xs => f(x); xs.foreach(f)
    }
}

Cette fonction peut servir, par exemple, à afficher tous les éléments d'une liste :

xs foreach (x => println(x))

Exercice 9-4-1 : La fonction squareList renvoie la liste des carrés de tous les éléments d'une liste. Complétez les deux définitions suivantes de squareList, qui sont équivalentes :

def squareList(xs: List[Int]): List[Int] = xs match {
    case List() => ??
    case y :: ys => ??
}
def squareList(xs: List[Int]): List[Int] =
    xs map ??
}

Filtrage des listes. Une autre opération fréquente consiste à sélectionner dans une liste tous les éléments qui satisfont un critère particulier. La fonction suivante, par exemple, renvoie la liste de tous les éléments positifs d'une liste d'entiers :

def posElems(xs: List[Int]): List[Int] = xs match {
    case Nil => xs
    case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1)
}

Ce motif est généralisé par la méthode filter de la classe List :

def filter(p: A => Boolean): List[A] = this match {
    case Nil => this
    case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
}

Grâce à filter, nous pouvons écrire posElems de façon plus concise :

def posElems(xs: List[Int]): List[Int] =
    xs filter (x => x > 0)

Une opération liée au filtrage consiste à tester si tous les éléments d'une liste satisfont une certaine condition. On peut également vouloir savoir s'il existe au moins un élément de la liste correspondant au critère. Ces opérations sont encapsulées par les fonctions d'ordre supérieur forall et exists de la classe List.

def forall(p: A => Boolean): Boolean =
    isEmpty || (p(head) && (tail forall p))
def exists(p: A => Boolean): Boolean =
    !isEmpty && (p(head) || (tail exists p))

Pour illustrer l'utilisation de forall, considérons le problème consistant à déterminer si un nombre est premier. Le nombre n est premier s'il n'est divisible que par 1 et par lui-même. La traduction la plus directe de cette définition consiste donc à tester que toutes les divisions de n par les nombres de 2 à n - 1 produisent un reste non nul. La liste des diviseurs possibles peut être produite par une fonction List.range qui est définie de la façon suivante dans la classe List :

package scala
object List { ...
    def range(from: Int, end: Int): List[Int] =
        if (from >= end) Nil else from :: range(from + 1, end)

List.range(2, n), par exemple, produit la liste de tous les entiers compris entre 2 et n-1. La

fonction isPrime peut donc être simplement définie de la façon suivante :

def isPrime(n: Int) =
    List.range(2, n) forall (x => n % x != 0)

Nous avons ainsi pu traduire directement en Scala la définition mathématique.

Exercice : Définissez les fonctions forall et exists à l'aide de filter.

Accumulation et réduction des listes. Une opération courante consiste à combiner les éléments d'une liste à l'aide d'un opérateur. Par exemple :

sum(List(x1, ..., xn)) = 0 + x1 + ... + xn
product(List(x1, ..., xn)) = 1 * x1 * ... * xn

Nous pourrions, bien sûr, implémenter ces deux fonctions sous forme récursive :

def sum(xs: List[Int]): Int = xs match {
    case Nil => 0
    case y :: ys => y + sum(ys)
}

def product(xs: List[Int]): Int = xs match {
    case Nil => 1
    case y :: ys => y * product(ys)
}

Mais nous pouvons également utiliser la généralisation de ce schéma fournie par la méthode reduceLeft de la classe List :

List(x1, ..., xn).reduceLeft(op) = (...(x1 op x2) op ... ) op xn

Avec reduceLeft nous pouvons donc mettre en évidence le motif de traitement utilisé par sum et product :

def sum(xs: List[Int]) = (0 :: xs) reduceLeft {(x, y) => x + y}
def product(xs: List[Int]) = (1 :: xs) reduceLeft {(x, y) => x * y}

Voici l'implémentation de reduceLeft :

def reduceLeft(op: (A, A) => A): A = this match {
    case Nil => error("Nil.reduceLeft")
    case x :: xs => (xs foldLeft x)(op)
}
def foldLeft[B](z: B)(op: (B, A) => B): B = this match {
    case Nil => z
    case x :: xs => (xs foldLeft op(z, x))(op)
}

Nous pouvons constater que la méthode reduceLeft est définie à l'aide d'une autre méthode, foldLeft. Cette dernière prend un accumulateur z comme paramètre supplémentaire, qui est renvoyé lorsque foldLeft est appliquée à la liste vide. Par conséquent :

(List(x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ... ) op xn

Les méthodes sum et product peuvent donc également être définies à partir de foldLeft :

def sum(xs: List[Int]) = (xs foldLeft 0) {(x, y) => x + y}
def product(xs: List[Int]) = (xs foldLeft 1) {(x, y) => x * y}

foldRight et reduceRight. Les appels de foldLeft et reduceLeft produisent des arbres penchés à gauche. Il existe également les méthodes duales foldRight et reduceRight qui produisent des arbres penchés à droite :

List(x1, ..., xn).reduceRight(op) = x1 op ( ... (xn −1 op xn)...)
(List(x1, ..., xn) foldRight acc)(op) = x1 op ( ... (xn op acc)...)

Ces deux méthodes sont définies de la façon suivante :

def reduceRight(op: (A, A) => A): A = this match {
    case Nil => error("Nil.reduceRight")
    case x :: Nil => x
    case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[B](z: B)(op: (A, B) => B): B = this match {
    case Nil => z
    case x :: xs => op(x, (xs foldRight z)(op))
}

La classe List définit également deux abréviations symboliques de foldLeft et foldRight :

def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)
def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f)

Les noms des méthodes symbolisent les arbres penchés à gauche/droite des opérations fold par des barres obliques penchées vers l'avant ou vers l'arrière. Le caractère : pointe toujours vers la liste alors que la barre pointe toujours vers l'accumulateur z :

(z /: List(x1, ..., xn))(op) = (...(z op x1) op ... ) op xn
(List(x1, ..., xn) :\ z)(op) = x1 op ( ... (xn op z)...)

Pour les opérateurs associatifs et commutatifs, /: et :\ sont équivalents (bien que leur efficacité puisse être différente).

Exercice 9-4-2 : Soit la fonction flatten qui prend une liste de listes d'éléments en arguments et renvoie la concaténation de tous les éléments sous la forme d'une liste simple. Voici une implémentation de cette méthode à l'aide de :\ :

def flatten[A](xs: List[List[A]]): List[A] =
 (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}

Si l'on remplace le corps de flatten par :

((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)

quelle serait la différence de complexité asymptotique entre ces deux versions ?

En fait, comme d'autres fonctions utiles, flatten est prédéfinie dans l'objet List de la bibliothèque standard. Elle est donc accessible via un appel à List.flatten. Ce n'est pas une méthode de la classe List - cela n'aurait aucun sens ici, car elle ne s'applique qu'à une liste de listes, pas à toutes les listes en général.

Renversement de listes revisité. Nous avons présenté dans la section 9.2Définition de la classe List I : méthodes du premier ordre une implémentation de la méthode reverse dont le temps d'exécution était quadratique par rapport à la longueur de la liste à renverser. Nous allons maintenant présenter une nouvelle version ayant un coût linéaire. Le principe consiste à utiliser foldLeft en se servant du schéma suivant :

class List[+A] { ...
    def reverse: List[A] = (z? /: this)(op?)

Il ne reste plus qu'à remplacer les parties z? et op?. Essayons de les déduire à partir d'exemples :

  Nil
= Nil.reverse           // selon la spécification
= (z /: Nil)(op)        // selon le schéma de reverse
= (Nil foldLeft z)(op)  // selon la définition de /:
= z                     // selon la définition de foldLeft

z? doit donc être Nil. Pour déduire le second opérande, étudions le renversement d'une liste de longueur un.

  List(x)
= List(x).reverse              // selon la spécification
= (Nil /: List(x))(op)         // selon le schéma de reverse, avec z = Nil
= (List(x) foldLeft Nil)(op)   // selon la définition de /:
= op(Nil, x)                   // selon la définition de foldLeft

Donc op(Nil, x) est égal à List(x), c'est-à-dire à x :: Nil. Ceci suggère que op est l'opérateur :: avec ses opérandes échangés. Nous arrivons donc à l'implémentation suivante de reverse, qui a une complexité linéaire :

def reverse: List[A] =
    ((Nil: List[A]) /: this) {(xs, x) => x :: xs}

(Remarque : l'annotation de type de Nil est nécessaire pour que l'inférenceur de type puisse fonctionner).

Exercice 9-4-3 : Remplissez les expressions manquantes pour compléter ces définitions des opérations de base sur les listes sous forme d'opérations fold :

def mapFun[A, B](xs: List[A], f: A => B): List[B] =
    (xs :\ List[B]()){ ?? }

def lengthFun[A](xs: List[A]): int =
    (0 /: xs){ ?? }

Transformations imbriquées. Nous pouvons nous servir des fonctions d'ordre supérieur sur les listes afin d'exprimer des calculs qui sont généralement réalisés par des boucles imbriquées dans les langages impératifs.

À titre d'exemple, considérons le problème consistant à trouver toutes les paires d'entiers i et j telles que i + j est premier, avec j < i < n pour une valeur n donnée. Pour n = 7, par exemple, ces paires sont :

i     | 2 3 4 4 5 6 6
j     | 1 2 1 3 2 1 5
========================
i + j | 3 5 5 7 7 7 11

Un moyen naturel de résoudre ce problème consiste à le traiter en deux étapes. La première produit toutes les paires d'entiers (i, j) telles que j < i < n ; la seconde filtre cette suite pour ne garder que les paires telles que i + j est premier.

Si l'on étudie la première étape plus en détail, on constate que la production d'une suite de paires s'effectue en trois sous-étapes. On génère d'abord tous les entiers i compris entre 1 et n puis, pour chaque i, on produit la liste de paires (i, 1) jusqu'à (i, i -1), ce qui peut s'effectuer par une combinaison de range et de map :

List.range(1, i) map (x => (i, x))

Enfin, on combine toutes ces sous-listes avec foldRight et :::. L'expression complète est donc la suivante :

List.range(1, n)
  .map(i => List.range(1, i).map(x => (i, x)))
  .foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys}
  .filter(pair => isPrime(pair._1 + pair._2))

Transformations avec aplatissement des listes. La combinaison d'une transformation et de la concaténation des sous-listes produites par cette transformation est une opération si fréquente qu'il existe une méthode prévue pour dans la classe List :

abstract class List[+A] { ...
    def flatMap[B](f: A => List[B]): List[B] = this match {
        case Nil => Nil
        case x :: xs => f(x) ::: (xs flatMap f)
    }
}

Avec flatMap, l'expression trouvant les paires dont la somme des éléments est un nombre premier peut s'écrire de façon plus courte :

List.range(1, n)
  .flatMap(i => List.range(1, i).map(x => (i, x)))
  .filter(pair => isPrime(pair._1 + pair._2))

9-4-1. Résumé▲