Introduction au système de types en Haskell

Par stendhal666

Ce billet sera court et sans grande difficulté. Il servira de marche-pied ou d'aide-mémoire pour les billets suivants, qui présenteront un des aspects les plus excitants mais aussi les plus abstraits de la programmation en Haskell: l'apport de la théorie des catégories au développement d'applications. Je tenterai ici de vous présenter, aussi clairement que possible, le système de types de Haskell, à la fois souple et puissant.

Ce que vous savez déjà
- Haskell possède un système de type statique (la régularité est vérifiée à partir du code, pas pendant l'exécution) et strict (aucune conversion automatique n'est acceptée).
- Le compilateur et l'interpréteur sont capables, sauf ambiguïté du programme, d'inférer les types utilisés à partir d'éléments de contexte (ex: fonctions appelées sur les arguments)
- la syntaxe basique d'une déclaration de type est:

nom :: Type

Par exemple:

> pi :: Double

Pour les fonctions, on a:

nomDeFonction :: arg1 -> arg2 -> ... -> argN -> returnType

Par exemple:

> integerSum :: [Integer] -> Integer

Ce que vous allez apprendre
Le système de types Haskell est plus souple et plus puissant que cela. Il permet d'utiliser des types génériques, plus ou moins semblables aux templates du C++, mais également d'ajouter des contraintes de type: pour reprendre l'exemple du C++, ces contraintes seraient l'équivalent des "concepts" qu'il est envisagé d'ajouter dans une norme future du langage. Enfin, Haskell permet de créer de nouveaux types, des alias de types et enfin de les "recouvrir".

Les types génériques
La fonction integerSum que nous avons déclarée est sympathique, mais si on lui donne une liste de Float, elle la refusera sèchement. Pourtant, l'algorithme pour additionner les membres d'une liste de Float ou de Double n'est pas différent. Aussi existe-t-il la possibilité de donner un type générique aux arguments d'une fonction:

> sum :: [a] -> a

NB: contrairement aux types concrets, les types génériques commencent par une minuscule.

Les lecteurs attentifs se doutent que la fonction sum fait appel à un opérateur (+), qui aurait donc comme signature:

> (+) :: a -> a -> a

Nous voilà dans une situation insatisfaisante: on voulait s'éviter d'écrire une fonction sum pour chaque type numérique, et nous voilà avec un opérateur d'addition qui accepte n'importe quel type: des connexions à des bases de données, des arbres binaires... La seule contrainte est que chaque membre de l'addition, et le résultat, soient de même type (celui que 'a' représente).

Les classes de types (typeclasses)
Haskell permet de créer des familles de types, qui peuvent être ensuite utilisées pour placer des contraintes de types sur les arguments génériques d'une fonction. Pour vous faire une idée des familles prédéfinies, en voilà la hiérarchie en une image:




NB: vous pouvez retrouver cette image et des informations complémentaires ici.

La syntaxe pour créer une classe est la suivante:

Un exemple simple est la classe Eq:

class Eq a where

(==) :: a -> a -> Bool
x == y = if x /= y then False else True
(/=) :: a -> a -> Bool
x /= y = if x == y then False else True

Un type est une instance de la classe Eq si elle implémente au moins l'une des deux fonctions (remarquez en effet que chacune est définie par rapport à l'autre). Comme le nom de ces fonctions est déjà pris (par la classe Eq), un mécanisme d'instanciation est nécessaire -plus simplement, il faut déclarer que notre type est une instance de cette classe. Par exemple, pour un type User:

instance Eq User where

(==) = sameId -- est vrai si les deux utilisateurs ont le même id

Lors de la déclaration d'une fonction, nous pouvons désormais exiger qu'un type abstrait soit l'instance d'une classe. La syntaxe est:

nomDeFonction :: constraint1 Class NomDe Type, constraint2 Class NomDe Type, ... => NomDeType -> NomDeType -> ...

Prenons l'exemple d'une fonction filtre, qui conserve les éléments d'une liste égaux à son premier argument:

filter :: Eq a => a -> [a] -> [a]
filter _ [] = []
filter n (x : xs) = if x == n then x : (filter n xs) else filter n xs

Créer de nouveaux types
Cette possibilité n'est réellement intéressante que conjuguée à la création de nouveaux types -et Haskell le permet. Si Haskell était dépourvu d'un type Bool, on pourrait en créer un ainsi:

data Bool = True | False

- data est le mot clé qui introduit la création d'un nouveau type
- Bool est le nom du nouveau type
- True et False sont les constructeurs d'instances de ce type
- et le symbole pipe ( | ) sépare les constructeurs

Avec des constructeurs sans argument, on est tout de même un peu limité. Pour reprendre notre type User, il pourrait être défini ainsi:

data User = User Integer String

- le nom du constructeur et du type peuvent être identiques

Un nouvel utilisateur peut être alors créé:


Mieux encore, un constructeur peut faire référence au type qu'il construit, afin de créer un type récursif. L'exemple canonique est celui de la liste:

data Liste a = Vide | Cons a (Liste a)

- Liste est un type abstrait, qui doit être paramétrisé par un autre type (le type des éléments qu'elle contient)
- a est le nom du type (générique) qui paramétrise le type Liste

On pourrait donc créer une de ces listes ainsi:


ou encore:


Conclusion:
Nous n'avons pas encore couvert tout le système de type de Haskell, mais nous avons vu les aspects les plus intéressants. Les alias ne présentent pas de difficulté particulière: le mot-clé type remplace le mot-clé typedef du C/C++, essentiellement. La "couverture" de type est une notion un peu plus avancée dont les avantages n'apparaissent pas à ce stade: il me semblait donc inutile de surcharger cette cuillère, qui est déjà une bonne cuillère à soupe...

Exercices:
- dans l'interpréteur GHCI, la commande :t suivie d'une expression renvoie le type de cette expression. Regardez le type de quelques fonctions. En particulier, le type de l'opérateur de composition (.) ou d'application $, ou encore le type de différentes fonctions numériques
- définir un type BinaryTree
- quels sont pour vous les avantages des différents systèmes de types?