A Gentle Introduction to Haskell, version 98

Les classes Eq et Ord ont déjà été rencontrées dans cet article. La définition de Ord dans le Prélude est plus complexe que la version simplifiée que nous avions présentée précédemment. En particulier, observez la méthode compare :

data Ordering           =  EQ | LT | GT 
compare                 :: Ord a => a -> a -> Ordering

La méthode compare est suffisante pour définir toutes les autres méthodes (via les définitions par défaut) de cette classe, et dans le meilleur des cas de créer des instances de Ord.

La classe Enum possède un ensemble d'opérations qui gèrent le sucre syntaxique des suites arithmétiques. Par exemple, l'expression de suite arithmétique [1,3..] signifie enumFromThen 1 3 (cf 3.10) pour la traduction formelle). On peut maintenant voir que les expressions de suites arithmétiques peuvent être utilisées pour générer des listes de n'importe quel type qui puissent être une instance de Enum. Cela n'inclut pas seulement la majorité des types numériques, mais aussi Char. Par exemple, ['a'..'z'] définit la liste des lettres minuscules dans l'ordre alphabétique. Par ailleurs, les types énumérés définis par l'utilisateur, comme Color, peuvent facilement être générés par une déclaration d'instance de Enum. Ainsi :

[Red .. Violet] => [Red, Green, Blue, Indigo, Violet]

Remarquez qu'une telle suite est arithmétique dans le sens que l'incrément entre chaque valeur est constant, même si les valeurs ne sont pas des nombres. La majorité des types de Enum peuvent être associés à des entiers avec une précision fixée. Ainsi, on trouve les méthodes fromEnum et toEnum qui traduisent des données du type Int au type Enum, ou inversement.

Les instances de la classe Show sont celles qui peuvent être converties en chaîne de caractères (typiquement pour des entrées/sorties). La classe Read fournit des opérations pour parser les chaînes de caractères pour obtenir les valeurs qu'elles représentent. La fonction la plus simple de la class Show est show :

show                    :: (Show a) => a -> String

Bien sûr, show prend n'importe quelle valeur d'un type adéquate et renvoie sa représentation sous forme de chaîne de caractères, comme dans show (2+2) qui renverra 4. Tant que cela fonctionne, cela suffit, mais on aura besoin de produire des chaînes de caractères plus complexes qui peuvent représenter de nombreuses valeurs, telles :

"The sum of " ++ show x ++ " and " ++ show y ++ " is " ++ show (x+y) ++ "."

Au bout d'un moment, les concaténations deviendront quelque peu inefficaces. En particulier, on peut considérer une fonction qui représente des arbres binaires sous forme de chaînes de caractères (cf 2.2.1), avec des marques adéquates pour montrer les sous-arbres, et la séparation des branches droite et gauche (pourvu que le type de l'élément soit représentable sous forme de chaîne de caractères.

showTree                :: (Show a) => Tree a -> String
showTree (Leaf x)       =  show x
showTree (Branch l r)   =  "<" ++ showTree l ++ "|" ++ showTree r ++ ">"

Étant donné que (++) a une complexité temporelle linéaire en la longueur de son argument de gauche, showTree est potentiellement quadratique en la taille de l'arbre.

Pour restaurer la complexité linéaire, la fonction show est fournie :

shows                   :: (Show a) => a -> String -> String

shows prend en arguments une valeur affichable et une chaîne de caractères, et renvoie cette chaîne de caractères avec la représentation de la valeur concaténée au début. Le second argument sert comme une sorte d'accumulateur, et show peut maintenant être définie comme shows avec un accumulateur vide. C'est d'ailleurs la définition par défaut de show dans la classe Show :

show x                  =  shows x ""

On peut utiliser shows pour définir une version plus efficace de showTree, qui utilise aussi un argument comme accumulateur :

showsTree               :: (Show a) => Tree a -> String -> String
showsTree (Leaf x) s    =  shows x s
showsTree (Branch l r) s=  '<' : showsTree l ('|' : showsTree r ('>' : s))

Cela résout notre problème d'efficacité (showTree est désormais linéaire), mais la présentation de cette fonction (et d'autres du même style) peut être améliorée. Tout d'abord, créons un type synonyme :

type ShowS              =  String -> String

