A Gentle Introduction to Haskell, version 98

Il y a une dernière particularité du système de typage de Haskell qui le sépare des autres langages de programmation. Le genre de polymorphisme dont nous avons parlé jusque là est communément appelé polymorphisme paramétrique. Il existe un autre genre appelé polymorphisme ad hoc, plus connu sous le nom de surcharge. Voici quelques exemples de polymorphisme ad hoc :

• Les littéraux 1, 2, etc. sont souvent utilisés pour représenter à la fois les entiers à longueur fixe ou à longueur arbitraire.
• Les opérateurs numériques tels que + sont souvent définis pour opérer sur plusieurs types de nombres.
• L'opérateur d'égalité (== dans Haskell) opère sur des nombres, mais également sur beaucoup (mais pas tous) d'autres types.

Notez que le comportement de ces opérateurs surchargés est différent pour chaque type (en fait, le comportement est parfois indéfini ou une erreur), tandis qu'avec le polymorphisme paramétrique le type n'a pas d'influence (frange, par exemple, ne se soucie pas de savoir quel type d'éléments se trouve dans les feuilles de son arborescence). Dans Haskell, les classes de types permettent de contrôler de manière structurée les polymorphismes ad hoc, ou surcharge.

Commençons avec un exemple simple, mais important : l'égalité. Il y a beaucoup de types pour lesquels nous voudrions que l'égalité soit définie, mais d'autres pour lesquels nous ne le voulons pas. Par exemple, on considère généralement qu'il est trop difficile d'informatiser le calcul de l'égalité entre des fonctions, par contre nous avons souvent besoin de comparer l'égalité de deux listes. Le genre d'égalité dont nous parlons ici est l'« égalité de valeurs », à l'opposé de l'« égalité de pointeurs » que l'on trouve, par exemple, avec le == dans java. L'égalité de pointeurs n'est pas référentiellement transparente et ne s'adapte pas bien dans un langage purement fonctionnel. Pour mettre en évidence ce sujet, considérons cette définition d'une fonction elem qui teste l'appartenance à une liste :

x  `elem `  []             = False
x  `elem ` (y :ys)         = x==y || (x  `elem ` ys)

Pour des raisons stylistiques discutées dans la section 3.1, nous avons choisi de définir elem dans une forme infixée. == et || sont, respectivement, les opérateurs infixes de l'égalité et le ou logique.

Intuitivement, le type de elem « doit » être : a->[a]->Bool. Mais cela impliquerait que == est de type a->a->Bool, quand bien même nous venons de dire que nous ne nous attendions pas à ce que == soit défini pour tous les types.

De plus, comme nous l'avons noté plus haut, même si == était défini pour tous les types, la comparaison de deux listes pour tester leur égalité ou la comparaison de deux entiers sont deux choses très différentes. En ce sens, nous nous attendons à ce que == soit surchargé pour mener ces différentes tâches.

Les classes de types permettent de résoudre ces deux problèmes. Elles permettent de déclarer tels types comme des instances de telles classes, et de fournir des définitions pour les opérations surchargées associées à une classe. Par exemple, définissons une classe de type contenant un opérateur d'égalité :

class Eq a where 
  (==)                  :: a -> a -> Bool

