Tutoriel pour apprendre le langage Scala par l'exemple

Notre premier exemple est une implémentation du tri rapide en Scala :

def sort(xs: Array[Int]) {
    def swap(i: Int, j: Int) {
        val t = xs(i); xs(i) = xs(j); xs(j) = t
    }
    def sort1(l: Int, r: Int) {
        val pivot = xs((l + r) / 2)
        var i = l; var j = r
        while (i <= j) {
            while (xs(i) < pivot) i += 1
            while (xs(j) > pivot) j -= 1
            if (i <= j) {
                swap(i, j)
                i += 1
                j -= 1
            }
        }
        if (l < j) sort1(l, j)
        if (j < r) sort1(i, r)
    }
    sort1(0, xs.length - 1)
}

Cette implémentation ressemble beaucoup à ce que l'on aurait pu écrire en Java ou en C : elle utilise les mêmes opérateurs et les mêmes structures de contrôle qu'on le ferait dans ces deux langages. Mais nous pouvons cependant noter quelques différences de syntaxe :

• les définitions commencent par un mot réservé. Les définitions de fonctions sont introduites par def, les définitions de variables par var et les définitions de valeurs (des variables en lecture seule) par val ;
• le type d'un symbole est placé après le symbole et le signe deux-points. Ce type peut souvent être omis, car le compilateur peut le déduire du contexte ;
• les types tableaux s'écrivent Array[T] au lieu de T[] et l'accès à un élément se note a(i) et non a[i] ;
• les fonctions peuvent être imbriquées. Une fonction « interne » peut accéder aux paramètres et aux variables locales de sa fonction englobante. Le nom de tableau xs, par exemple, est visible dans les fonctions swap et sort1 et n'a donc pas besoin de leur être passé en paramètre.

Pour l'instant, Scala ressemble à un langage assez conventionnel avec quelques spécificités syntaxiques. De fait, vous pouvez écrire vos programmes dans un style impératif classique ou selon le paradigme orienté objet. C'est un point important, car c'est l'une des choses qui permettent de combiner aisément des composants Scala avec des composants écrits en Java, C# ou Visual Basic.

Cependant, vous pouvez également utiliser un style de programmation totalement différent. Voici à nouveau la fonction de tri rapide, cette fois-ci écrite dans un style fonctionnel :