Il s'agit du type de la fonction qui retourne une chaîne de caractères représentant quelque chose, suivi d'une chaîne de caractères d'accumulation. Ensuite, on peut éviter de traîner ces accumulateurs, et ainsi éviter d'empiler les parenthèses à la droite des constructions un peu longues, en utilisant la composition fonctionnelle :

showsTree               :: (Show a) => Tree a -> ShowS
showsTree (Leaf x)      =  shows x
showsTree (Branch l r)  =  ('<':) . showsTree l . ('|':) . showsTree r . ('>':)

Lors de cette transformation est apparue quelque chose de plus important qu'une simple vérification du code : on est passé d'une représentation d'un niveau objet (ici des chaînes de caractères), et un niveau fonctionnel. On peut penser au typage comme si showTree mettait en relation un arbre et une fonction représentative. Des fonctions comme ('<' :) ou (« a string » ++) sont des fonctions de représentation primitives, et on peut à partir d'elle construire des fonctions plus complexes par composition.

Maintenant que l'on a transformé les arbres en chaînes de caractères, considérons le problème inverse. L'idée de base est le parsage pour un type a, ce qui demande une fonction prenant en argument une chaîne de caractères, et renvoyant une liste de paires (a, String). Le Prélude fournit un type synonyme pour de telles fonctions :

type ReadS a            =  String -> [(a,String)]

Normalement, le parseur renvoie une liste à un élément, qui contient la valeur de type a qui a été lue depuis la chaîne de caractères en entrée, et la chaîne de caractères restante une fois que cet élément est parsé. Cependant, si aucune lecture n'est possible, la liste retournée sera vide, ou s'il y a ambiguïté (plusieurs interprétations possibles), la liste renvoyée contiendra plus d'une paire. La fonction standard reads est un parseur pour n'importe quelle instance de la classe Read :

reads                   :: (Read a) => ReadS a

On peut utiliser cette fonction pour définir une fonction de parsage d'une chaîne de caractères représentant des arbres binaires, produite par showTree. Les listes en compréhension nous donnent une syntaxe pratique pour construire de tels parseurs.
(Une approche plus élégante consisterait à parser au moyen de monades et de combinateurs de parseurs. C'est d'ailleurs la méthode utilisée dans les bibliothèques standards de parsage fournies dans la majorité des systèmes Haskell.)

readsTree               :: (Read a) => ReadS (Tree a)
readsTree ('<':s)       =  [(Branch l r, u) | (l, '|':t) <- readsTree s,
                                              (r, '>':u) <- readsTree t ]
readsTree s             =  [(Leaf x, t)     | (x,t)      <- reads s]

Prenons un moment pour examiner cette définition de fonction en détail. Il y a deux cas principaux à considérer. Si le premier caractère de la chaîne de caractères à parser est '<', on devrait avoir une représentation d'une branche ; sinon on devrait avoir la représentation d'une feuille.
Dans le premier cas, il faut faire un appel récursif sur la chaîne de caractères restante après le <, le seul parsage possible devrait alors être un arbre Branch l r avec une chaîne de caractères résiduelle u, et respectant les conditions suivantes :

• L'arbre l peut être parsé à partir du début de la chaîne de caractères s ;
• La chaîne de caractères restante (qui suit la représentation de l) commence par '|'. Nous appellerons la queue de cette chaîne de caractères t ;
• L'arbre r peut être parsé depuis le début de t ;
• La chaîne de caractères restante après le parsage commence par '>', et u est sa queue.

Remarquez le pouvoir d'expression que l'on obtient en combinant de la reconnaissance de motifs et des listes par compréhension. La forme du résultat du parsage est donnée par l'expression principale de la liste par compréhension, les deux premières conditions sont exprimées par le premier générateur ("(l, '|':t) qui renvoie la liste des parsages de s, et les conditions restantes sont exprimées par le second générateur.

La seconde équation définie dit juste que pour parser la représentation d'une feuille, on parse la représentation du type de l'élément de l'arbre, et qu'on applique le constructeur Leaf à la valeur obtenue.

Pour l'instant, on considérera comme acquis le fait qu'il existe une instance de Read (et de Show) pour les types Integer (parmi les types couramment utilisés), qui fournit reads et ce comporte comme on l'attend, c'est-à-dire :

(reads "5 golden rings") :: [(Integer,String)] => [(5, " golden rings")]

