Il existe trois manières de déclarer un type en Haskell, qui ont toutes une utilité différente.
type : un autre nom pour un type
Avec
type, vous pouvez déclarer un nouveau nom pour un type qui existe déjà. Par exemple, vous avez déjà vu que le type
String est en fait un autre nom pour le type
[Char]. En réalité, le type String est défini de la façon suivante :
Code : Haskell
Ce genre de définition ne crée pas à proprement parler un nouveau type : les deux types String et [Char] sont interchangeables, String n'est qu'un autre nom pour [Char]. Cependant, ce genre de définition présente un avantage quand on écrit le type d'une variable. Par exemple, si on utilise
(Double,Double,Double) comme type pour représenter une couleur, et qu'on crée une liste de couleurs, si on indique le type comme dans l'exemple ci-dessous, son rôle est assez obscur :
Code : Haskell | palette :: [(Double,Double,Double)]
palette = [(1,0,0), (0,1,1), (0,1,0)]
inverser :: (Double,Double,Double) -> (Double,Double,Double)
inverser (r,g,b) = (1-r,1-g,1-b)
|
Comparez avec ce code-là, où on a défini un type avec
type. Le code est tout de suite plus clair, et comme c'est moins long d'écrire les signatures de chaque valeur, vous pourrez toutes les écrire sans perdre votre temps, ce qui fait que le code est plus sûr et plus compréhensible.
Code : Haskell | type Couleur = (Double, Double, Double)
palette :: [Couleur]
palette = [(1,0,0), (0,1,1), (0,1,0)]
inverser :: Couleur -> Couleur
inverser (r,g,b) = (1-r,1-g,1-b)
|
Pour définir en général un nouveau nom pour un type déjà existant, il faut écrire :
type NomDuType = UnAutreType (Au,Nom) Super Long
Les noms de types doivent toujours commencer par une majuscule. Par exemple, MonSuperType est un nom valide, pas monSuperType
Utiliser data pour définir des types algébriques
La deuxième manière de déclarer des types utilise
data. Cette construction permet de faire beaucoup de choses, comme vous allez le voir dans les paragraphes qui suivent.
Des énumérations
Imaginons que vous êtes en train de coder un logiciel pour un marchand de glace. Ce marchand vend des glaces avec plusieurs goûts différents, et certains coûtent plus cher que d'autres. Il faut donc coder une fonction qui, pour un parfum donné, renvoie le prix d'une boule de glace à ce goût-là. Pour cela, il faut d'abord vous demander comment vous allez représenter un parfum. Une première solution serait d'utiliser des chaînes de caractères; la fonction ressemblerait à ceci :
Code : Haskell | type Parfum = String
prixParfum :: Parfum -> Double
prixParfum "chocolat" = 1.5
prixParfum "vanille" = 1.2
prixParfum "framboise" = 1.4
|
Le problème, c'est qu'il est très facile d'introduire des valeurs invalides, comme "qsd%ù&é" (ou de faire une faute d'orthographe quelque part dans le code). Pour être sûr de ne pas faire d'erreur, il faudrait mettre beaucoup de vérifications dans toutes les fonctions qui utilisent des parfums. Et même dans ce cas, on ne profite pas du système de types : les erreurs ne sont pas détectées à la compilation. On pourrait représenter les parfums avec des entiers, mais on se retrouve avec le même problème. On va donc utiliser data pour faire une énumération :
Code : Haskell | data Parfum = Chocolat
| Vanille
| Framboise
deriving Show
|
Cette fois, on a créé un nouveau type. Cette déclaration veut dire qu'une valeur de type Parfum est soit Fraise, soit Framboise, soit Chocolat. Le
deriving Show à la fin de la déclaration fait que ghc génère automatiquement une instance de Show pour notre type, si c'est possible. Cela nous permet notamment de travailler facilement avec dans ghci, c'est donc une bonne idée de l'indiquer.
Maintenant, pour traiter des valeurs de notre nouveau type, on doit utiliser le filtrage de motif. Ici, on définit la fonction prixParfum pour utiliser notre nouveau type :
Code : Haskell | prixParfum :: Parfum -> Double
prixParfum Chocolat = 1.5
prixParfum Vanille = 1.2
prixParfum Framboise = 1.4
|
On peut définir d'autres énumérations avec data, mais un nom ne doit être utilisé qu'une fois. Il est donc impossible de créer une autre énumération qui comprend une valeur comme Chocolat, Vanille ou Framboise. On peut redéfinir les booléens de cette façon :
Code : Haskell | data Booleen = Vrai | Faux
|
Types algébriques
Vous savez maintenant utiliser data pour créer des énumérations. Mais ce n'est qu'un cas particulier de quelque chose de plus général : les types algébriques, qu'on définit avec data.
Revenons à notre logiciel pour commander des glaces. Le glacier fait deux types de glace : des glaces à une boule, et des glaces à deux boules. On pourrait utiliser une liste pour représenter ces deux types de glace, mais dans ce cas, on risque d'avoir des commandes pour des glaces à 0 boule ou à 3 boules, alors que le glacier n'en fait pas. On va donc utiliser data pour créer un nouveau type :
Code : Haskell | data Glace = UneBoule Parfum
| DeuxBoules Parfum Parfum
deriving Show
|
Si on prononce "|" comme "ou", le sens de cette déclaration devient évident : une glace est soit une glace à une boule ayant un parfum, soit une glace à deux boules ayant deux parfums. Ensuite, on utilise le filtrage de motif pour différencier les deux cas dans nos fonctions :
Code : Haskell | prixGlace (UneBoule a) = 0.10 + prixParfum a
prixGlace (DeuxBoules a b) = 0.15 + prixParfum a + prixParfum b
|
Ainsi, pour créer un type avec data, on donne une liste de possibilité (les différents constructeurs, UneBoule et DeuxBoules dans le cas de glace), et les attributs qui correspondent à chaque possibilité.
Par exemple, pour un programme de dessin, on pourrait vouloir représenter des formes géométriques : cercle et rectangle. Pour définir un cercle, on a besoin de son centre (un point), et de son rayon; pour définir un rectangle, il faut deux points : la position du sommet en bas à gauche, et celle du sommet en haut à droite. Vous pouvez donc essayer d'écrire le type correspondant, et des fonctions
aire et
perimetre qui renvoient l'aire et le périmètre d'une forme.
Code : Haskell | type Point = (Float,Float)
data Forme = Cercle Point Float | Rectangle Point Point
aire :: Forme -> Float
aire (Rectangle (a,b) (c,d)) = abs (a-c) * abs (b-d)
aire (Cercle _ r) = pi * r^2
perimetre :: Forme -> Float
perimetre (Rectangle (a,b) (c,d)) = 2 * ( abs (a-c) + abs (b-d) )
perimetre (Cercle _ r) = 2 * pi * r
|
La troisième façon de définir des types en Haskell est d'utiliser newtype. En fait, newtype est un cas particulier de data : il permet seulement de définir des types à un seul constructeur, et ce constructeur ne doit prendre qu'un seul argument. Par exemple, pour éviter de mélanger les points avec autre chose, on pourrait écrire newtype Point = Point (Float, Float) (le Point à gauche du signe = est un nom de type, celui à droite le nom d'un constructeur de type, donc utiliser deux fois le nom Point ne pose pas de problème ici). La seule différence est qu'avec newtype, le compilateur sait qu'une valeur de type Point utilise forcément le constructeur Point, donc peut optimiser le programme pour qu'il fonctionne comme si on utilisait le type (Float,Float) à la place de Point. Cependant, quand le compilateur vérifie les types, les deux types sont différents, ce qui permet de repérer les erreurs où on utilise l'un à la place de l'autre.
Enregistrements
Maintenant, le glacier veut garder un profil de chacun de ses utilisateurs. Pour cela, il veut stocker le nom, le prénom, l'adresse e-mail, la date des première et dernière commandes de ce client, et la somme totale dépensée chez le glacier. On a donc toutes les informations nécessaires pour créer un type, et quelques fonctions utiles :
Code : Haskell 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | data Date = Date Int Int Int -- Une date : jour/mois/année
data Client = Client String String String Date Date Float
-- Créer un nouveau client qui n'a encore rien commandé
nouveauClient :: String -> String -> String -> Client
nouveauClient nom prenom mail = Client nom prenom mail (Date 0 0 0) (Date 0 0 0) 0
-- Actualiser les infos d'un client qui vient de passer une commande
actualiserClient : Date -> Float -> Client -> Client
actualiserClient date somme (Client nom prenom mail premiereCommande _ sommeCommandes) =
Client nom prenom mail premiereCommande date (sommeCommandes + somme)
-- Donne l'adresse mail d'un client
mailClient :: Client -> String
mailClient (Client _ _ mail _ _ _) = mail
|
Comme vous le voyez, ce type n'est pas facile à manipuler : on ne voit pas nettement le nom des champs, donc on risque d'inverser l'ordre de deux champs de même type, et d'avoir une erreur non trouvée par le système de type, ce n'est pas facile d'accéder à un champ du type, et quand on veut modifier une valeur, on est obligé de copier toutes les autres explicitement, ce qui fait du code vraiment très lourd.
Heureusement, pour ce genre de choses, on peut utiliser les enregistrements. On définit un type d'enregistrement comme ceci :
Code : Haskell | data Client = Client {
nom :: String,
prenom :: String,
mail :: String,
premiereCommande :: Date,
derniereCommande :: Date,
sommeCommandes :: Float
} deriving Show
|
On peut toujours créer un client en utilisant le constructeur et en donnant la valeur des champs dans l'ordre, mais on peut aussi indiquer le nom des champs. Dans ce cas, l'ordre n'importe pas :
Code : Haskell | unClient = Client { nom = "Dupont",
prenom = "Hubert",
mail = "hubert.dupont@example.com",
premiereCommande = Date 1 2 2003,
derniereCommande = Date 9 9 2009,
sommeCommandes = 13.3
}
autreClient = Client "Dupont" "Robert" "rdupont@example.com" (Date 29 2 2003) (Date 1 10 2009) 42
|
On peut aussi utiliser le nom des champs avec le filtrage de motif. Cependant, quand on définit un enregistrement, des fonctions sont automatiquement créées pour accéder à chacun des champs :
Code : Haskell | nomPrenom (Client {nom = nom, prenom = prenom}) = nom ++ " " ++ prenom
nomPrenom' client = nom client ++ " " ++ prenom client
|
Enfin, on dispose d'une syntaxe plus pratique pour modifier seulement quelques champs d'un enregistrement :
Code : Haskell | actualiserClient :: Date -> Float -> Client -> Client
actualiserClient date somme client = client {
derniereCommande = date,
sommeCommandes = sommeCommandes client + somme
}
|
Types récursifs, types paramétrés
Des paramètres pour les types
Dans cette partie, on va créer un nouveau type qui correspond aux listes à au moins un élément. Ce n'est pas forcément un type utile dans toutes les situations, mais des fois il peut être utile, pour des opérations qui n'ont pas de sens sur des listes vides. Une façon simple de créer un type qui correspond est de prendre une paire constituée d'un élément, et d'une liste d'éléments, ce qui garantit qu'on a au moins un élément. Cependant, en essayant de déclarer un tel type, vous allez avoir un problème : quel est le type de l'élément ?
On va commencer par définir notre type pour les entiers, et une ou deux fonctions :
Code : Haskell | data SomeInt = SomeInt Int [Int]
someIntToList :: SomeInt -> [Int]
someIntToList (SomeInt x xs) = x:xs
addInt :: Int -> SomeInt -> SomeInt
addInt i s = SomeInt i (someIntToList s)
|
On pourrait alors redéfinir un type à chaque fois qu'on veut un type différent pour les éléments. Mais ça nous oblige aussi à redéfinir les fonctions. On pourrait le faire par copier-coller, mais vous savez déjà que c'est une bonne façon de faire des erreurs bêtes, et de les copier partout dans le programme pour les rendre impossible à corriger, et que ça va à l'encontre du premier principe du programmeur (et de n'importe qui) : faire le moins possible de choses inutiles et inintéressantes. Dans ce cas, les fonctions ne font rien de spécial sur les éléments contenus dans le type SomeInt, on devrait donc pouvoir en faire des fonctions polymorphes. C'est ce qu'on ferait avec des listes, ou avec Maybe.
Pour résoudre ce problème, on va utiliser les types paramétrés :
Code : Haskell | data Some a = Some a [a]
someToList :: Some a -> [a]
someToList (Some x xs) = x:xs
add :: a -> Some a -> Some a
add i s = Some i (someToList s)
|
En fait, vous aviez déjà utilisé des types paramétrés, comme Maybe ou le type des listes. La seule chose que vous ne saviez pas faire, c'est en définir. Maintenant, vous êtes capables de redéfinir le type Maybe, mais pas encore le type des listes : ce sera le sujet de la suite.
Notez que vous pouvez aussi utiliser des paramètres quand vous déclarez un alias avec type, de la même façon qu'avec data. Il est aussi possible de prendre plusieurs paramètres. Vous pouvez donc définir des types comme :
Code : Haskell | -- Ce type représente des listes d'associations : par exemple [("Jean Dupont", 42), ("Jean Bon", 12)]
-- pour représenter l'argent dans le compte en banque d'un certain nombre de personnes
type Assoc a b = [(a,b)]
|
Types récursifs
Rappelez-vous du chapitre sur les suites : elles sont définies par deux constructeurs possibles,
[] (la liste vide), et
: qui permet d'ajouter un élément en tête d'une liste, et qui prend donc deux arguments, un élément et une liste d'éléments. Ce type est défini en fonction de lui même : c'est un type récursif.
Pour vous montrer comment définir des types récursifs, on va créer un type
MyList a, qui correspond en fait au type
[a], avec deux constructeurs : Nil et Cons.
Code : Haskell | data MyList a = Nil | Cons a (MyList a)
|
Voilà, définir un type récursif n'est pas vraiment compliqué. Ensuite, on peut l'utiliser comme n'importe quel type normal :
Code : Haskell | liste = Cons 1 (Cons 2 (Cons 3 Nil))
|
Exemples
Manipuler des arbres
Un arbre binaire est une structure de donnée qui peut se représenter sous la forme d'un arbre, dont chaque noeud contient une valeur et deux éléments fils (c'est à dire deux arbres), comme sur la figure ci-contre.
On voit bien qu'une telle structure de données se définit très facilement de manière récursive : à chaque niveau, soit on est arrivé au bout de l'arbre (représenté par le constructeur Feuille), soit on arrive à un embranchement, où l'arbre se sépare en deux branches. À chaque embranchement, on trouve un élément.
Code : Haskell | data Arbre a = Branche a (Arbre a) (Arbre a)
| Feuille
deriving Show
|
Par exemple, l'arbre donné comme exemple est représenté de la façon suivante :
Code : Haskell | arbreExemple = Branche 1
(Branche 2
(Branche 4 Feuille Feuille)
(Branche 5
(Branche 7 Feuille Feuille)
(Branche 8 Feuille Feuille)))
(Branche 3
Feuille
(Branche 6
(Branche 9 Feuille Feuille)
Feuille))
|
On appelle profondeur d'un arbre la distance maximale de la racine à une Feuille. Par exemple, si la racine est une Feuille, la profondeur vaut 0. On peut donc calculer la profondeur d'un arbre à l'aide d'une fonction récursive. On veut aussi des fonctions pour calculer le nombre de branches et le nombre de feuilles d'un arbre. On crée aussi une fonction permettant de calculer la somme des éléments d'un arbre.
Code : Haskell | profondeur Feuille = 0
profondeur (Branche _ gauche droite) = 1 + max (profondeur gauche) (profondeur droite)
feuilles Feuille = 1
feuilles (Branche _ gauche droite) = feuilles gauche + feuilles droite
branches Feuille = 0
branches (Branche _ gauche droite) = 1 + branches gauche + branches droite
somme Feuille = 0
somme (Branche el gauche droite) = el + somme gauche + somme droite
|
Comme vous pouvez le constater, ces fonctions se ressemblent beaucoup : on donne une valeur fixée pour les Feuilles, et pour chaque Branche, on combine les résultats obtenus avec la fonction sur les deux sous-arbres. On aimerait bien créer une fonction d'ordre supérieur pour factoriser ce code. Si vous suivez vraiment attentivement, vous devriez avoir une impression de déjà vu : dans le chapitre sur les listes, c'est à partir d'un procédé de récursivité utilisé par un certain nombre de fonctions qu'on a montré l'utilité de la fonction foldr sur les listes. Et en effet, la fonction d'ordre supérieur foldArbre qu'on va créer suit le même principe :
Code : Haskell | foldArbre f n Feuille = n
foldArbre f n (Branche e d g) = f e (foldArbre f n d) (foldArbre f n g)
profondeur' = foldArbre (\ _ d g -> 1 + max d g) 0
feuilles' = foldArbre (\ _ d g -> d + g) 1
branches' = foldArbre (\ _ d g -> 1 + d + g) 0
somme' = foldArbre (\ e d g -> e + d + g) 0
retourner = foldArbre (\ e d g -> Branche e g d) Feuille
|
Pour vous convaincre de la similarité entre foldr et foldArbre, comparez ces deux schémas :
Dans les deux schémas, fold remplace tous les constructeurs Branche par un appel à la fonction f, et tous les constructeurs Branche (qui ne prennent pas d'argument) par la valeur z. On peut définir de manière similaire une opération fold sur tous les types récursifs.
Arbres binaires de recherche
Les arbres binaires servent de base à un certain nombre de structures de données. Une structure simple et pourtant intéressante est l'arbre binaire de recherche (ou ABR). C'est un arbre binaire qui doit respecter une propriété particulière : pour chaque noeud de l'arbre, tous les éléments dans la branche gauche de l'arbre doivent être inférieurs à l'élément placé dans le noeud, et tous ceux situés à droite doivent être supérieurs. Par exemple, l'arbre ci-contre est un arbre binaire de recherche, mais celui donné comme exemple d'arbre n'en est pas un.
On peut déjà créer une fonction qui teste si un arbre est un ABR ou pas, et la tester dans ghci :
Code : Haskell 1
2
3
4
5
6
7
8
9
10
11
12
13
14 | -- teste si une propriété p est respectée par tous les éléments d'un arbre
allArbre _ Feuille = True
allArbre p (Branche e g d) = p e && allArbre p g && allArbre p d
abrValide Feuille = True
abrValide (Branche e g d) = allArbre (< e) g && allArbre (> e) d && abrValide g && abrValide d
abr = Branche 10
(Branche 5 Feuille (Branche 8 (Branche 7 Feuille Feuille) (Branche 9 Feuille Feuille)))
(Branche 20
(Branche 15 (Branche 12 Feuille Feuille) (Branche 17 Feuille Feuille))
(Branche 25 Feuille Feuille))
invalide = Branche 10 Feuille (Branche 3 Feuille Feuille)
|
| Prelude> abrValide abr
True
Prelude> abrValide invalide
False |
Si un arbre binaire s'appelle un arbre binaire de recherche, c'est bien parce qu'il est facile de rechercher des éléments dedans. Imaginons qu'on veuille vérifier si un élément est dans l'arbre. On se trouve donc à une Branche. Soit l'élément se trouve à cette branche, soit il se trouve à gauche, soit il se trouve à droite. On doit donc parcourir tout l'arbre pour savoir si un élément se trouve dans l'arbre avec cette méthode, ce n'est donc pas plus efficace que de chercher dans une simple liste. Cependant, on n'a pas pris en compte la propriété de l'arbre binaire de recherche, donc notre algorithme marche même sur un arbre binaire normal.
Dans le cas des arbres binaires de recherche, on sait que les éléments sont ordonnés. Donc, quand on se trouve à une Branche, on peut décider de quel côté aller chercher l'élément. On a donc qui un algorithme, qui au lieu d'explorer les deux possibilités à chaque branche n'en choisit qu'une seule : il est donc beaucoup plus performant.
Code : Haskell | rechercher _ Feuille = False
rechercher e (Branche f g d) | e == f = True
| e < f = rechercher e g
| e > f = rechercher e d
|
On teste ce code dans ghci pour voir s'il marche comme prévu :
Code : Console | *Main> rechercher 15 abr
True
*Main> rechercher 10 abr
True
*Main> rechercher 100 abr
False |
Et voilà, il a l'air de marcher correctement. Maintenant, on a besoin d'autres opérations pour manipuler les ABR, par exemple ajouter et supprimer des éléments. Pour ajouter un élément, on fait comme pour rechercher un élément, sauf qu'on reconstruit un nouvel arbre avec les données, et qu'on ajoute l'élément dès qu'on rencontre une feuille :
Code : Haskell | inserer e Feuille = Branche e Feuille Feuille
inserer e (Branche f g d) | e == f = Branche f g d
| e < f = Branche f (inserer e g) d
| e > f = Branche f g (inserer e d)
|
Ce code ne modifie pas l'arbre, mais en renvoie un nouveau. On pourrait donc s'inquiéter de ses performances : est-ce que tout l'arbre est copié à chaque fois pour rendre cela possible ? En regardant le code, vous pouvez trouver la réponse : seules les branches qui sont sur le chemin pour aller de la racine à l'élément qu'on a inséré ont été recréées. Les performances sont donc plutôt bonnes : avec une liste, il aurait fallu en moyenne recréer la moitié de la liste, alors que là on ne recopie que quelques branches de l'arbre.
D'ailleurs, on peut se servir de l'arbre binaire de recherche pour faire un tri plus rapide que le tri par insertion : au lieu d'insérer les éléments dans une liste triée, on les insère dans un ABR (donc trié lui aussi). Pour cela, on doit coder deux fonctions auxiliaires : une fonction
construireArbre, qui construit un arbre binaire de recherche à partir d'une liste triée, et d'une fonction
aplatir qui renvoie une liste triée constituée de tous les éléments d'un arbre binaire.
Code : Haskell 1
2
3
4
5
6
7
8
9
10
11
12 | -- construire un arbre à partir d'une liste
construireArbre :: (Ord a) => [a] -> Arbre a
construireArbre = foldr inserer Feuille
aplatir :: Arbre a -> [a]
aplatir = foldArbre (\e g d -> g ++ [e] ++ d) []
-- version sans foldArbre :
aplatir' Feuille = []
aplatir' (Branche e g d) = aplatir' g ++ [e] ++ aplatir' d
triABR :: (Ord a) => [a] -> [a]
triABR = aplatir . construireArbre
|
Une dernière opération utile sur les ABR est la suppression d'un élément (autrement dit, créer un nouvel arbre auquel on a enlevé un élément donné). C'est une opération un peu plus délicate à effectuer, et je vous invite à y réfléchir et à essayer de la coder vous-même avant de lire la solution (avec du papier et un crayon, c'est plus facile pour dessiner les arbres).
Puisqu'on sait déjà trouver un élément dans un arbre, on peut se ramener au cas où l'élément que l'on souhaite supprimer se trouve à la racine. Ensuite, on doit envisager différents cas suivant le ce qu'on trouve en allant à droite et à gauche : si on trouve deux Feuilles, il suffit de remplacer la racine par une Feuille. Si on trouve une Feuille et une Branche, on remplace la racine par cette Branche. Le cas compliqué est celui où on a deux branches. On doit donc chercher un nouvel élément qui servira de racine : pour cela, on prend le plus grand élément de la branche de gauche.
Code : Haskell 1
2
3
4
5
6
7
8
9
10
11
12
13
14 | supprimerPlusGrand (Branche e g Feuille) = (g,e)
supprimerPlusGrand (Branche e g d) = let (d',grand) = supprimerPlusGrand d in
(Branche e g d', grand)
supprimerRacine (Branche _ Feuille Feuille) = Feuille
supprimerRacine (Branche _ g Feuille) = g
supprimerRacine (Branche _ Feuille d) = d
supprimerRacine (Branche _ g d) = Branche e' g' d
where (g',e') = supprimerPlusGrand g
supprimer _ Feuille = Feuille
supprimer e (Branche f g d) | e == f = supprimerRacine (Branche f g d)
| e < f = Branche f (supprimer e g) d
| e > f = Branche f g (supprimer e d)
|
On a donc vu comment utiliser les arbres binaires de recherche comme structure de données pour représenter des ensembles, et les opérations qui vont avec.
Un problème se pose cependant. Quand on introduit successivement des éléments déjà ordonnés dans un ABR, à chaque fois l'élément qu'on insère va se retrouver à droite de l'arbre. Donc, tous les éléments vont être concentrés d'un côté, ce qui fait qu'on se retrouve finalement avec des opérations de recherche, d'insertion et de suppression inefficaces. Par exemple, avec un arbre à
éléments, il faut
opérations dans le pire des cas pour trouver si un élément est dans l'arbre. Au contraire, si l'arbre est équilibré (c'est-à-dire si la feuille qui est à la plus grande profondeur n'a pas une profondeur très différente de celle qui est le plus proche de la racine), il va avoir à peu près une profondeur de
, et donc il faudra
opérations pour rechercher un élément. Il existe des arbres où les opérations de modification rééquilibrent automatiquement l'arbre : c'est le cas des
arbres AVL et des
arbres rouge-noir.
Représenter des expressions mathématiques
On peut aussi utiliser des types algébriques récursifs pour représenter un petit langage de programmation. Par exemple, ici on va créer un type qui représente des expressions mathématiques simples (addition, multiplication, soustraction). Le constructeur Litt permet d'utiliser des valeurs littérales dans les expressions (par exemple
Lit 42), et Var sert à représenter une variable.
Code : Haskell | data Expr =
Litt Integer
| Var String
| Add Expr Expr
| Mul Expr Expr
deriving (Eq, Show)
-- Exemple : cette expression correspond à x^2+7x+1
test = Add (Mul (Var "x") (Var "x")) (Add (Mul (Litt 7) (Var "x")) (Litt 1))
|
On peut commencer par coder une fonction pour évaluer une expression, c'est-à-dire donner sa valeur. Elle prend en argument un contexte, qui donne la valeur des variables utilisées, et bien sûr une expression. Pour des raisons de simplicité, on ne s'occupera pas de la gestion des erreurs, par exemple si on ne connaît pas la valeur d'une variable utilisée.
Code : Haskell | -- Cette fonction renvoie la valeur d'une variable dans le contexte ctx
valeur ctx var = snd $ head $ filter (\(nom,_) -> nom == var) ctx
eval ctx (Add a b) = eval ctx a + eval ctx b
eval ctx (Mul a b) = eval ctx a * eval ctx b
eval ctx (Litt a) = a
eval ctx (Var s) = valeur ctx s
-- On évalue l'expression test pour x=5
valTest = eval [("x",5)] test
|
Le code pour évaluer nos expressions est donc plutôt simple. En revanche, la syntaxe pour écrire les expressions est très lourde : on pourrait vouloir créer un parser pour nos expressions mathématiques, qui transforme une chaîne de caractère comme
(x^2+72x+2)(20+y+xy) en la valeur du type Expr qui correspond. Si vous cherchez quelque chose à faire, ça peut être amusant de regarder comment faire. En tout cas, vous verrez dans la prochaine sous-partie une astuce amusante pour ne pas avoir à faire ça vous même.
On peut aussi coder des fonctions qui font des transformations sur les expressions : développer, évaluer tout ce qui peut être évalué sans connaître la valeur de toutes les variables, réduire une expression (regrouper les termes en x ensembles, puis les termes en
, ...
Code : Haskell | developper (Add x y) = Add (developper x) (developper y)
developper (Mul x y) = case (developper x, developper y) of
(Add a b,y') -> developper (Add (Mul a y') (Mul b y'))
(x', Add a b) -> developper (Add (Mul x' a) (Mul x' b))
(x',y') -> Mul x' y'
developper e = e
|
Il y a beaucoup de choses intéressantes à faire à partir de ça : vous pouvez coder d'autres fonctions de manipulation des expressions mathématiques (par exemple, mettre les expressions dans une forme correcte ou essayer de factoriser une expression) ou bien rajouter des opérations à ce tout petit langage de base pour créer un petit langage de programmation.
Créez vos propres types
gnomnain
Trouvez une formation
Suggestions
Flux RSS News
Twitter
Facebook
Google+