def sort(xs: Array[Int]): Array[Int] = {
    if (xs.length <= 1) xs
    else {
        val pivot = xs(xs.length / 2)
        Array.concat(sort(xs filter (pivot >)),
                     xs filter (pivot ==),
                     sort(xs filter (pivot <)))

Ce programme fonctionnel capture de façon concise l'essence même de l'algorithme du tri rapide :

• si le tableau est vide ou n'a qu'un seul élément, alors il est déjà trié et on le renvoie immédiatement ;
• si le tableau n'est pas vide, on choisit un élément situé au milieu, qui servira de « pivot » ;
• on divise le tableau en trois tableaux contenant, respectivement, les éléments plus petits que le pivot, les éléments plus grands que le pivot et les éléments égaux au pivot (1)  ;
• on trie les deux premiers sous-tableaux en appelant récursivement la fonction de tri ;
• le résultat est obtenu en concaténant ces trois sous-tableaux.

Les implémentations impérative et fonctionnelle ont la même complexité asymptotique - kitxmlcodeinlinelatexdvpO(N \log(N))finkitxmlcodeinlinelatexdvp en moyenne et kitxmlcodeinlinelatexdvpO(N^2)finkitxmlcodeinlinelatexdvp dans le pire des cas. Cependant, alors que la première agit sur place en modifiant son paramètre tableau, la seconde renvoie un nouveau tableau trié sans modifier son paramètre - elle nécessite donc plus de mémoire temporaire que la version impérative.

L'implémentation fonctionnelle peut donner l'impression que Scala est un langage spécialisé dans le traitement fonctionnel des tableaux. Ce n'est pas le cas : toutes les opérations utilisées dans cet exemple sont, en réalité, de simples appels de méthodes de la classe Seq[T], qui décrit les séquences et qui fait partie de la bibliothèque standard de Scala, elle-même écrite en Scala. Les tableaux étant des instances de Seq, toutes les méthodes sur les séquences peuvent donc leur être appliquées.

La méthode filter, par exemple, prend en paramètre une fonction prédicat qui associe des valeurs booléennes à chaque élément du tableau. Le résultat est un tableau contenant tous les éléments du tableau initial qui vérifient ce prédicat. La méthode filter d'un objet de type Array[T] a donc la signature suivante :

def filter(p: T => Boolean): Array[T]

Ici, T => Boolean est le type des fonctions prenant un élément de type T et renvoyant un Boolean. Les fonctions comme filter, qui prennent une autre fonction en paramètre ou qui renvoient une fonction comme résultat, sont appelées des fonctions d'ordre supérieur.

Scala ne fait pas de différence entre les noms de méthodes et les noms d'opérateurs. Un nom de méthode peut être une suite de lettres et de chiffres commençant par une lettre ou une suite de caractères spéciaux comme « + », « * » ou « : ». En Scala, tout identifiant peut être utilisé comme opérateur infixé : l'opération binaire E op E' sera toujours interprétée comme l'appel de méthode E.op(E'). Ceci est également vrai pour les opérateurs binaires infixés dont le nom commence par une lettre : l'expression xs filter (pivot >) est équivalente à l'invocation de méthode xs.filter(pivot >).

Dans l'exemple du tri rapide, filter est appliquée trois fois à un paramètre qui est une fonction anonyme. Lors du premier appel, pivot > représente la fonction qui prend un paramètre x et renvoie la valeur pivot > x. C'est un exemple d'application partielle d'une fonction. Une autre façon d'écrire ce paramètre aurait été de rendre x explicite, en utilisant la notation x => pivot > x. Cette fonction est anonyme, car elle n'a pas de nom qui lui est associé. Ici, le type du paramètre x a été omis, car le compilateur Scala est capable de l'inférer automatiquement à partir du contexte d'utilisation de la fonction. Pour résumer, xs.filter(pivot >) renvoie la liste de tous les éléments de la liste xs inférieurs à pivot.

Si vous examinez à nouveau en détail la première implémentation impérative du tri rapide, vous pourrez constater qu'elle utilise également la plupart des constructions de la seconde solution, mais sous forme déguisée.

Les opérateurs « standard » comme +, - ou <, par exemple, ne sont pas traités de façon spéciale : comme append, ce sont des méthodes de leur opérande gauche. Par conséquent, l'expression i + 1 est considérée comme l'invocation i.+(1) de la méthode + de la valeur entière i. Un compilateur peut évidemment (et devrait, s'il est suffisamment astucieux) reconnaître qu'il s'agit d'un cas particulier d'appel de la méthode + sur des opérandes entiers et produire un code optimisé pour cette opération.

Pour des raisons d'efficacité et pour améliorer les diagnostics d'erreurs, la boucle while est une construction primitive en Scala, mais, en principe, elle aurait très bien pu être écrite comme une fonction prédéfinie. En voici une implémentation possible :

def While (p: => Boolean) (s: => Unit) {
    if (p) { s ; While(p)(s) }
}

La fonction While prend une fonction de test comme premier paramètre. Celle-ci n'attend pas de paramètre et produit une valeur booléenne. Le second paramètre de While est une fonction commande qui ne prend pas non plus de paramètre et qui produit un résultat de type Unit. While appelle la fonction commande tant que la fonction de test renvoie true.

Le type Unit correspond en gros au void de Java : il est utilisé à chaque fois qu'une fonction ne renvoie pas de résultat intéressant. En fait, Scala étant un langage orienté expressions, chaque fonction renvoie un résultat : si aucune expression explicite n'est renvoyée, c'est la valeur () (qui se prononce « unit ») qui est renvoyée par défaut. Les fonctions qui renvoient le type Unit sont également appelées procédures. Voici, par exemple, une version « orientée expression » de la fonction swap de la première version du tri rapide qui renvoie explicitement « unit » :

def swap(i: Int, j: Int) {
    val t = xs(i); xs(i) = xs(j); xs(j) = t
    ()
}

La valeur renvoyée par cette fonction est simplement celle de sa dernière expression - il n'y a pas besoin du mot-clé return. Notez que les fonctions qui renvoient une valeur qui n'est pas de type Unit doivent toujours avoir un = avant leur corps ou l'expression qui les définit (comme le fait notre version fonctionnelle de la fonction sort).