Avec cela, le parseur devrait vérifier les évaluations suivantes :

readsTree "<1|<2|3>>"    =>    [(Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), "")]
readsTree "<1|2"        =>    []

Il y a deux problèmes dans notre définition de readsTree. D'une part, le parseur est un peu trop rigide. Il n'autorise pas les espaces avant ou entre les éléments de la représentation de l'arbre. D'autre part, la façon dont on parse les symboles de ponctuation est différente de celle dont on parse les valeurs des feuilles et les sous-arbres. Ce manque d'homogénéité ne facilite pas la lecture de la définition de la fonction. On peut résoudre ces deux problèmes en utilisant l'analyseur lexical fourni par le Prélude :

lex                     :: ReadS String

lex renvoie normalement une liste à un élément contenant une paire de chaînes de caractères : le premier lexème de la chaîne de caractères passée en argument, et le reste. Les règles lexicales sont celles des programmes Haskell, incluant les commentaires, que lex va ignorer, et autorisant les espaces. Si la chaîne de caractères en entrée est vide ou ne contient que des espaces et des commentaires, lex renverra [(« ", »")]. Si elle n'est pas vide dans ce sens, mais qu'elle ne commence pas par un lexème valide après un nombre quelconque d'espaces et de commentaires, lex renverra [].

En utilisant l'analyseur lexical, notre parseur d'arbre ressemble désormais à cela :

readsTree               :: (Read a) => ReadS (Tree a)
readsTree s             =  [(Branch l r, x) | ("<", t) <- lex s,
                                              (l,   u) <- readsTree t,
                                              ("|", v) <- lex u,
                                              (r,   w) <- readsTree v,
                                              (">", x) <- lex w         ]
                           ++
                           [(Leaf x, t)     | (x,   t) <- reads s       ]

On peut désormais souhaiter utiliser readsTree et showsTree pour déclarer (Read a) => Tree a une instance de Read et (Show a) => Tree a une instance de Show. Cela nous permettrait d'utiliser des surcharges des fonctions génériques du Prélude pour parser et afficher les arbres. Par ailleurs, on pourrait automatiquement parser et afficher de nombreux autres types contenant des arbres, par exemple [Tree Integer]. À cet instant, readsTree et showsTree semblent être des candidats sérieux pour être les méthodes de Read et Show. Les méthodes showsPrec et readsPrec sont des versions paramétriques de shows et reads. Un paramètre supplémentaire est le niveau de priorité, qui peut servir pour mettre correctement les expressions contenant des constructeurs infixes entre parenthèses. Pour des types comme Tree, la notion de priorité peut être ignorée. Ainsi, les instances de Show et Read sont :

instance Show a => Show (Tree a) where
    showsPrec _ x = showsTree x
 
instance Read a => Read (Tree a) where
    readsPrec _ s = readsTree s

D'un autre point de vue, on peut aussi définir cette instance de Show à partir de showTree :

instance Show a => Show (Tree a) where
   show t = showTree t

Cependant, cela serait moins performant que la version ShowS. Remarquez que la classe Show définit les méthodes par défaut pour showsPrec et show, ce qui permet à l'utilisateur de redéfinir l'une d'elles dans la déclaration d'instance. Comme celles par défaut sont mutuellement récursives, une déclaration d'instance qui ne définit aucune d'entre elles bouclera infiniment lors d'un appel. D'autres classes comme Num ont également ce problème d'interblocage par défaut.

On renverra les lecteurs intéressés au §D pour plus de détails sur Read et Show.

On peut tester les instances de Read et Show en appliquant (read . show) (qui représente la fonction identité) à quelques arbres, où read est une méthode spécialisée dérivée de reads :

read                    :: (Read a) => String -> a

Cette fonction échoue s'il n'existe pas d'unique parseur ou si l'entrée contient n'importe quoi en plus qu'une représentation d'une valeur du type a (et d'éventuels espaces et commentaires).

Rappelez-vous de l'instance de Eq pour les arbres que l'on a présentés dans la section 5 comme une déclaration simple (et ennuyante) à produire. On avait besoin que le type d'élément pour les feuilles soit un type « égalable ». Ainsi, deux feuilles sont égales si elles contiennent des éléments égaux, et deux branches sont égales si leurs arbres gauche et droit sont respectivement égaux. Tous les couples d'arbres étant différents.

