Tutoriel pour apprendre le langage Scala par l'exemple

Le chapitre précédent a présenté les variables, l'affectation et les objets avec état. Nous avons vu que nous pouvions modéliser les objets du monde réel qui évoluent avec le temps en modifiant l'état des variables au cours du traitement. Les modifications du temps dans le monde réel sont ainsi modélisées par des changements du temps au cours de l'exécution d'un programme. Ces modifications temporelles sont généralement étalées ou au contraire compressées, mais leur ordre relatif est le même. Tout ceci semble naturel, mais il y a un prix à payer : le modèle de substitution simple et puissant que nous utilisions en programmation fonctionnelle n'est plus applicable dès que l'on introduit des variables et des affectations.

Existe-t-il un autre moyen ? Peut-on modéliser les changements d'états du monde réel en n'utilisant que des fonctions qui ne modifient pas leurs arguments ? Si l'on se fie aux mathématiques, la réponse est évidemment oui : une quantité de temps variable est simplement modélisée par une fonction f(t), où t est un temps. Il en va de même pour nos programmes. Au lieu d'écraser une variable avec des valeurs successives, nous pouvons représenter toutes ces valeurs comme les éléments successifs d'une liste. Une variable modifiable var x: T peut donc être remplacée par une valeur non mutable val x: List[T]. Dans un certain sens, nous sacrifions l'espace mémoire pour le temps - les différentes valeurs de la variable existent désormais toutes simultanément en tant qu'éléments de la liste. L'avantage de cette vue est que nous pouvons « voyager dans le temps », c'est-à-dire voir plusieurs valeurs successives de la variable. Un autre intérêt est que nous pouvons utiliser la puissance de la bibliothèque de fonctions sur les listes, qui simplifie souvent les traitements. Considérez, par exemple, l'approche impérative pour calculer la somme de tous les nombres premiers compris entre deux bornes :

def sumPrimes(start: Int, end: Int): Int = {
    var i = start
    var acc = 0
    while (i < end) {
        if (isPrime(i)) acc += i i += 1
    }
    acc
}

Vous remarquerez que la variable i parcourt toutes les valeurs de l'intervalle [start .. end - 1].

Une approche plus fonctionnelle consiste à représenter directement la liste des valeurs de i avec range(start, end). La fonction peut alors être réécrite de la façon suivante :

def sumPrimes(start: Int, end: Int) =
  sum(range(start, end) filter isPrime)

On voit tout de suite quel programme est le plus court et le plus clair ! Cependant, le programme fonctionnel est également considérablement moins efficace, car il construit une liste de tous les nombres de l'intervalle, puis une autre pour les nombres premiers. C'est encore pire si l'on recherche le deuxième nombre premier entre 1000 et 10 000 :

range(1000, 10000) filter isPrime at 1

Ce code construit la liste de tous les nombres compris entre 1000 et 10 000 alors que l'essentiel de cette liste ne sera jamais parcouru !

Pour ce type d'exemple, nous pouvons cependant obtenir une exécution efficace en utilisant l'astuce suivante :

Nous allons donc présenter une nouvelle classe pour gérer ce type de séquences : la classe Stream.

Les streams (flux) sont créés à partir de la constante empty et du constructeur cons qui sont tous les deux définis dans le module scala.Stream. L'expression suivante, par exemple, construit un flux contenant les éléments 1 et 2 :

Stream.cons(1, Stream.cons(2, Stream.empty))

Voici un autre exemple, produisant un flux analogue à la liste produite par List.range :

def range(start: Int, end: Int): Stream[Int] =
    if (start >= end) Stream.empty
    else Stream.cons(start, range(start + 1, end))

(Cette fonction existe déjà dans le module Stream). Bien que Stream.range et List.range se ressemblent, leur comportement est totalement différent :

Stream.range se termine immédiatement en renvoyant un objet Stream dont le premier élément est start ; les autres éléments ne seront calculés que lorsqu'ils seront demandés par la méthode tail (ce qui peut ne jamais arriver).

On accède aux éléments des flux comme aux éléments des listes. Comme ces dernières, les méthodes de base sont isEmpty, head et tail. Nous pouvons par exemple afficher tous les éléments d'un flux de la façon suivante :

def print(xs: Stream[A]) {
    if (!xs.isEmpty) { Console.println(xs.head); print(xs.tail) }
}

Les flux disposent également de la plupart des méthodes définies sur les listes (voir plus bas). Nous pouvons donc trouver le second nombre premier compris entre 1000 et 10 000 en nous servant des méthodes filter et apply d'un flux :

Stream.range(1000, 10000) filter isPrime at 1

La différence avec l'implémentation reposant sur une liste est que, désormais, nous ne construisons pas inutilement les nombres supérieurs à 1013 et nous ne testons pas non plus s'ils sont premiers.

Construction et concaténation des flux. Deux méthodes de la classe List ne sont pas reconnues par la classe Stream : il s'agit de :: et de :::, car le récepteur de ces méthodes est leur opérande droit, ce qui signifie qu'il doit être évalué avant que la méthode ne soit appelée. Dans le cas d'une opération x :: xs sur une liste, par exemple, il faut évaluer xs avant d'appeler :: pour construire la nouvelle liste. Ceci ne fonctionne pas pour les flux, car nous voulons justement que la fin d'un flux ne soit évaluée que si cela est demandé par l'opération tail. C'est pour la même raison que la concaténation des listes ::: n'est pas non plus adaptée aux flux.

Au lieu de x :: xs, utilisez Stream.cons(x, xs) pour construire un flux dont le premier élément sera x et le reste (non évalué) sera xs. À la place de xs ::: ys, utilisez xs append ys.