8. Types et méthodes génériques▲
En Scala, les classes peuvent avoir des paramètres de type. Nous allons illustrer l'utilisation de ces paramètres de type avec un exemple de pile fonctionnelle. Supposons que nous voulions créer un type de données pour représenter les piles d'entiers, avec les méthodes push, top, pop et isEmpty. Voici la hiérarchie de classes correspondante :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
abstract class IntStack {
def push(x: Int): IntStack = new IntNonEmptyStack(x, this)
def isEmpty: Boolean
def top: Int
def pop: IntStack
}
class IntEmptyStack extends IntStack {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")
}
class IntNonEmptyStack(elem: Int, rest: IntStack) extends IntStack {
def isEmpty = false
def top = elem
def pop = rest
}
Il serait bien sûr tout aussi judicieux de définir une pile pour les chaînes de caractères. Pour ce faire, nous pourrions reprendre InStack, la renommer en StringStack et remplacer toutes les occurrences de Int par String.
Une meilleure approche, qui évite de dupliquer le code, consiste à paramétrer les définitions des piles avec le type de leurs éléments. Cette paramétrisation nous permet de passer d'une représentation spécifique d'un problème à une représentation plus générale. Jusqu'à maintenant, nous n'avions paramétré que des valeurs, mais nous pouvons faire de même pour les types. Pour disposer d'une version générique de Stack, il suffit donc de lui ajouter un paramètre de type :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
abstract class Stack[A] {
def push(x: A): Stack[A] = new NonEmptyStack[A](x,this)
def isEmpty: Boolean
def top: A
def pop: Stack[A]
}
class EmptyStack[A] extends Stack[A] {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")
}
class NonEmptyStack[A](elem: A, rest: Stack[A]) extends Stack[A] {
def isEmpty = false
def top = elem
def pop = rest
}
Dans ces définitions, A est le paramètre de type de la classe Stack et de ses sous-classes. Le nom de ce paramètre n'a pas d'importance ; il doit être placé entre crochets afin de le distinguer des paramètres classiques. Voici un exemple d'utilisation de ces classes génériques :
2.
3.
val x = new EmptyStack[Int]
val y = x.push(1).push(2)
println(y.pop.top)
La première ligne crée une pile vide de Int. Notez l'argument effectif [Int] qui remplace le paramètre de type formel [A].
Les méthodes peuvent également être paramétrées par des types. Voici, par exemple, une méthode générique qui teste si une pile est préfixe d'une autre :
2.
3.
4.
def isPrefix[A](p: Stack[A], s: Stack[A]): Boolean = {
p.isEmpty ||
p.top == s.top && isPrefix[A](p.pop, s.pop)
}
Les paramètres de la méthode sont polymorphes - c'est la raison pour laquelle les méthodes génériques sont également appelées méthodes polymorphes. Ce terme est un mot grec qui signifie « avoir plusieurs formes ». Pour appliquer une méthode polymorphe comme isPrefix, vous devez lui fournir les paramètres de type ainsi que les paramètres valeurs :
2.
3.
val s1 = new EmptyStack[String].push("abc")
val s2 = new EmptyStack[String].push("abx").push(s1.top)
println(isPrefix[String](s1, s2))
Inférence de type locale. Passer constamment des paramètres de type comme [Int] ou [String] peut devenir assez lourd lorsque l'on utilise beaucoup les méthodes génériques. Assez souvent, l'indication d'un paramètre de type est redondante, car le type de paramètre correct peut également être déterminé en inspectant les paramètres valeurs de la fonction ou le type de son résultat. Si l'on prend comme exemple l'expression isPrefix[String](s1, s2), on sait que ses paramètres valeurs sont tous les deux de type Stack[String] et l'on peut donc déduire que le paramètre de type doit être String. Scala dispose d'un « inférenceur » (ou déducteur) de type assez puissant permettant d'omettre les paramètres de type des fonctions polymorphes et des constructeurs dans des situations comme celle-ci. Dans l'exemple ci-dessus, nous aurions donc simplement pu écrire isPrefix(s1, s2) et le paramètre de type manquant, [String], aurait été inséré par l'inférenceur de type.
8-1. Bornes des paramètres de type▲
Maintenant que nous savons créer des classes génériques, il est naturel de vouloir généraliser certaines de nos classes précédentes. La classe IntSet, par exemple, pourrait être étendue aux ensembles d'éléments de types quelconques :
2.
3.
4.
abstract class Set[A] {
def incl(x: A): Set[A]
def contains(x: A): Boolean
}
Cependant, si nous voulons toujours les implémenter comme des arbres de recherche binaires, nous allons avoir un problème. En effet, les méthodes contains et incl comparent toutes les deux les éléments à l'aide des méthodes < et >. Ceci ne posait pas de problème avec Intset, car le type Int dispose de ces deux méthodes, mais nous ne pouvons pas le garantir pour un paramètre de type a quelconque. L'implémentation précédente de contains produira donc une erreur de compilation.
2.
3.
def contains(x: Int): Boolean =
if (x < elem) left contains x
^ < not a member of type A.
Une façon de résoudre ce problème consiste à restreindre les types autorisés à se substituer au type A à ceux qui contenant les méthodes < et > avec les signatures adéquates. La bibliothèque standard de Scala contient un trait Ordered[A] qui représente les valeurs comparables (avec < et >) à des valeurs de type A. Ce trait est défini de la façon suivante :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
/** Classe représentant les données totalement ordonnées */
trait Ordered[A] {
/** Résultat de la comparaison de 'this' avec 'that'.
* renvoie 'x' avec :
* x < 0 ssi this < that
* x == 0 ssi this == that
* x > 0 ssi this > that
*/
def compare(that: A): Int
def < (that: A) : Boolean = (this compare that) < 0
def > (that: A) : Boolean = (this compare that) > 0
def <= (that: A) : Boolean = (this compare that) <= 0
def >= (that: A) : Boolean = (this compare that) >= 0
def compareTo(that: A): Int = compare(that)
}
Nous pouvons imposer la compatibilité d'un type en demandant qu'il soit un sous-type de Ordered. Pour ce faire, nous fixons une borne supérieure au paramètre de type de Set :
2.
3.
4.
trait Set[A <: Ordered[A]] {
def incl(x: A): Set[A]
def contains(x: A): Boolean
}
La déclaration A <: Ordered[A] précise que A est un paramètre de type et qu'il doit être un sous-type de Ordered[A], c'est-à-dire que ses valeurs doivent être comparables entre elles.
Grâce à cette restriction, nous pouvons maintenant implémenter le reste de notre ensemble générique, comme nous l'avions fait pour IntSet :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
class EmptySet[A <: Ordered[A]] extends Set[A] {
def contains(x: A): Boolean = false
def incl(x: A): Set[A] = new NonEmptySet(x, new EmptySet[A], new EmptySet[A])
}
class NonEmptySet[A <: Ordered[A]] (elem: A, left: Set[A], right: Set[A])
extends Set[A] {
def contains(x: A): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: A): Set[A] =
if (x < elem) new NonEmptySet(elem, left incl x, right)
else if (x > elem) new NonEmptySet(elem, left, right incl x)
else this
}
Notez que nous n'avons pas indiqué l'argument de type lors des créations d'objets new NonEmptySet(...). Tout comme pour les méthodes polymorphes, les arguments de type absents lors des appels aux constructeurs peuvent être inférés à partir des arguments valeurs et/ou du type de résultat attendu.
Voici un exemple utilisant l'abstraction des ensembles génériques. Commençons par créer une sous-classe de la classe Ordered :
2.
3.
4.
5.
6.
case class Num(value: Double) extends Ordered[Num] {
def compare(that: Num): Int =
if (this.value < that.value) -1
else if (this.value > that.value) 1
else 0
}
Puis :
val s = new EmptySet[Num].incl(Num(1.0)).incl(Num(2.0))
s.contains(Num(1.5))Tout va bien puisque le type Num implémente le trait Ordered[Num]. En revanche, le code suivant est erroné :
val s = new EmptySet[java.io.File]
^ java.io.File does not conform to type
parameter bound Ordered[java.io.File].Un problème avec les bornes des paramètres de types est qu'il faut être prévoyant : si nous n'avions pas déclaré Num comme sous-classe de Ordered, nous n'aurions pas pu utiliser les éléments Num dans les ensembles. Pour la même raison, les types hérités de Java - comme Int, Double ou String - n'étant pas des sous-classes de Ordered, leurs valeurs ne peuvent pas être utilisées comme éléments d'un ensemble.
Une conception plus souple, qui permet d'utiliser des éléments de ces types, consiste à utiliser des bornes de vues à la place des bornes de vrais types que nous avons vues jusqu'à maintenant. La seule modification de code dans l'exemple précédent consiste à changer les paramètres de généricité :
2.
3.
4.
5.
6.
7.
8.
trait Set[A <% Ordered[A]]
…
class EmptySet[A <% Ordered[A]]
…
class NonEmptySet[A <% Ordered[A]]
...
Les bornes de vues <% sont plus faibles que les bornes réelles <:. Une clause de borne de vue [A <% T] précise simplement que le type A doit être convertible dans le type de la borne T à l'aide d'une conversion implicite.
La bibliothèque standard de Scala prédéfinit des conversions implicites pour un certain nombre de types, notamment les types primitifs et String. Par conséquent, notre nouvelle abstraction des ensembles peut désormais également être instanciée avec ces types. Vous trouverez plus d'informations sur les conversions implicites au chapitre 15Paramètres et conversions implicites.
8-2. Annotation de variance▲
La combinaison des paramètres de type et du sous-typage pose quelques questions intéressantes. Est-ce que Stack[String] doit être un sous-type de Stack[AnyRef], par exemple ? Intuitivement, ceci semble être le cas puisqu'une pile de String est un cas particulier d'une pile de AnyRef. De façon générale, si T est un sous-type de S, alors Stack[T] devrait être un sous-type de Stack[S]. Cette propriété est appelée sous-typage covariant.
En Scala, les types utilisent, par défaut, un sous-typage covariant. Avec notre classe Stack telle qu'elle est définie, les piles de différents types d'éléments ne seront jamais dans une relation de sous-typage, mais nous pouvons imposer un sous-typage covariant des piles en modifiant la première ligne de la définition de la classe :
class Stack[+A] {Un paramètre formel de type préfixé par + indique que le sous-typage sera covariant pour ce paramètre. Il existe également le préfixe - qui indique un sous-type contra-variant : si Stack avait été définie par class Stack[-A] ... , Stack[S] serait un sous-type de Stack[T] si T est un sous-type de S (ce qui, dans le cas de nos piles, serait assez surprenant !).
Dans un monde purement fonctionnel, tous les types pourraient être covariants. Cependant, la situation change lorsque l'on introduit des données modifiables. Par exemple, les tableaux Java ou .NET sont représentés en Scala par la classe générique Array dont voici une définition partielle :
2.
3.
4.
class Array[A] {
def apply(index: Int): A
def update(index: Int, elem: A)
}
Cette classe définit la façon dont sont vus les tableaux Scala par les programmes clients. Dans la mesure du possible, le compilateur fera correspondre cette abstraction aux tableaux sous-jacents du système hôte.
En Java, les tableaux sont évidemment covariants : si T et S sont des types références et que T est sous-type de S, alors Array[T] est également un sous-type de Array[S]. Ceci semble naturel, mais peut poser des problèmes nécessitant des vérifications spéciales lors de l'exécution :
2.
3.
val x = new Array[String](1)
val y: Array[Any] = x
y(0) = new Rational(1, 2) // sucre syntaxique pour y.update(0, new Rational(1, 2))
La première ligne crée un tableau de chaînes de caractères. La seconde lie ce tableau à une variable y de type Array[Any], ce qui est correct puisque les tableaux sont covariants : Array[String] est donc un sous-type de Array[Any]. Enfin, la dernière ligne stocke un nombre rationnel dans le tableau y, ce qui également permis puisque le type Rational est un sous-type de Any, le type des éléments de y. Finalement, nous avons donc stocké un nombre rationnel dans un tableau de chaînes, ce qui viole clairement notre notion des types.
Java résout ce problème en introduisant un test à l'exécution dans la troisième ligne, afin de vérifier que l'élément stocké est compatible avec celui des éléments du tableau tel qu'il a été créé. Nous avons vu dans l'exemple que ce type des éléments n'est pas nécessairement le type statique du tableau mis à jour. Si le test échoue, l'exception ArrayStoreException est générée.
Scala, quant à lui, résout ce problème de façon statique, en interdisant la seconde ligne lors de la compilation puisque les tableaux Scala ont un sous-typage non variant. Ceci pose donc la question de savoir comment un compilateur Scala vérifie que les annotations de variance sont correctes. Si nous avions simplement déclaré les tableaux comme covariants, comment aurait-on pu détecter ce problème ?
Scala utilise une approximation prudente pour vérifier la cohérence des annotations de variance. Un paramètre de type covariant d'une classe ne peut apparaître qu'aux positions covariantes de la classe - les types des valeurs dans la classe, les types des résultats des méthodes de la classe et les paramètres de type des autres types covariants, notamment. Les types des paramètres formels des méthodes ne sont pas des positions covariantes. La définition de classe suivante est donc incorrecte :
2.
3.
4.
5.
6.
class Array[+A] {
def apply(index: Int): A
def update(index: Int, elem: A)
^ covariant type parameter A appears
in contravariant position.
}
Pour l'instant, tout va bien. Intuitivement, le compilateur a bien fait de rejeter la procédure update dans une classe covariante, car cette méthode peut modifier l'état et donc perturber la cohérence du sous-typage covariant.
Cependant, certaines méthodes ne modifient pas l'état et ont un paramètre de type qui apparaîtra donc comme contra-variant - c'est le cas de la méthode push de la classe Stack, par exemple. Là aussi, le compilateur Scala rejettera la définition de cette méthode pour des piles covariantes :
2.
3.
4.
class Stack[+A] {
def push(x: A): Stack[A] =
^ covariant type parameter A appears
in contravariant position.
C'est dommage, car, à la différence des tableaux, les piles sont des structures de données fonctionnelles pures et elles devraient donc autoriser un sous-typage covariant. Il existe toutefois un moyen de résoudre ce problème à l'aide d'une méthode polymorphe avec une borne inférieure pour le paramètre de type.
8-3. Bornes inférieures▲
Nous venons de voir les bornes supérieures pour les paramètres de type : dans une clause comme T <: U, le paramètre type T est limité aux sous-types de U. Il existe également des bornes inférieures : dans la clause T >: S, le paramètre type T est limité aux types parents de S (il est également possible de combiner les bornes inférieures et supérieures, avec une clause comme T >: S <: U).
Les bornes inférieures vont nous permettre de généraliser la méthode push de la classe Stack :
class Stack[+A] {
def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)Techniquement, ceci résout notre problème de variance puisque, désormais, le paramètre de type A n'est plus un paramètre de type de la méthode push, mais une borne inférieure d'un autre type paramètre, qui se trouve dans une position covariante. Le compilateur Scala acceptera donc cette nouvelle définition.
En réalité, nous avons non seulement résolu ce problème de variance, mais nous avons également généralisé la définition de push. Auparavant, cette méthode ne pouvait empiler que des éléments dont les types étaient conformes au type d'élément de la pile. Désormais, nous pouvons également empiler des éléments qui sont d'un type parent de ce type et la pile renvoyée sera d'un type modifié en conséquence. Nous pouvons, par exemple, empiler un AnyRef sur une pile de String : le résultat sera une pile d'AnyRef et non une pile de String.
En résumé, n'hésitez pas à ajouter des annotations de variance à vos structures de données, car cela produit des relations de sous-typage riches et naturelles. Le compilateur détectera les éventuels problèmes de cohérence. Lorsque l'approximation du compilateur est trop prudente, comme dans le cas de la méthode push de la classe Stack, cela suggère souvent une généralisation utile de la méthode concernée.
8-4. Types minimaux▲
Scala ne permet pas de paramétrer les objets avec des types. C'est la raison pour laquelle nous avions défini une classe EmptyStack[A] alors qu'une unique valeur suffisait pour représenter les piles vides de type quelconque. Pour les piles covariantes, vous pouvez toutefois utiliser l'idiome suivant :
object EmptyStack extends Stack[Nothing] { ... }Le type minimal Nothing ne contenant aucune valeur, le type Stack[Nothing] exprime le fait qu'une EmptyStack ne contient aucun élément. En outre, Nothing est un sous-type de tous les autres types ce qui signifie que, pour les piles covariantes, Stack[Nothing] est un sous-type de Stack[T] quel que soit T. Nous pouvons donc désormais utiliser un unique objet pile vide dans le code client :
val s = EmptyStack.push("abc").push(new AnyRef())Analysons en détail l'affectation des types dans cette expression. L'objet EmptyStack est de type Stack[Nothing] et dispose donc d'une méthode
push[B >: Nothing](elem: B): Stack[B]L'inférence de type locale déterminera que B doit être instancié par String lors de l'appel EmptyStack.push("abc"). Le type du résultat de cet appel est donc Stack[String] qui, à son tour, dispose d'une méthode
push[B >: String](elem: B): Stack[B]La dernière partie de la définition de valeur est l'appel de cette méthode auquel on passe new AnyRef() en paramètre de type. L'inférence de type locale déterminera que le paramètre de type devrait cette fois-ci être instancié par AnyRef et que le résultat sera donc de type Stack[AnyRef]. Le type de la valeur affectée à s est donc Stack[AnyRef].
Outre Nothing, qui est un sous-type de tous les autres types, il existe également le type Null, qui est un sous-type de scala.AnyRef et de toutes ses classes filles. En Scala, le littéral null est la seule valeur de ce type, ce qui la rend compatible avec tous les types référence, mais pas avec un type valeur comme Int.
Nous conclurons cette section par une définition complète de notre classe Stack. Les piles ont désormais un sous-typage covariant, la méthode push a été généralisée et la pile vide est représentée par un objet unique :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
abstract class Stack[+A] {
def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)
def isEmpty: Boolean
def top: A
def pop: Stack[A]
}
object EmptyStack extends Stack[Nothing] {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")
}
class NonEmptyStack[+A](elem: A, rest: Stack[A]) extends Stack[A] {
def isEmpty = false
def top = elem
def pop = rest
}
De nombreuses classes de la bibliothèque Scala sont génériques et nous allons maintenant présenter les deux familles les plus courantes : les tuples et les fonctions. Les listes, qui sont également très utilisées, seront présentées dans le prochain chapitre.
8-5. Tuples▲
Une fonction doit parfois pouvoir renvoyer plusieurs résultats. La fonction divmod, par exemple renvoie le quotient entier et le reste de la division de ses deux paramètres entiers. Nous pourrions évidemment définir une classe pour encapsuler ces deux résultats de divmod :
case class TwoInts(first: Int, second: Int)
def divmod(x: Int, y: Int): TwoInts = new TwoInts(x / y, x % y)Mais devoir définir une nouvelle classe pour chaque paire de types de résultats possibles serait très lourd. En Scala, nous pouvons plutôt utiliser la classe générique Tuple2, qui est définie ainsi :
package scala
case class Tuple2[A, B](_1: A, _2: B)Avec Tuple2, la méthode divmod peut être écrite de la façon suivante :
def divmod(x: Int, y: Int) = new Tuple2[Int, Int](x / y, x % y)Comme d'habitude, les paramètres de type du constructeur peuvent être omis s'ils peuvent être déduits des arguments passés à l'appel. Il existe également des classes tuples pour contenir n'importe quel autre nombre d'éléments (l'implémentation actuelle limite ce nombre à une valeur raisonnable).
Les tuples étant des case classes, les éléments des tuples peuvent être accédés de deux façons différentes. La première consiste à utiliser les noms des paramètres _i du constructeur, comme dans cet exemple :
val xy = divmod(x, y)
println("quotient: " + xy._1 + ", rest: " + xy._2)La seconde consiste à utiliser la reconnaissance de motif sur les tuples, comme ici :
2.
3.
4.
divmod(x, y) match {
case Tuple2(n, d) =>
println("quotient: " + n + ", rest: " + d)
}
Notez que les paramètres de types ne sont jamais utilisés dans les motifs - l'écriture Tuple2[Int, Int](n, d) serait illégale.
Les tuples sont si pratiques que Scala définit une syntaxe spéciale pour faciliter leur utilisation. Pour un tuple de n éléments x1, … xn, nous pouvons écrire (x1 ... xn) à la place de Tuplen(x1, ..., x n). La syntaxe (...) fonctionnant à la fois pour les types et les motifs, l'exemple précédent peut donc être réécrit de la manière suivante :
2.
3.
4.
5.
def divmod(x: Int, y: Int): (Int, Int) = (x / y, x % y)
divmod(x, y) match {
case (n, d) => println("quotient: " + n + ", rest: " + d)
}
8-6. Fonctions▲
Scala est un langage fonctionnel, car les fonctions sont des valeurs de première classe. C'est également un langage orienté objet, car chaque valeur est un objet. Il s'ensuit donc qu'en Scala les fonctions sont des objets. Une fonction de String vers Int, par exemple, sera représentée comme une instance du trait Function1[String, Int]. Le trait Function1 est défini de la façon suivante dans la bibliothèque standard :
2.
3.
package scala trait Function1[-A, +B] {
def apply(x: A): B
}
Outre Function1, il existe également des définitions pour les fonctions ayant d'autres arités ou nombres d'arguments (l'implémentation actuelle autorise une limite raisonnable). Il y a donc une seule définition pour chaque nombre de paramètres possible. La syntaxe des types fonctions en Scala, (T1, ..., Tn) => S est simplement un raccourci pour le type paramétré Functionn[T1, ..., Tn,S].
Scala utilise la même syntaxe f(x) pour l'application de fonction, que f soit une méthode ou un objet fonction. Ceci est possible en raison de la convention suivante : une application de fonction f(x) où f est un objet (et non une méthode) est un raccourci de f.apply(x). La méthode apply d'un type fonction est donc insérée automatiquement lorsque cela est nécessaire.
C'est également la raison pour laquelle nous avons défini l'indexation des tableaux dans la section 8.2Annotation de variance par une méthode apply. Pour tout tableau a, l'opération a(i) est un raccourci de a.apply(i).
Les fonctions sont un exemple d'utilisation d'un paramètre de type contra-variant. Étudiez, par exemple, le code suivant :
2.
3.
val f: (AnyRef => Int) = x => x.hashCode()
val g: (String => Int) = f
g("abc")
Il semble logique de lier la valeur g de type String => Int à f qui est de type AnyRef => Int. En effet, tout ce que l'on peut faire avec une fonction de type String => Int est de lui passer une chaîne afin d'obtenir un entier. Il en va de même pour la fonction f : si nous lui passons une chaîne (ou un autre objet), nous obtenons un entier. Ceci démontre que le sous-typage d'une fonction est contra-variant pour le type de son argument alors qu'il est covariant pour le type de son résultat. En résumé, S => T est un sous-type de S => T' si S' est un sous-type de S et T est un sous-type de T'.
Exemple 8-6-1 : Ce code :
val plus1:(Int => Int) = (x: Int) => x + 1
plus1(2)est traduit dans le code suivant :
2.
3.
4.
val plus1: Function1[Int, Int] = new Function1[Int, Int] {
def apply(x: Int): Int = x + 1
}
plus1.apply(2)
Ici, la création d'objets new Function1[Int, Int]{ … } représente une instance d'une classe anonyme. Elle combine la création d'un nouvel objet Function1 avec une implémentation de la méthode apply (qui est abstraite dans Function1). Nous aurions également pu utiliser une classe locale, mais cela aurait été plus lourd :
2.
3.
4.
5.
6.
val plus1: Function1[Int, Int] = {
class Local extends Function1[Int, Int] {
def apply(x: Int): Int = x + 1 new Local: Function1[Int, Int]
}
}
plus1.apply(2)