Le polymorphisme paramétrique

Une fonction de cette sorte a dans sont type des paramètres ou variables de type qui pourront être spécialisés (on dit aussi instanciés) à n'importe quel type. Par exemple, dans le type de longueur², le symbole 'a est un paramètre de type.

# let rec longueur l = if l =[] then 0 else 1 + longueur (List.tl l);;
longueur : 'a list -> int = <fun>

Le type 'a list -> int est lu: ``pour tout type a arbitraire, la fonction qui prend en argument une liste d'éléments de type a et rend un résultat de type int''.

# longueur [4;3];;
- : int = 2
# longueur ["ab"];;
- : int = 1

Lorsqu'on applique longueur à [4,3], le paramètre de type a est instancié à int et donc, le type de la fonction est instancié à int list -> int. Ainsi, cette fonction a une infinité de types: autant qu'on pourra construire en spécialisant le paramètre de type vers un type arbitraire.

Notation (Instantiation):
On note l'instantiation ou spécialisation d'une variable de type a vers un type t par $[a \mapsto t]$. Par exemple, l'instantiation de a par int est notée $[a \mapsto {\tt int}]$.

Exemple:
L'instantiation $[a \mapsto {\tt int}]$ appliquée sur ('a list -> int) est notée
$(a {\tt\ list -> int})[a \mapsto {\tt int}]$ et donne en résultat (int list -> int). Un tel type spécialisé est appelé une instance du type polymorphe ('a list -> int).

Définition: (Instance)
On dit qu'un type $\tau'$ est une instance polymorphe du type $\tau$ s'il existe une spécialisation $[a \mapsto t]$ des variables de type de $\tau$ telle que $\tau' = \tau[a \mapsto t]$.

Remarque:
Ce qui caractérise le polymorphisme paramétrique est la relation d'instantiation qui existe entre le type général de la fonction polymorphe, et le type particulier de chaque spécialisation. Un type polymorphe a des instances polymorphes.

Par exemple, on peut appliquer la fonction longeur à la liste ["ab"] car celle-ci a le type string list qui est une instance de ('a list). En revanche on ne peut pas l'appliquer à "ab", car son type string n'est pas une instance de ('a list).

Voici quelques exemples de fonctions polymorphes:

#let identite x = x;;
val identite : 'a -> 'a = <fun>

# identite 1;;
- : int = 1
# identite true;;
- : bool = true
# identite [1;2];;
- : int list = [1; 2]

#let pg x y = x > y;;
val pg : 'a -> 'a -> bool = <fun>

# pg 1 2;;
- : bool = false
# pg 'a' 'b';;
- : bool = false
# pg "bonjour" "adieu";;
- : bool = true

#let rec member x l =
 match l
 with [] -> false
  |   a::r -> if a=x then true else member x r;;
val member : 'a -> 'a list -> bool = <fun>

# member 1 [3;4;1];;
- : bool = true
# member 'a' ['b';'c'];;
- : bool = false

Exercice: Quelles sont les instanciations qu'il faut appliquer pour typer chaque appel?