Programmation fonctionnelle (Haskell)

Les types simples

La definition d’un type comprend la description d’un ensemble de valeurs eventuellement infini. Dans ce texte, nous verrons comment les types de base sont definis en Haskell. Il est evident que ces techniques de definition peuvent etre utilisees pour introduire de nouveaux types.

Definition par enumeration

Une premi`ere m´ethode pour d´efinir un type dont l’ensemble de valeurs est fini, est d’´enum´erer explicitement tous les el´ements appartenant a` ce type. Le type Bool – comprenant les valeurs logiques – et le type Char – comprenant les caract`eres – sont tous les deux d´efini par l’´enum´eration explicite de leurs el´ements.

Le type booleen

Le type bool´een est d´efini en Haskell comme l’ensemble comprenant les va-leurs True et False :
data Bool = False | True
On observe l’usage des majuscules dans le nom du type et de ses valeurs. En-suite, on peut d´efinir des fonctions qui prennent un argument bool´een utilisant “pattern matching” comme dans l’exemple suivant :
not : : Bool −> Bool
not True = False
not False = True
Afin de simplifier une expression de la forme not e, les ´equations sont utilis´ees comme des r`egles de r´e-´ecriture. D’abord, e est simplifi´ee a` sa forme canonique. Si ce processus se termine et r´esulte a` True, l’´evaluateur appliquera la premi`ere r`egle. Si le r´esultat est False, la deuxi`eme r`egle est utilis´ee. Si e ne peut pas ˆetre r´eduit a` une forme canonique, la valeur de not e est ind´efinie. Alors not⊥
= ⊥ et not est donc une fonction stricte. On pourrait dire qu’il y a donc trois valeurs bool´eennes : True, False et ⊥. En fait, chaque type en Haskell inclut une valeur ‘anonyme’ : ⊥. Les op´erations logiques ∧ et ∨ sont d´efinies de fa¸con similaire :
(&&) : : Bool −> Bool −> Bool
( | | ) : : Bool −> Bool −> Bool
False && x = False
True && x = x
False | | x = x
True | | x = True
Ces d´efinitions utilisent pattern matching sur l’argument gauche. Pour simpli-fier une expression de la forme e1&&e2, l’´evaluateur simplifie d’abord e1 a` sa forme canonique (si possible). Si le r´esultat est False, l’´evaluateur emploiera la premi`ere r`egle et retourna False comme r´esultat (e2 n’est donc pas evalu´ee). Si par contre la valeur de e1 est True, l’´evaluateur emploiera la deuxi`eme r`egle et retourera la valeur de e2 (ce qui n´ecessite donc l’´evaluation de e2 a` sa forme canonique). On a donc
⊥ && False = ⊥
False && ⊥ = False
True && ⊥ = ⊥
Autrement dit, (&&) est stricte dans son argument gauche, mais ne pas dans son argument droite. Une autre d´efinition de (&&) serait
False && False = False
False && True = False
True && False = False
True && True = True
Cette d´efinition utilise pattern matching sur les deux arguments ; elle est donc stricte dans ses deux arguments.
On peut introduire les op´erateurs de comparaison : (==) et (/=). Ces op´erateurs seront red´efinis pour chaque type rencontr´. Alors il faut mieux in-troduire une classe de types.
c l a s s Eq a where
(==) , (/=) : : a −> a−> Bool
La classe de types Eq comprend donc deux fonctions (parfois appel´ees m´ethodes) dont la signature est
(==) , (/=) : : Eq a => a −> a−> Bool
Ensuite on d´eclare Bool une instance de cette classe en fournissant les d´efinitions concr`etes des m´ethodes (==) et (/=) dans le context Bool.1
instance Eq Bool where
x == y = ( x && y ) | | ( not x && not y )
x /= y = not ( x == y )
De fa¸con similaire, on introduit les op´erateurs de comparaison (<), (<=), (>=) et (>) qui seront d´efinis pour chaque type d’une classe Ord qui ressemble les types dont les el´ements sont ordonn´es.
c l a s s (Eq a ) => Ord a where
(<), (<=), (>=), (>) : : a −> a −> Bool
( x <= y ) = ( x < y ) | | ( x == y )
( x >= y ) = ( x > y ) | | ( x == y )
( x > y ) = not ( x <= y )
On observe la restriction de la classe ord aux types qui appartiennent a` la classe Eq. Autrement dit, Ord est d´efinie comme une sous-classe de eq. La classe Ord comprend 4 op´erations dont 3 (les op´erations (<=), (<=) et (>)) sont d´efinies par la classe elle-mˆeme en fonction de la quatri`eme op´eration (<) et de l’op´eration (==) d´efinie dans la classe Eq. En d´eclarant un type instance de Ord, il suﬃt donc de fournir une d´efinition de (>). Dans l’exemple de Bool :
instance Ord Bool where
False < False = False
False < True = True
True < False = False
True < True = False
Les d´efinitions de (<=), (<=) et (>) sont donc reprises de la classe.
1On observe la diﬀ´erence entre les symboles == (comparaison) et = (d´efinition).

Le type des caracteres

Le type Char est pr´ed´efini en Haskell et comprend les 256 symboles de la table ASCII. Ils incluent les symboles alphanum´eriques ainsi que quelques ca-ract`eres de contrˆole comme le retour a` la ligne etc. Dans leur forme canonique, les caract`eres sont repr´esent´es en entourant le symbole concern´ par des guille-mets, par exemple ‘a’, ‘7’ , etc. Une espace est repr´esent´ee par ‘ ’. Les fonctions suivantes sont pr´ed´efinies :
ord : : Char −> Int
chr : : Int −> Char
Elles ´etablissent la correspondance entre un caract`ere et sa rang´ee dans la table ASCII. Les caract`eres peuvent ˆetre compar´es et test´es sur (in)´egalit´. On a instance Eq Char where
( x == y ) = ( ord x == ord y )
instance Ord Char where
( x < y ) = ( ord x < ord y )
Dans cette d´efinition, on utilise le fait que Int est il-mˆeme une instance de Eq et de Ord.

Autres enumerations

On peut utiliser le technique d’´enum´eration pour introduire de nouveaux types.
data Jour = Dim | Lun | Mar | Mer | Jeu | Ven | Sam
Cette d´efinition introduit le type Jour comprenant 8 el´ements : 7 valeurs qui sont repr´esent´ees par les constantes Dim, Lun, etc. et la valeur ind´efinie ⊥.
En g´en´eral on veut que les el´ements d’une enum´eration soient comparables. Afin de d´eclarer le nouveau type instance de Eq et de Ord, il est pr´ef´erable d’´etablir une correspondance une-`a-une entre les constantes d’une enum´eration et un ensemble d’entiers. A cet eﬀet on introduit une classe de types dont les el´ements sont enum´erables :
c l a s s Enum a where
toEnum : : a −> Int
fromEnum : : Int −> a
La correspondance entre les constantes d’une enum´eration d’une part et un ensemble d’entiers d’autre part est ´etablit en d´eclarant le type d’´enum´eration une instance de Enum, ce qui n´ecessite de fournir des d´efinitions concr`etes de toEnum et fromEnum. Il est clair que ces d´efinitions doivent ˆetre telles que fromEnum (toEnum x) = x pour chaque x mais on ne peut pas expri-mer cette exigence en Haskell. On observe que le mˆeme principe d’associer une valeur enti`ere unique a` chaque el´ement d’une enum´eration ´etait pr´esent dans la d´efinition du type Char. En eﬀait, on peut d´eclarer
instance Enum Char where
toEnum = ord
fromEnum = chr
Supposons la d´efinition suivante pour le type Jour :
instance Enum Jour where
toEnum Dim = 0
toEnum Lun = 1
toEnum Mar = 2
toEnum Mer = 3
toEnum Jeu = 4
toEnum Ven = 5
toEnum Sam = 6
Ensuite, on peut d´eclarer
instance Eq Jour where
( x == y ) = (toEnum x == toEnum y )
instance Ord Jour where
( x < y ) = (toEnum x < toEnum y )
Haskel permet, pour n’importe quel type d´efini par enum´eration, de d´eriver automatiquement les d´efinitions qui font le type une instance de Eq, de Ord et de Enum. Il suﬃt d’introduire une clause “deriving” comme dans l’exemple suivant :
data Jour = Dim | Lun | Mar | Mer | Jeu | Ven | Sam deriving (Eq, Ord, Enum)

La definition par constructeurs

Les tuples

Le type polymorphe Pair a b represente l’ensemble de toutes les paires qui comprennent une valeur de a et une de b.
data P a i r a b = MkPair a b
Ce type est d´eclar´ par une fonction dite constructeur MkPair dont la signature
MkPair : : a −> b −> P a i r a b
En g´en´eral, un constructeur est une fonction ayant les propri´et´es suivantes :
– elle n’a pas de d´efinition. Son seul eﬀet est de construire une valeur. Dans l’exemple ci-dessus MkPair True ’b’ est une valeur (du type Pair Bool Char en forme canonique.
– elle peut ˆetre utilis´ee dans la partie gauche d’une d´efinition (afin de r´ealiser pattern matching).
Consid´erons les fonctions de base
f s t : : P a i r a b −> a
f s t MkPair x y = x
snd : : P a i r a b −> b
snd MkPair x y = y
Haskell permet d’utiliser une syntaxe alternative pour les paires. Le type Pair a b est repr´esent´ par (a,b) et une valeur Mkpair e1, e2 est repr´esent´ee par (e1, e2). Les fonctions de base deviennent donc
f s t : : ( a , b ) −> a
f s t ( x , y ) = x
snd : : ( a , b ) −> b
snd ( x , y ) = y
On observe l’usage de pattern matching dans la d´efinition de ces fonctions. Afin d’´evaluer un expression de la forme fst e, l’´evaluateur simplifie d’abord e jusqu’`a une forme (e1, e2) et retourne ensuite la sous-expression e1. N’oublions pas que le type (a,b) inclut la valeur ind´efinie ⊥. Pourtant, ⊥ 6= (⊥, ⊥). En eﬀet, les constructeurs sont des fonctions non-strictes.
Les el´ements d’un type (a,b) peuvent ˆetre compar´es si les el´ements de a et de b peuvent ˆetre compar´es eux-mˆemes :
instance (Eq a , Eq b ) => Eq ( a , b ) where
( x , y ) == ( u , v ) = ( x == u ) && ( y == v )
instance (Ord a , Ord b ) => Ord ( a , b ) where
( x , y ) < ( u , v ) = ( x < u ) | | ( x == u && y < v )
On apelle cette ordre l’ordre lexicographique. Les tuples ne sont pas limit´es a` deux valeurs ; on peut ´egalement utiliser les triplets (a,b,c), les 4-tuples (a,b,c,d), etc.

Autres types

En g´en´eral un type est defini par une enumeration de constructeurs.
data Either = Left Bool | Right Char
Le type Either comprend les valeurs construites par les constructeurs Left et Right dont les signatures
On peut g´en´eraliser ce type a` un type polymorphe
data Either a b = Left a | Right b
Dans ce cas, les constructeurs sont
Left : : a −> Either a b
Right : : b −> Either a b
A nouveau, les constructeurs peuvent ˆetre utilis´es pour pattern matching
case : : ( a −> c , b −> c ) −> Either −> c case ( f , g ) ( Left x ) = f x case ( f , g ) ( Right y ) = g y
En supposant que les valeurs de a et de b peuvent ˆetre compar´ees, on peut d´efinir la comparaison des el´ements du type Either a b :
instance (Eq a , Eq b ) => Eq ( Either a b ) where Left x == Left y = ( x == y )
Left x == Right y = False
Right x == Left y = False
Right x == Right y = ( x == y )
instance (Ord a , Ord b ) => Ord ( Either a b ) where Left x < Left y = ( x < y )
Left x < Right y = True
Right x < Left y = False
Right x < Right y = ( x < y )
Ces d´eclarations sont obtenues de fa¸con automatique par la d´eclaration
data Either a b = Left a | Right b
deriving (Eq, Ord)

La definition par equivalence

Il est facile d’introduire un synonyme pour un type type Angle = Float
type P o s i t i o n = ( Float , Float )
Les synonymes peuvent ˆetre polymorphes eux-mˆemes :
type P a i r s a = ( a , a )
type Automorphisme a = a −> a
type Flag a = ( a , Bool )
Un synonyme peut ˆetre d´efini en fonction d’un autre synonyme tant qu’il n’y a pas de circularit´es dans les d´efinitions. Chaque synonyme d’un type h´erite les m´ethodes qui ont et´ d´eclar´ees dans les instances du type en-dessous. Ces m´ethodes ne peuvent pas ˆetre red´efinies.
Au lieu de cr´eer un synonyme, on peut introduire un nouveau type en em-ballant un autre type par un constructeur : data Angle = MkAngle Float