Ici, Eq est le nom de la classe que l'on définit, et == est l'unique opérateur dans cette classe. Cette déclaration peut être lue « un type a est une instance de la classe Eq s’il existe une opération (surchargée) ==, de type approprié, défini pour celui-ci ». (Notez que == est uniquement défini pour des paires d'objets de même type.)

La contrainte qui impose que a doit être une instance de la classe Eq s'écrit Eq a. Donc Eq a n'est pas une expression de type, mais plutôt l'expression d'une contrainte sur un type, que l'on appelle un contexte. Les contextes sont placés au début d'expressions de type. Par exemple, l'effet de la déclaration de classe ci-dessus est d'assigner le type suivant à == :

(==)                    :: (Eq a) => a -> a -> Bool

Ceci devrait se lire « Pour tout type a étant une instance de la classe Eq, == est de type a->a->Bool ». C'est ce type qui serait utilisé pour == dans l'exemple elem, et en fait, la contrainte imposée par le contexte se propage au type principal de elem :

elem                    :: (Eq a) => a -> [a] -> Bool

Ce qui se lit « Pour tout type a étant une instance de la classe Eq, elem est de type a->[a]->Bool ». C'est exactement ce que nous voulons –cela exprime le fait que elem n'est pas défini pour tous les types, mais seulement pour ceux dont nous savons déterminer l'égalité des éléments.

Jusque là, tout va bien. Mais comment faire pour spécifier quels types sont des instances de la classe Eq, ainsi que le comportement de == sur chacun de ces types? Cela ce fait à l'aide d'une déclaration d'instance. Par exemple :

instance Eq Integer where 
  x == y                =  x  `integerEq ` y

Cette définition de == est appelée une méthode. La fonction integerEq est une fonction primitive qui teste l'égalité entre deux entiers, mais en général n'importe quelle expression valide est autorisée dans le terme droit, comme pour n'importe quelle définition de fonction. Dans son ensemble, cette déclaration signifie « Le type Integer est une instance de la classe Eq, et voici la définition de la méthode correspondant à l'opération == ». Cette déclaration donnée, nous pouvons maintenant tester l'égalité de l'ensemble fini d'entiers en utilisant ==. De la même manière :

instance Eq Float where
  x == y                =  x  `floatEq ` y

nous permet de comparer des nombres à virgule flottante en utilisant ==. Les types récursifs tels que Arborescence définis précédemment peuvent aussi être gérés :

instance (Eq a) => Eq (Arborescence a) where 
  Feuille a         ==  Feuille b          =  a == b
  (Branche l1 r1)   ==  (Branche l2 r2)    =  (l1==l2) && (r1==r2)
  _                 ==  _                  =  False

Notez le contexte Eq a sur la première ligne –il est nécessaire parce que les éléments dans les feuilles (de type a) sont comparés pour tester leur égalité sur la seconde ligne. Cette contrainte additionnelle dit essentiellement que nous pouvons comparer des arborescences de a pour tester leur égalité à condition que nous soyons capables de tester l'égalité des a. Si le contexte était omis dans la déclaration d'instance, une erreur de type statique en résulterait.

Le Haskell Report, et particulièrement le Prélude, contient nombre d'exemples utiles de classes de types. En fait, une classe Eq y est définie et est légèrement plus longue que celle que nous avons définie plus haut :

class  Eq a  where
  (==), (/=)            :: a -> a -> Bool
  x /= y                =  not (x == y)

C'est un exemple de classe comprenant deux opérations, une pour l'égalité, l'autre pour l'inégalité. C'est aussi une démonstration de l'utilisation d'une méthode par défaut, dans ce cas pour l'opération d'inégalité /=. Si la méthode d'une opération particulière est omise dans une déclaration d'instance, alors la méthode par défaut définie dans la déclaration de classe, si elle existe, est utilisée. Par exemple, les trois instances de Eq définies plus tôt fonctionneront parfaitement avec la déclaration de classe ci-dessus, fournissant exactement la définition de l'inégalité que nous voulons : la négation logique de l'égalité.

Haskell supporte également la notion d'extension de classe. Par exemple, nous pourrions avoir besoin de définir une classe Ord qui hérite de toutes les opérations définies dans Eq, mais qui disposerait, en plus, d'un ensemble d'opérations de comparaison et des fonctions minimum et maximum :

class  (Eq a) => Ord a  where
  (<), (<=), (>=), (>)  :: a -> a -> Bool
  max, min              :: a -> a -> a

Notez le contexte dans la déclaration de class. Nous disons que Eq est une superclasse de Ord (à l'inverse, Ord est une sous-classe de Eq), et tout type étant une instance de Ord doit aussi être une instance de Eq. (Dans la section suivante, nous donnons une définition plus complète de Ord extraite du Prélude)

Un des bénéfices de telles inclusions de classes est que les contextes sont plus courts : Une expression de type pour une fonction qui utilise à la fois Eq et Ord peut utiliser le contexte (Ord a), plutôt que (Eq a, Ord a), puisque Ord « implique » Eq. Plus important encore, les méthodes pour les opérations des sous-classes peuvent supposer l'existence de méthodes définies pour les opérations des superclasses. Par exemple, la déclaration de Ord dans le Prélude Standard contient cette méthode par défaut pour (<) :

x < y               =  x <= y && x /= y

Pour un exemple de l'utilisation de Ord, le typage principal de quicksort défini dans la section 2.4.1 est :

quicksort               ::  (Ord a) => [a] -> [a]

En d'autres termes, quicksort n'opère que sur des listes de valeurs de type ordonné. Ce typage de quicksort est attribué en raison de l'utilisation des opérateurs de comparaison < et >= dans sa définition.

Haskell permet également l'« héritage multiple », puisque les classes peuvent avoir plus d'une superclasse. Par exemple, la déclaration :

class (Eq a, Show a) => C a where ...

crée une classe C qui hérite aussi bien des opérations de Eq que de celles de Show.

Les méthodes de classe sont traitées comme des déclarations de niveau supérieur dans Haskell. Elles partagent le même espace de nom que les variables ordinaires. Un même nom ne peut pas être utilisé pour dénoter à la fois une méthode de classe et une variable ou des méthodes dans différentes classes.

Les contextes sont également autorisés dans les déclarations de données (voir §4.2.1).

Les méthodes de classe peuvent contenir des contraintes supplémentaires sur n'importe quel type de variable à l'exception de ceux définissant la classe courante. Par exemple, dans cette classe :

class C a where
  m                     :: Show b => a -> b

la méthode m impose que le type b soit une instance de la classe Show. Cependant, la méthode m ne peut contenir aucune autre contrainte de classe sur le type a. Celles-ci devraient plutôt faire partie du contexte dans la déclaration de classe.

À ce stade, nous avons utilisé les types de « premier ordre ». Par exemple, le constructeur de type Arborescence a toujours été mis en parité avec un argument, comme dans Arborescence Integer (une arborescence contenant des valeurs entières Integer) ou Arborescence a (représentant la famille d'arborescences contenant des valeurs de type a). Mais Arborescence est elle même un constructeur de type, et en tant que tel, accepte un type en tant qu'argument et retourne un type en tant que résultat. Il n'existe pas de valeurs, dans Haskell, qui sont de ce type, mais de tels types d'« ordre supérieur » peuvent être utilisés dans les déclarations de classe.

Pour commencer, considérons la classe Functor suivante (extraite du Prélude) :

class Functor f where
  fmap                  :: (a -> b) -> f a -> f b

La fonction fmap généralise la fonction map utilisée précédemment. Notez que la variable de type f est appliquée à d'autres types dans f a et f b. Nous pourrions donc nous attendre à ce que celle-ci puisse être liée à un type tel que Arborescence qui peut être appliqué à un argument. Une instance de Functor pour le type Arborescence serait :

instance Functor Arborescence where
  fmap f (Feuille x)       = Feuille   (f x)
  fmap f (Branche t1 t2) = Branche (fmap f t1) (fmap f t2)

Cette déclaration d'instance déclare que Arborescence, plutôt que Arborescence a, est une instance de Functor. Cette capacité est très utile, et démontre ici la possibilité de décrire des types « conteneurs » génériques, permettant à des fonctions telles que fmap de fonctionner uniformément sur des arborescences arbitraires, des listes, et d'autres types de données.

[Les applications de types sont écrites de la même manière que les applications de fonctions. Le type T a b est traduit comme (T a) b. Les types tels que les tuples qui utilisent une syntaxe spéciale peuvent être écrits dans un style alternatif qui autorise la curryfication. Pour les fonctions, (->) est un constructeur de type. Les types f -> g et (->) f g sont équivalents. De même, les types [a] et [] a sont équivalents. Pour les tuples, les constructeurs de type (ainsi que pour les constructeurs de données) sont (,), ( €ž), et ainsi de suite.]

Comme nous le savons, le système de typage détecte les erreurs de type dans les expressions. Mais qu'en est-il des erreurs dues à des expressions de type mal formées? L'expression (+) 1 2 3 provoque une erreur de type puisque (+) n'accepte que deux arguments. De même, le type Arborescence Int Int devrait produire une erreur puisque le type Arborescence n'accepte qu'un seul argument. Alors, comment Haskell détecte-t-il les expressions de type mal formées? La réponse est un deuxième système de typage qui garantit que les types soient corrects! Chaque type a une « espèce » qui lui est associée ce qui garantit que les types sont utilisés correctement.

Les expressions de type sont classées selon différentes espèces qui prennent une des deux formes possibles :

• Le symbole * représente l'espèce de type associée aux objets de données concrètes. C'est-à-dire, si la valeur « v » est de type « t », l'espèce de « v » doit être *.
• Si k1 et k2 sont des espèces, alors k1 -> k2 est l'espèce de types qui prennent un type d'espèce k1 et retournent un type d'espèce k2.

Le constructeur de type Arborescence est d'espèce * -> *. Le type d'Arborescence Int est d'espèce *. Les membres de la classe Functor doivent tous être de la même espèce * -> *. Une erreur d'espèce résulterait d'une déclaration telle que :

instance Functor Integer where ...

puisque l'espèce de Integer est *.

Les espèces n'apparaissent pas directement dans les programmes Haskell. Le compilateur infère les espèces avant de passer à la vérification des types sans avoir besoin d'une quelconque « déclaration d'espèce ». Les espèces restent dans les tréfonds des programmes Haskell sauf lorsqu'une signature de type erronée conduit à une erreur d'espèce. Les espèces sont assez simples pour que les compilateurs soient capables de fournir des messages d'erreurs descriptifs quand des conflits d'espèce surviennent. Voir §4.1.1 et §4.6 pour plus d'informations sur les espèces.

Une perspective différente

Avant d'aller plus loin avec d'autres exemples de l'utilisation des classes de types, il peut être bon de se choisir deux autres points de vue sur les classes de types. Le premier est par analogie avec la programmation orientée objet (POO). Dans l'énonciation suivante à propos de la POO, une simple substitution des classes de types par des classes, et des types par des objets, donne un bon résumé du mécanisme des classes de types de Haskell :

« Les classes renferment des jeux communs d'opérations. Un objet particulier peut être l'instance d'une classe, et aura une méthode correspondant à chaque opération. Les classes peuvent être arrangées hiérarchiquement, formant les notions de superclasses et sous-classes, et permettant l'héritage d'opérations/méthodes. Une méthode par défaut peut aussi être associée à une opération ».

Contrairement à la POO, il devrait être clair que les types ne sont pas des objets, et en particulier il n'y a pas de notion d'état interne mutable des objets ou des types. Un avantage de Haskell par rapport à quelques langages POO est d'imposer que les méthodes opèrent sur des types cohérents : Une tentative d'appliquer une méthode à une valeur dont le type n'appartient pas à la classe requise sera détectée à la compilation plutôt qu'à l'exécution. En d'autres termes, les méthodes ne sont pas « examinées » à l'exécution, mais sont simplement passées en tant que fonctions d'ordre supérieur.

On aura encore une autre perspective en considérant la relation entre le polymorphisme paramétrique et ad hoc. Nous avons montré comment le polymorphisme paramétrique pouvait être utile dans la définition de familles de types en quantifiant universellement pour tous les types. Quelquefois, cependant, cette quantification universelle peut s'avérer trop large –nous souhaitons quantifier sur des ensembles plus restreints de types, tels que les types dont les éléments peuvent être comparés pour tester leur égalité. On peut se représenter les classes de types précisément comme une manière d'obtenir ceci. En fait, nous pouvons aussi nous représenter le polymorphisme paramétrique comme un genre de surcharge! C'est juste que la surcharge intervient implicitement sur tous les types plutôt que sur un ensemble restreint de types (c.-à.d. les classes de types).

Comparaisons avec d'autres langages

Les classes utilisées par Haskell sont similaires à celles utilisées dans d'autres langages orientés objet, tel que C++ et Java. Cependant, il y a d'importantes différences :

• Dans Haskell, la définition d'un type est séparée de la définition des méthodes associées à ce type. Normalement, une classe dans C++ ou Java, définit à la fois une structure de données (les variables membres) et les fonctions associées à cette structure (les méthodes). Dans Haskell, ces définitions sont séparées.
• Les méthodes de classe définies par une classe Haskell correspondent à une fonction virtuelle dans une classe C++. Chaque instance d'une classe fournit sa propre définition pour chaque méthode. Le comportement par défaut d'une classe correspond aux définitions par défaut pour une fonction virtuelle dans la classe de base.
• Les classes Haskell sont grossièrement similaires à des interfaces Java. De même qu'une déclaration d'interface, une déclaration de classe Haskell définit un protocole pour l'utilisation d'un objet plutôt que la définition de l'objet lui-même.
• Haskell ne permet pas le style de surcharge C++ qui fonctionne sur différents types et partageant le même nom.
• Le type d'un objet Haskell ne peut pas être implicitement forcé. Il n'existe pas de classe de base universelle telle que Object dont les valeurs peuvent être projetées dans ou « hors de ».
• C++ et Java attachent des informations d'identification (telle que VTable) à la représentation de l'objet à l'exécution. Dans Haskell, de telles informations sont attachées à des valeurs logiquement plutôt que physiquement, à travers le système de typage.
• Il n'y a pas de contrôle des accès (tels que les constituants de classe privée ou publique) intégrés au système de classes de Haskell. En lieu et place, le système de modules doit être utilisé pour cacher ou révéler les composants d'une classe.