II. Valeurs, types, et autres friandises▲
Parce que Haskell est un langage purement fonctionnel, tous les calculs sont faits via l'évaluation d'expressions (terme syntaxique) qui retournent des valeurs (entités abstraites que l'on considère comme des réponses). À chaque valeur est associé un type (intuitivement, on peut se représenter les types comme des ensembles de valeurs). Les expressions peuvent être des valeurs atomiques telles que l'entier 5, le caractère 'a', ou la fonction \x -> x+1, mais elles peuvent aussi être des valeurs structurées telles que la liste [1,2,3] ou la paire ('b',4).
De même que les expressions dénotent des valeurs, les expressions de type sont des termes syntaxiques qui dénotent des valeurs de type (ou, plus simplement, des types). Les expressions de type peuvent être des types atomiques tels que Integer (l'ensemble infini des entiers), Char (les caractères) ou Integer->Integer (les fonctions qui, à un Interger associent un Integer), mais elles peuvent aussi être des types structurés tels que [Integer] (liste homogène d'entiers) ou (Char,Integer) (les paires composées d'un caractère et d'un entier).
Avec Haskell, toutes les valeurs sont dites de « première-classe », c'est-à-dire qu'elles peuvent être passées à des fonctions en tant qu'arguments, retournées en tant que résultats, placées dans des structures de données, etc. En revanche, les types ne sont pas de « première classe ». En un sens, les types décrivent des valeurs. On appelle typage, l'association d'une valeur avec son type. En reprenant les exemples donnés plus haut, nous écririons leur typage comme suit :
5
::
Integer
'a'
::
Char
inc ::
Integer
->
Integer
[1
,2
,3
] ::
[Integer
]
('b'
,4
) ::
(Char
,Integer
)
Les deux points (« :: ») se lisent « est de type ».
Avec Haskell, les fonctions sont en principe définies par une série d'équations. Par exemple, la fonction inc peut être définie par la simple équation :
inc n =
n+
1
Une équation est un exemple de déclaration. Un autre exemple de déclaration est la signature de type (), avec laquelle nous pouvons déclarer un type explicite pour inc :
inc ::
Integer
->
Integer
Nous aurons encore beaucoup à dire à propos de la définition des fonctions dans la section .
À des fins pédagogiques, quand nous voudrons indiquer que l'évaluation d'une expression e1 retourne une autre expression ou une valeur e2, nous écrirons :
e1 => e2
Par exemple, notons que :
inc (inc 3
) =>
5
Le système de typage statique de Haskell définit une relation formelle entre des types et des valeurs (). Ce système garantit que les programmes Haskell opèrent sur des types cohérents; autrement dit, que le programmeur n'aura pas d'erreurs d'incompatibilité de types. Par exemple, il n'est pas possible, en principe, d'additionner deux caractères; ainsi, l'expression 'a'+'b' est incohérente en raison du type de ses opérandes (en anglais on dit que l'expression est ill-typed). L'avantage principal des langages à types statiques est bien connu : toutes les erreurs de type sont détectées à la compilation. Cependant, un tel système ne peut détecter toutes les erreurs; le type d'une expression telle que 1/0 n'est pas incohérent, mais son évaluation provoquera une erreur à l'exécution. Néanmoins, ce système permet de détecter beaucoup d'erreurs à la compilation, d'aider l'utilisateur à raisonner sur les programmes, et permet également au compilateur de générer un code plus efficace (par exemple, les marqueurs ou les tests de type ne sont pas requis à l'exécution).
Ce système de typage garantit également que les signatures de type fournies par l'utilisateur sont correctes. En fait, le système de typage de Haskell est même suffisamment puissant pour nous épargner l'écriture de toute signature de type (à quelques exceptions près, qui seront décrites plus tard). On dit que le système de typage infère les types corrects. Néanmoins, il est recommandé d'utiliser judicieusement les signatures de type, telles que celles que nous avons données pour inc, parce qu'elles sont une forme efficace de documentation du code et aident à mettre en évidence les erreurs de programmation.
[Le lecteur notera l'emploi d'une majuscule à la première lettre des identificateurs qui dénotent un type spécifique, tels que Integer et Char, mais pas sur les identificateurs qui dénotent des valeurs, tel que inc. Ce n'est pas une simple convention : Haskell impose cette syntaxe lexicale. De plus, la casse des caractères suivants est également importante : foo, fOo et fOO sont tous des identificateurs distincts.]
II-A. Les types polymorphes▲
Haskell intègre également les types polymorphes, c'est-à-dire des types qui sont universellement quantifiés d'une certaine manière pour tous les types. Les expressions de type polymorphes décrivent essentiellement des familles de types. Par exemple, (forall a)[a] est la famille de types qui comprend, pour tout type a, le type de listes de a. Les listes d'entiers (p. ex. [1,2,3]), les listes de caractères (p. ex. ['a','b','c']), et même les listes de listes d'entiers (p. ex. [[1,2,3],[4,5,6]]), etc. sont toutes membres de cette famille. (Notons, toutefois, que [2,'b'] n'est pas un exemple valide, puisqu'il n'existe pas de type simple contenant à la fois 2 et 'b'.)
[Les identificateurs tels que a ci-dessus sont appelés variables de type, et sont en minuscules pour les distinguer des types spécifiques tels que Int. De plus, puisque Haskell utilise uniquement des types universellement quantifiés, il n'est pas nécessaire d'écrire explicitement le symbole de la quantification universelle, et donc, dans l'exemple ci-dessus, nous écrivons simplement [a]. En d'autres termes, toutes les variables de type utilisent implicitement une quantification universelle.]
Les listes sont des structures de données utilisées fréquemment dans les langages fonctionnels et elles sont un bon véhicule pour expliquer les principes du polymorphisme. Dans Haskell, la liste [1,2,3] est en réalité un raccourci pour la liste 1:(2:(3:[])), où [] est la liste vide et : est l'opérateur infixe qui ajoute son premier argument au début de son deuxième argument (une liste). (: et [] sont, respectivement, l'équivalent de cons et nil dans Lisp.) Puisque : est associatif à droite, nous pouvons également écrire cette liste comme ceci : 1:2:3:[].
Comme exemple d'une fonction définie par l'utilisateur et opérant sur une liste, considérons l'opération qui consiste à compter les éléments contenus dans une liste :
length ::
[a] ->
Integer
length [] =
0
length (x:xs) =
1
+
length xs
Cette définition s'explique presque d'elle-même. Nous pouvons lire l'équation comme suit : « La longueur d'une liste vide est 0, et la longueur d'une liste dont le premier élément est x et le reste de la liste est xs est égal à 1 plus la longueur de xs. » (Notons la convention de dénomination utilisée ici ; xs est le pluriel de x, et devrait être lu comme tel.)
Bien qu'il soit intuitif, cet exemple met en lumière un aspect important de Haskell qui doit encore être expliqué : la correspondance de motif (pattern matching en anglais). Le terme gauche de l'équation contient des motifs (patterns) tels que [] et x:xs. Dans l'application d'une fonction, ces motifs sont mis en correspondance avec le paramètre réel d'une manière intuitive ([] correspond uniquement à une liste vide et x:xs correspond à n'importe quelle liste contenant au moins un élément, associant x au premier élément et xs au reste de la liste). Si la correspondance est positive, le terme droit de l'équation est évalué et retourné en tant que résultat de l'application. Si une correspondance est négative, la correspondance de l'équation suivante est testée, et si toutes les correspondances sont négatives, une erreur en résulte.
La définition de fonctions par correspondance de motifs est très courante avec Haskell, et l'utilisateur devrait se familiariser avec toutes les sortes de motifs qui sont autorisées. Nous reviendrons sur cet aspect dans la section .
La fonction length est également un exemple de fonction polymorphe. Elle peut être appliquée à une liste contenant des éléments de n'importe quel type. Par exemple : [Integer], [Char], or [[Integer]].
length [1
,2
,3
] =>
3
length ['a'
,'b'
,'c'
] =>
3
length [[1
],[2
],[3
]] =>
3
Voici deux autres fonctions polymorphes utiles, opérant sur des listes, que nous utiliserons plus tard. La fonction head retourne le premier élément d'une liste, la fonction tail retourne toute la liste à l'exception du premier élément.
head ::
[a] ->
a
head (x:xs) =
x
tail ::
[a] ->
[a]
tail (x:xs) =
xs
Contrairement à length, ces fonctions ne sont pas définies pour toutes les valeurs possibles de leur argument : une erreur d'exécution surviendra quand ces fonctions seront appliquées à une liste vide.
Formellement, les types polymorphes sont plus généraux que les autres, dans le sens où l'ensemble de valeurs qu'ils définissent est plus grand. Par exemple, le type [a] est plus général que le type [Char]. En d'autres termes, le deuxième peut être dérivé du premier par une substitution appropriée de a. Concernant cette hiérarchie des généralisations, le système de typage de Haskell a deux importantes propriétés : Premièrement, toute expression correctement typée est garantie d'avoir un type principal unique (explication plus bas) et deuxièmement, le type principal peut être inféré automatiquement (). En comparaison d'un langage monomorphe tel que C, le lecteur s'apercevra que le polymorphisme améliore l'expressivité, et que l'inférence de type diminue le fardeau du typage supporté par le programmeur.
Le type principal d'une expression ou d'une fonction est le type le moins général qui, intuitivement, « contient toutes les occurrences de l'expression ». Par exemple, le type principal de head est [a]->a. Par contre [b]->a, a->a, ou même a sont des types corrects, mais trop généraux, tandis que [Integer]->Integer est trop spécifique. L'existence d'un type principal unique est une caractéristique du système de typage Hindley-Milner, qui est à la base du système de typage de Haskell, ML, Miranda, (« Miranda » est une marque déposée de Research Software, Ltd.) et de plusieurs autres langages (principalement fonctionnels).
II-B. Types définis par l'utilisateur▲
Avec Haskell, nous pouvons définir nos propres types de données en utilisant une déclaration data () dont voici une introduction par une série d'exemples :
Dans Haskell, un type prédéfini important est celui des valeurs de vérité :
data
Bool
=
False
|
True
Le type ainsi défini est le type Bool, et il a exactement deux valeurs : True et False. Le type Bool est un exemple de constructeur de type (nul-aire), et True et False sont des constructeurs de données (ou simplement constructeurs).
Dans le même esprit, nous pourrions avoir besoin de définir un type « couleur » :
data
Color =
Red |
Green |
Blue |
Indigo |
Violet
Les types Bool et Couleur sont tous deux des exemples de types énumératifs, puisqu'ils consistent en une série finie de constructeurs (nul-aires) de données.
Voici un exemple de type comprenant uniquement un constructeur de données :
data
Point a =
Pt a a
Parce qu'il a un unique constructeur, un type comme Point est souvent appelé un type tuple, puisqu'il est essentiellement le produit cartésien (binaire, dans ce cas) d'autres types. (Les tuples correspondent plus ou moins à des records (enregistrements) dans d'autres langages.) En revanche, les types à constructeurs multiples, tels que Bool et Couleur, sont appelés des types union (disjoint) ou somme.
Plus important encore, Point est un exemple de type polymorphe : pour tout type t, il définit le type des points cartésiens utilisant t comme type de coordonnées. Le type Point peut maintenant clairement être vu comme un constructeur de type unaire, puisqu'à partir du type t il construit un nouveau type Point t. (Dans ce sens, l'exemple de liste donné plus haut, [], est également un constructeur de type. À n'importe quel type t donné, on peut « appliquer » [] qui retourne un nouveau type [t]. La syntaxe de Haskell permet d'écrire []t de cette manière : [t]. De la même manière, -> est un constructeur de type : Soit les types donnés t et u, t->u est le type des fonctions associant des éléments de type t à des éléments de type u.)
Notons que le type du constructeur de données Pt est a -> a -> Point a, et par conséquent, les typages suivants sont valides :
Pt 2
.0
3
.0
::
Point Float
Pt 'a'
'b'
::
Point Char
Pt True
False
::
Point Bool
Par contre, une expression telle que Pt 'a' 1 est mal typée puisque 'a' et 1 sont de types différents.
Il est important de faire une distinction entre l'application d'un constructeur de données pour obtenir une valeur et l'application d'un constructeur de type pour obtenir un type. La première se produit à l'exécution et c'est de cette manière que les choses sont calculées dans Haskell, alors que la deuxième se produit à la compilation et fait partie du système de typage qui garantit la validité des types.
[Les constructeurs de type tel que Point et les constructeurs de données, tels que Pt sont chargés dans des espaces de noms différents. Cela permet d'utiliser le même nom pour un constructeur de type et un constructeur de données, comme le montre l'exemple suivant :
data
Point a =
Point a a
Même si cela peut prêter à confusion, cela permet de mettre en évidence le lien entre un type et son constructeur de données.]
II-B-1. Les types récursifs▲
Les types peuvent aussi être récursifs, comme dans le cas du type des arborescences binaires :
data
Tree a =
Leaf a |
Branch (Tree a) (Tree a)
Nous avons défini ainsi un type polymorphe d'arborescence binaire dont les éléments sont soit des nœuds « feuille » contenant une valeur de type a, soit des nœuds internes (« branches ») contenant (récursivement) deux sous-arborescences.
À la lecture de telles déclarations de données, il faut se souvenir que Arborescence est un constructeur de type, alors que Branche et Feuille sont des constructeurs de données. Hormis la connexion établie entre ces deux constructeurs, la déclaration ci-dessus définit essentiellement les types suivants pour Branche et Feuille :
Branch ::
Tree a ->
Tree a ->
Tree a
Leaf ::
a ->
Tree a
Avec cet exemple, nous avons défini un type suffisamment riche pour permettre la définition d'intéressantes fonctions (récursives) qui l'utilise. Supposons, par exemple, que nous souhaitions définir une fonction frange qui retourne une liste de tous les éléments dans les feuilles d'une arborescence en allant de gauche à droite. Il est généralement utile de commencer par écrire le type d'une nouvelle fonction. Dans ce cas, nous voyons que le type devrait être Arborescence a -> [a]. Ce qui revient à dire que frange est une fonction polymorphe qui, pour tout type a associe des arborescences de a à une liste de a. En voici une définition convenable :
fringe ::
Tree a ->
[a]
fringe (Leaf x) =
[x]
fringe (Branch left right) =
fringe left ++
fringe right
Ici ++ est l'opérateur infixe qui concatène deux listes (sa définition complète sera donnée dans la section ).
Comme dans l'exemple length donné plus tôt, la fonction frange est définie en utilisant une correspondance de motif, sauf qu'ici nous introduisons des motifs impliquant des constructeurs définis par l'utilisateur : Feuille et Branche. [Notons que les paramètres formels sont facilement identifiables par leurs noms qui commencent par une minuscule.]
II-C. Les synonymes de Type▲
Pour notre confort, Haskell permet de définir des synonymes de type. C'est-à-dire, des noms pour les types fréquemment utilisés. Les synonymes de type se créent en utilisant la déclaration type (). En voici quelques exemples :
type
String
=
[Char
]
type
Person =
(Name,Address)
type
Name =
String
data
Address =
None |
Addr
String
Les synonymes de type ne définissent pas de nouveaux types, mais ils donnent simplement un nouveau nom à des types préexistants. Par exemple, le type Personne -> Nom est strictement équivalent à (String,Adresse) -> String. Les nouveaux noms sont souvent plus courts que ceux dont ils sont synonymes, mais cela n'est pas l'unique avantage des synonymes de type : ils peuvent également améliorer la lisibilité des programmes qu'ils rendent plus mnémotechniques. L'exemple précédent le démontre bien. Il est même possible de donner de nouveaux noms à des types polymorphes :
type
AssocList a b =
[(a,b)]
Est le type de « listes associatives » qui associent des valeurs de type a à des valeurs de type b.
II-D. Les types internes n'ont rien de particulier▲
Précédemment, nous avons présenté plusieurs types « internes » tels que les listes, les tuples, les entiers et les caractères. Nous avons également montré comment de nouveaux types pouvaient être définis par l'utilisateur. Hormis la syntaxe spécifique, les types internes ont-ils quoi que ce soit de particulier par rapport aux types définis par l'utilisateur ? La réponse est non. La syntaxe spécifique est une commodité et elle se conforme à des conventions historiques, mais n'a aucune conséquence sémantique.
Pour mettre ce point en exergue, considérons la déclaration de type que nous écririons pour redéfinir ces types internes, si nous y étions autorisés, avec notre syntaxe spécifique. Par exemple, le type Char pourrait être réécrit de cette manière :
data
Char
=
'a'
|
'b'
|
'c'
|
..
. – This is not valid
|
'À'
|
'B'
|
'C'
|
..
. – Haskell code!
|
'1'
|
'2'
|
'3'
|
..
.
..
.
La syntaxe du nom de ces constructeurs n'est pas valide. Pour bien faire, il faudrait écrire quelque chose comme :
data
Char
=
Ca |
Cb |
Cc |
..
.
|
CA |
CB |
CC |
..
.
|
C1 |
C2 |
C3 |
..
.
Même si ces constructeurs sont plus concis, ce n'est pas une manière très conventionnelle de représenter des caractères.
Malgré tout, écrire un tel « pseudocode » Haskell nous aide à mieux comprendre cette syntaxe spécifique. Cela montre que le type Char n'est qu'un type énumératif qui consiste en un grand nombre de constructeurs nul-aires. Cette manière de représenter le type Char démontre que l'on peut utiliser une correspondance de motif sur des caractères dans la définition d'une fonction, comme nous pouvions nous attendre à pouvoir le faire pour n'importe quel constructeur de type.
[Cet exemple introduit l'usage des commentaires dans Haskell. Les caractères – ainsi que tous ceux qui suivent jusqu'à la fin d'une ligne sont ignorés. Haskell permet également les commentaires emboîtés qui sont de la forme {-…-} et peuvent être insérés n'importe où ().]
De la même manière, nous pourrions définir Int (ensemble fini d'entiers homogènes) et Integer avec :
data
Int
=
-
65532
|
..
. |
-
1
|
0
|
1
|
..
. |
65532
– more pseudocode
data
Integer
=
..
. -
2
|
-
1
|
0
|
1
|
2
..
.
où -65532 et 65532 sont, respectivement, les valeurs minimum et maximum des entiers pour une implémentation donnée. Int est une énumération beaucoup plus grande que Char, mais elle est finie. En revanche, le pseudocode pour Integer est conçu pour donner une énumération infinie.
À ce petit jeu, les tuples sont également faciles à définir :
data
(a,b) =
(a,b) – more pseudocode
data
(a,b,c) =
(a,b,c)
data
(a,b,c,d) =
(a,b,c,d)
. .
. .
.
Chacune des déclarations ci-dessus définit un type tuple d'une longueur donnée, (…) ayant un rôle aussi bien dans la syntaxe de l'expression (en tant que constructeur de données) que dans la syntaxe de l'expression de type (en tant que constructeur de type). Les points verticaux après la dernière déclaration signalent un nombre infini de telles déclarations, pour indiquer que Haskell autorise les tuples de n'importe quelle longueur.
Les listes peuvent également être traitées facilement et, en prime, elles sont récursives :
data
[a] =
[] |
a :
[a] – more pseudocode
Nos précédentes explications concernant les listes s'expliquent plus clairement à présent : [] est la liste vide, et : est l'opérateur infixe de construction de liste. Par conséquent [1,2,3] doit être équivalent à la liste 1:2:3:[] (: est associatif à droite). Le type de [] est [a], et le type de : est a->[a]->[a].
[La syntaxe de notre pseudodéfinition de « : » est légale. En effet, les constructeurs infixes sont autorisés dans les déclarations data, et on les distingue des opérateurs infixes (pour la correspondance de motifs) par le fait qu'ils doivent commencer par un « : » (exigence à laquelle « : » se conforme de manière rudimentaire.]
À ce stade le lecteur devrait soigneusement noter les différences entre les listes et les tuples. Les définitions que nous en avons faites ci-dessus mettent ces différences en évidence. Notons, en particulier, la nature récursive du type liste dont les éléments sont homogènes et de longueur arbitraire, ainsi que la nature non récursive du type d'un tuple (particulier) dont les éléments sont hétérogènes et de longueur fixe. Les règles de typage pour les tuples et les listes devraient également être claires :
Pour (e1,e2,…,eN), n>=2, si ti est le type de ei, alors, le type du tuple est (t1,t2,…,tN).
Pour [e1,e2,…,eN], n>=0, chaque ei doit être du même type t, et le type de la liste est [t].
II-D-1. Les compréhensions de listes et les séquences arithmétiques▲
De même qu'avec les dialectes Lisp, les listes sont primordiales dans Haskell, et ainsi que dans d'autres langages fonctionnels, il existe beaucoup de friandises syntaxiques pour aider à leur création. En plus des constructeurs de listes abordés précédemment, Haskell fournit une expression connue sous le nom de compréhension de liste qui s'explique mieux avec des exemples :
[ f x |
x <-
xs ]
Intuitivement, cette expression peut se lire « La liste de tout f x où x appartient à xs ». La ressemblance avec la notation des ensembles n'est pas une coïncidence. La phrase x <- xs est appelée un générateur, qui peuvent être plusieurs, comme dans :
[ (x,y) |
x <-
xs, y <-
ys ]
Cette compréhension de liste forme le produit cartésien des deux listes xs et ys. Les éléments sont sélectionnés comme si les générateurs étaient « emboîtés » de gauche à droite (le générateur le plus à droite variant plus rapidement). Donc, si xs est [1,2] et ys est [3,4], le résultat est [(1,3),(1,4),(2,3),(2,4)].
Outre les générateurs, des expressions booléennes appelées gardes sont permises. Les gardes imposent des contraintes aux éléments générés. Par exemple, voici une définition concise de l'algorithme de tri que tout le monde aime :
quicksort [] =
[]
quicksort (x:xs) =
quicksort [y |
y <-
xs, y<
x ]
++
[x]
++
quicksort [y |
y <-
xs, y>=
x]
Afin d'améliorer encore la manipulation des listes, Haskell offre une syntaxe spéciale pour les séries arithmétiques, que la série d'exemples suivante vous révèle :
[1
..
10
] =>
[1
,2
,3
,4
,5
,6
,7
,8
,9
,10
]
[1
,3
..
10
] =>
[1
,3
,5
,7
,9
]
[1
,3
..
] =>
[1
,3
,5
,7
,9
, ..
. (infinite sequence)
Plus de détails seront donnés sur les séquences arithmétiques dans la section , et sur les « listes infinies » dans la section.
II-D-2. Chaînes de caractères▲
Un autre exemple de friandise syntaxique pour les types internes est révélé par le fait que la chaîne de caractères « bonjour » est en réalité un raccourci pour la liste de caractères ['b','o','n','j','o','u','r']. En effet, le type de « bonjour » est String, ou String est le synonyme d'un type prédéfini (que nous avons donné dans un exemple précédent) :
type
String
=
[Char
]
Cela signifie que nous pouvons utiliser des fonctions polymorphes prédéfinies opérant sur des listes pour traiter des chaînes de caractères. Par exemple :
"Bonjour"
++
"monde"
=>
"Bonjour monde"