instance  (Eq a) => Eq (Tree a)  where
    (Leaf x)     == (Leaf y)        =  x == y
    (Branch l r) == (Branch l' r')  =  l == l' && r == r'
    _            == _               =  False

Heureusement, on n'a pas besoin d'aller le détail à chaque fois que l'on veut des opérateurs d'égalité pour un nouveau type. L'instance de Eq peut les dériver automatiquement à partir de la déclaration de données que l'on a spécifiée :

data  Tree a            =  Leaf a | Branch (Tree a) (Tree a)  deriving Eq

La clause de dérivation produit implicitement une déclaration d'instance de Eq comme dans la section 5. Les instances de Ord, Enum, Read et Show peuvent aussi être générées par la clause de dérivation.
Plus d'un nom de classe peut être spécifié. Dans ce cas, la liste des noms doit être parenthèsée et les noms séparés par des virgules.

Une instance dérivée de Ord pour Tree est légèrement plus compliquée que l'instance de Eq :

instance  (Ord a) => Ord (Tree a)  where
    (Leaf _)     <= (Branch _)      =  True
    (Leaf x)     <= (Leaf y)        =  x <= y
    (Branch _)   <= (Leaf _)        =  False
    (Branch l r) <= (Branch l' r')  =  l == l' && r <= r' || l <= l'

Cela spécifie un ordre lexicographique. Les constructeurs sont ordonnés dans l'ordre de leur apparition dans la déclaration de données, et les arguments d'un constructeur sont comparés de la gauche vers la droite. Rappelez-vous que le type liste « natif » est sémantiquement équivalent à un type à deux constructeurs. En fait, voici sa déclaration complète :

data [a]        = [] | a : [a] deriving (Eq, Ord)     – pseudocode

(Les listes ont ainsi des instances de Show et Read, qui ne sont pas dérivées.) Les instances dérivées de Eq et Ord pour les listes sont celles par défaut. En particulier, les chaînes de caractères, considérées comme des listes de caractères, sont ordonnées comme il est prévu par le type sous-jacent Char, avec une sous-chaîne initiale comparant moins qu'une chaîne de caractères plus longue, par exemple « cat » < « catalog ».

Dans la pratique, les instances de Eq et Ord sont toujours dérivées, et non redéfinies par l'utilisateur. En fait, on devrait fournir nos propres définitions des relations d'égalité et d'ordre de prédicats seulement avec quelques changements, en étant attentif au fait de maintenir les propriétés algébriques attendues de relation d'équivalence, et d'ordre total. Par exemple, un prédicat non transitif (==) peut être désastreux, et troubler les personnes qui relisent le programme et qui confondraient les transformations manuelles et automatiques se basant sur le fait que le prédicat (==) est une approximation de l'égalité. Néanmoins, il est parfois nécessaire de fournir des instances de Eq et Ord différentes de celles qui auraient été dérivées. L'exemple le plus important est probablement le cas où un type de données abstrait pouvant se concrétiser en différents types ; ainsi plusieurs valeurs réelles distinctes peuvent avoir le même représentant abstrait.

Un type énuméré peut avoir une instance dérivée de Enum, et ici encore, un ordre défini par les constructeurs dans la déclaration de données. Par exemple :

data Day = Sunday | Monday | Tuesday | Wednesday
         | Thursday | Friday | Saturday         deriving (Enum)

Ici quelques exemples simples utilisent les instances dérivées pour ce type :

[Wednesday .. Friday]     =>     [Wednesday, Thursday, Friday]
[Monday, Wednesday ..]     =>    [Monday, Wednesday, Friday]

Les instances dérivées de Read (ou Show) sont possibles pour tous les types dont les types composant ont des instances de Read (ou Show). (Les instances de Read et Show pour les types standards sont pour la plupart d'entre eux définis dans le Prélude. Quelques types, tel le type fonction (->), ont une instance de Show, mais pas d'instance de Read correspondante.) La représentation textuelle définie par une instance dérivée de Show est cohérente avec la représentation des expressions Haskell constantes du type en question. Par exemple, si on ajoute Show et Read à la clause de dérivation pour le type Day, on obtiendrait :

show [Monday .. Wednesday] => "[Monday,Tuesday,Wednesday]"