Classes Haskell standard
Dans cette section, nous présentons les classes de types standards prédéfinies dans Haskell. Nous avons quelque peu simplifié ces classes en omettant certaines des méthodes les moins intéressantes de ces classes; le rapport Haskell contient une description plus complète. De plus, certaines des classes standards font partie des bibliothèques Haskell standard ; elles sont décrites dans le rapport de la bibliothèque Haskell.
Egalité et classes ordonnées
Les classes Eq et Ord ont déjà été abordées. La définition de Ord dans le prélude est un peu plus complexe que la version simplifiée de Ord présentée précédemment. Notez en particulier 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 valeurs par défaut) dans cette classe et constitue le meilleur moyen de créer des instances Ord.
La classe Enumeration
La classe Enum possède un ensemble d'opérations qui sous-tendent le sucre syntaxique des séquences arithmétiques ; par exemple, l'expression de séquence arithmétique [1,3..] signifie enumFromThen 1 3 (voir §3.10 pour la traduction formelle). Nous pouvons maintenant voir que les expressions de séquence arithmétique peuvent être utilisées pour générer des listes de tout type qui est une instance de Enum. Cela inclut non seulement la plupart des types numériques, mais aussi Char, de sorte que, par exemple, ['a'..'z'] désigne la liste des lettres minuscules dans l'ordre alphabétique. De plus, les types énumérés définis par l'utilisateur comme Color peuvent facilement recevoir des déclarations d'instance Enum. Si c'est le cas :
- [Red .. Violet] => [Red, Green, Blue, Indigo, Violet]
Notez qu'une telle séquence est arithmétique dans le sens où l'incrément entre les valeurs est constant, même si les valeurs ne sont pas des nombres. La plupart des types dans Enum peuvent être cartographiés sur des entiers à précision fixe ; pour ceux-ci, fromEnum et toEnum convertissent entre Int et un type dans Enum.
Les classes Read et Show
Les instances de la classe Show sont les types pouvant être convertis en chaînes de caractères (généralement pour les entrées/sorties). La classe Read fournit des opérations pour analyser les chaînes de caractères afin d'obtenir les valeurs qu'elles peuvent représenter. La fonction la plus simple de la classe Show est show :
- show :: (Show a) => a -> String
Naturellement, show prend n'importe quelle valeur d'un type approprié et renvoie sa représentation sous forme de chaîne de caractères (liste de caractères), comme dans show (2+2), ce qui donne "4". C'est très bien dans ce cas, mais nous devons généralement produire des chaînes de caractères plus complexes pouvant contenir les représentations de nombreuses valeurs, comme dans :
- "La somme de " ++ show x ++ " et " ++ show y ++ " est " ++ show (x+y) ++ "."
et après un certain temps, toute cette concaténation devient un peu inefficace. Plus précisément, considérons une fonction pour représenter les arbres binaires sous forme de chaîne de caractères, avec des marquages ??appropriés pour montrer l'imbrication des sous-arbres et la séparation des branches gauche et droite (à condition que le type d'é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 dans la longueur de son paramètre de gauche, showTree est potentiellement quadratique dans la taille de l'arbre.
Pour restaurer la complexité linéaire, la fonction shows est fournie :
- shows :: (Show a) => a -> String -> String
shows prend 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 deuxième paramètre sert en quelque sorte d'accumulateur de chaîne de caractères, et show peut maintenant être défini comme shows avec l'accumulateur null. Il s'agit de la définition par défaut de show dans la définition de classe Show :
- show x = shows x ""
Nous pouvons utiliser shows pour définir une version plus efficace de showTree, possédant également un paramètre accumulateur de chaîne de caractères :
- 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é (showsTree a une complexité linéaire), mais la présentation de cette fonction (et d'autres similaires) peut être améliorée. Commençons par créer un synonyme de type :
- type ShowS = String -> String
Il s'agit du type de fonction renvoyant une représentation sous forme de chaîne de caractères de quelque chose suivie d'une chaîne de caractères d'accumulateurs. Deuxièmement, nous pouvons éviter de transporter des accumulateurs et également d'accumuler des parenthèses à la fin droite de longues constructions en utilisant la composition fonctionnelle :
- showsTree :: (Show a) => Tree a -> ShowS
- showsTree (Leaf x) = shows x
- showsTree (Branch l r) = ('<':) . showsTree l . ('|':) . showsTree r . ('>':)
Cette transformation a permis de réaliser quelque chose de plus important que de simplement mettre de l'ordre dans le code : nous avons élevé la présentation d'un niveau objet (dans ce cas, des chaînes) à un niveau fonction. Nous pouvons considérer le typage comme disant que showsTree cartographie un arbre dans une fonction d'affichage. Des fonctions comme ('<' :) ou ("a string" ++) sont des fonctions d'affichage primitives, et nous construisons des fonctions plus complexes par composition de fonctions.
Maintenant que nous pouvons transformer des arbres en chaînes de caractères, passons au problème inverse. L'idée de base est un analyseur pour un type a, étant une fonction prenant une chaîne de caractères et renvoie une liste de paires (a, String) [9]. Le Prélude fournit un synonyme de type pour de telles fonctions :
- type ReadS a = String -> [(a,String)]
Normalement, un analyseur renvoie une liste singleton, contenant une valeur de type a ayant été lue à partir de la chaîne de caractères d'entrée et la chaîne de caractères restante suivant ce qui a été analysé. Cependant, si aucune analyse n'est possible, le résultat est la liste vide, et s'il existe plusieurs analyses possibles (une ambiguïté), la liste résultante contient plusieurs paires. La fonction standard reads est un analyseur pour toute instance de Read :
- reads :: (Read a) => ReadS a
Nous pouvons utiliser cette fonction pour définir une fonction d'analyse pour la représentation sous forme de chaîne de caractères d'arbres binaires produite par showsTree. Les compréhensions de liste nous donnent un idiome pratique pour construire de tels analyseurs : (Une approche encore plus élégante de l'analyse utilise des monades et des combinateurs d'analyseurs. Ceux-ci font partie d'une bibliothèque d'analyse standard distribuée avec la plupart 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 à analyser est '<', nous devrions avoir la représentation d'une branche ; sinon, nous avons une feuille. Dans le premier cas, en appelant le reste de la chaîne de caractères d'entrée suivant le crochet angulaire ouvrant s, toute analyse possible doit être un arbre Branch l r avec la chaîne de caractères restante u, sous réserve des conditions suivantes :
- L'arbre l peut être analysé à partir du début de la chaîne de caractères s.
- La chaîne de caractères restante (suivant la représentation de l) commence par '|'. Appelons la queue de cette chaîne de caractères t.
- L'arbre r peut être analysé à partir du début de t.
- La chaîne de caractères restante de cette analyse commence par '>', et u est la queue.
Remarquez la puissance expressive que nous obtenons de la combinaison de la correspondance de motifs avec la compréhension de liste : la forme d'une analyse résultante est donnée par l'expression principale de la compréhension de liste, les deux premières conditions ci-dessus sont exprimées par le premier générateur ("(l, '|':t) est tiré de la liste des analyses de s"), et les conditions restantes sont exprimées par le deuxième générateur.
La deuxième équation de définition ci-dessus dit simplement que pour analyser la représentation d'une feuille, nous analysons une représentation du type d'élément de l'arbre et appliquons le constructeur Leaf à la valeur ainsi obtenue.
Nous accepterons de bonne foi pour le moment qu'il existe une instance Read (et Show) de Integer (parmi de nombreux autres types), fournissant une lecture se comportant comme on pourrait s'y attendre, par exemple :
- (reads "5 anneaux d'or") :: [(Integer,String)] => [(5, " anneaux d'or")]
Avec cette compréhension, le lecteur devrait vérifier les évaluations suivantes :
- readsTree "<1|<2|3>>" => [(Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), "")]
- readsTree "<1|2" => []
Notre définition de readsTree présente quelques défauts. L'un d'eux est que l'analyseur est assez rigide, ne laissant aucun espace avant ou entre les éléments de la représentation arborescente ; l'autre est que la façon dont nous analysons nos symboles de ponctuation est assez différente de la façon dont nous analysons les valeurs des feuilles et les sous-arbres, ce manque d'uniformité rendant la définition de la fonction plus difficile à lire. Nous pouvons résoudre ces deux problèmes en utilisant l'analyseur lexical fourni par Prelude :
- lex :: ReadS String
lex renvoie normalement une liste singleton contenant une paire de chaînes de caractères : le premier lexème de la chaîne de caractères d'entrée et le reste de l'entrée. Les règles lexicales sont celles des programmes Haskell, y compris les commentaires, que lex ignore, ainsi que les espaces. Si la chaîne de caractères d'entrée est vide ou ne contient que des espaces et des commentaires, lex renvoie [("","")] ; si l'entrée n'est pas vide dans ce sens, mais ne commence pas non plus par un lexème valide après un espace et des commentaires de début, lex renvoie [].
En utilisant l'analyseur lexical, notre analyseur d'arbre ressemble maintenant à ceci :
- 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 ]
Nous pouvons maintenant 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 les fonctions génériques surchargées du Prelude pour analyser et afficher des arbres. De plus, nous serions alors automatiquement en mesure d'analyser et d'afficher de nombreux autres types contenant des arbres en tant que composants, par exemple, [Tree Integer]. Il s'avère que readsTree et showsTree sont presque des types appropriés pour être des méthodes Show et Read. Les méthodes showsPrec et readsPrec sont des versions paramétrées de shows et reads. Le paramètre supplémentaire est un niveau de priorité, utilisé pour mettre correctement entre parenthèses les expressions contenant des constructeurs infixes. Pour des types tels que Tree, la priorité peut être ignorée. Les instances Show et Read pour Tree sont :
- instance Show a => Show (Tree a) where
- showsPrec _ x = showsTree x
-
- instance Read a => Read (Tree a) where
- readsPrec _ s = readsTree s
Alternativement, l'instance Show pourrait être définie en termes de showTree :
- instance Show a => Show (Tree a) where
- show t = showTree t
Ceci sera cependant moins efficace que la version ShowS. Notez que la classe Show définit des méthodes par défaut pour showsPrec et show, permettant à l'utilisateur de définir l'une ou l'autre de ces fonctions dans une déclaration d'instance. Étant donné que ces valeurs par défaut sont mutuellement récursives, une déclaration d'instance qui ne définit aucune de ces fonctions bouclera lorsqu'elle sera appelée. D'autres classes telles que Num ont également ces «valeurs par défaut imbriquées».
Nous pouvons tester les instances Read et Show en appliquant (read . show) (devant être l'identité) à certains arbres, où read est une spécialisation de reads :
- read :: (Read a) => String -> a
Cette fonction échoue s'il n'y a pas d'analyse unique ou si l'entrée contient autre chose qu'une représentation d'une valeur de type a (et éventuellement des commentaires et des espaces).
Instances dérivées
Rappelons l'instance Eq pour les arbres; une telle déclaration est simple et ennuyeuse à produire : nous exigeons que le type d'élément dans les feuilles soit un type d'égalité ; alors, deux feuilles sont égales iff elles contiennent des éléments égaux, et deux branches sont égales iff leurs sous-arbres gauche et droit sont respectivement égaux. Les deux autres arbres sont inégaux :
- 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, nous n'avons pas besoin de passer par cette procédure fastidieuse à chaque fois que nous avons besoin d'opérateurs d'égalité pour un nouveau type; l'instance Eq peut être dérivée automatiquement de la déclaration de données si nous le spécifions :
- data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Eq
La clause de dérivation produit implicitement une déclaration d'instance Eq. Les instances de Ord, Enum, Ix, Read et Show peuvent également être générées par la clause de dérivation. [Plus d'un nom de classe peut être spécifié, auquel cas la liste des noms doit être mise entre parenthèses et les noms séparés par des virgules.]
L'instance Ord dérivée pour Tree est légèrement plus compliquée que l'instance 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 classés selon l'ordre de leur apparition dans la déclaration de données, et les paramètres d'un constructeur sont comparés de gauche à droite. Rappelons que le type de liste intégré est sémantiquement équivalent à un type à deux constructeurs ordinaire. En fait, il s'agit de la déclaration complète :
- data [a] = [] | a : [a] deriving (Eq, Ord) -- pseudo-code
(Les listes ont également des instances Show et Read, n'étant pas dérivées.) Les instances dérivées Eq et Ord pour les listes sont les instances habituelles; en particulier, les chaînes de caractères, en tant que listes de caractères, sont ordonnées comme déterminé par le type Char sous-jacent, avec une sous-chaîne de caractères initiale comparable à moins qu'une chaîne plus longue ; par exemple, "chat" < "catalogue".
En pratique, les instances Eq et Ord sont presque toujours dérivées, plutôt que définies par l'utilisateur. En fait, nous devrions fournir nos propres définitions des prédicats d'égalité et d'ordre seulement avec une certaine appréhension, en prenant soin de maintenir les propriétés algébriques attendues des relations d'équivalence et des ordres totaux. Un prédicat intransitif (==), par exemple, pourrait être désastreux, déroutant les lecteurs du programme et confondant les transformations manuelles ou automatiques du programme reposant sur le fait que le prédicat (==) est une approximation de l'égalité définitionnelle. Néanmoins, il est parfois nécessaire de fournir des instances Eq ou Ord différentes de celles qui seraient dérivées ; L'exemple le plus important est probablement celui d'un type de données abstrait dans lequel différentes valeurs concrètes peuvent représenter la même valeur abstraite.
Un type énuméré peut avoir une instance Enum dérivée, et là encore, l'ordre est celui des constructeurs dans la déclaration de données. Par exemple :
- data Day = Sunday | Monday | Tuesday | Wednesday
- | Thursday | Friday | Saturday deriving (Enum)
Voici quelques exemples simples utilisant 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 (Show) sont possibles pour tous les types dont les types de composantes ont également des instances de Read (Show). (Les instances de Read et de Show pour la plupart des types standard sont fournies par le Prelude. Certains types, comme le type de fonction (->), ont une instance de Show mais pas de Read correspondante.) La représentation textuelle définie par une instance dérivée de Show est cohérente avec l'apparence des expressions Haskell constantes du type en question. Par exemple, si nous ajoutons Show et Read à la clause de dérivation pour le type Day, ci-dessus, nous obtenons :
- show [Monday .. Wednesday] => "[Monday,Tuesday,Wednesday]"