Les types somme permettent d'énumérer les valeurs que peuvent prendre nos variables. Plus précisément, c'est une union disjointe, car chaque constructeur apporte son propre ensemble, afin d'enrichir le type. Nous introduisons le mot-clé
type qui permet de créer de nouveaux types en OCaml.
Code : OCaml
Les variables de type
foo pourront prendre les valeurs A ou B. A et B sont appelés des
constructeurs de type. Les constructeurs de type doivent impérativement commencer par une majuscule.
Code : OCaml | # let a = A ;;
val a : foo = A
# let a = C ;;
Error: Unbound constructor C
|
Notons que A et B symbolisent les constructeurs possibles pour notre type ; dans ce cas, pensez à la similarité avec les
enum de certains langages. Mais les types sommes sont beaucoup plus puissants ! Voici un autre exemple :
Code : OCaml | type foo = A of int | B of string
|
Ce type indique que si notre variable a été construite avec le constructeur A on peut lui donner, en plus, une valeur entière. Si en revanche elle a été construite avec B, on peut lui donner une valeur de type chaîne ! Exemples :
Code : OCaml | # let a = A 3 ;;
val a : foo = A 3
# let b = B "the game" ;;
val b : foo = B "the game"
# let c = B 4 ;;
Error: This expression has type int but an expression was expected of type string
|
Le typeur d'OCaml nous rappelle à l'ordre : il sait que le constructeur B attend une valeur de type string.
Filtrage des types somme
Les types somme se prêtent tout particulièrement bien au filtrage ! Souvenez-vous que d'une manière générale le filtrage permet d'énumérer les cas possible selon
la valeur d'une variable. Dans le premier type somme que je vous ai montré un peu plus haut, on n'avait que deux valeurs possibles : A et B, elles sont donc énumérables dans un filtrage de motif :
Code : OCaml | # type foo = A | B ;;
type foo = A | B
# let f a = match a with
A -> "ananas"
| B -> "baobab" ;;
val f : foo -> string = <fun>
# f A ;;
- : string = "ananas"
|
Tuples et récursivité
Revenons un petit peu sur la construction
A of int. Ce qui suit le mot clé
of est un type, il peut donc être un produit. La syntaxe est la même que ce que vous retourne l'interpréteur OCaml lorsque que vous lui donnez un tuple :
Code : OCaml | # type foo = A of int * int ;;
type foo = A of int * int
# let a = A 2, 3 ;;
Error: The constructor A expects 2 argument(s),
but is applied here to 1 argument(s)
|
Oups ! Petit problème de précédence on dirait :
Code : OCaml | # let a = A (2, 3) ;;
val a : foo = A (2, 3)
|
Notez que
let a = A 2, 3 est tout à fait correct, mais n'a pas la même sémantique :
Code : OCaml | # type foo = A of int | B ;;
type foo = A of int | B
# let a = A 2, 3 ;;
val a : foo * int = (A 2, 3)
|
Un exemple pertinent d'utilisation des tuples dans les types somme est qu'ils permettent de définir des arbres en OCaml ! En y réfléchissant, un arbre c'est soit l'arbre vide, soit un nœud étiquetté par une valeur et qui contient un fils gauche et un fils droit.
Code : OCaml | # type tree = Nil | Node of tree * int * tree ;;
type tree = Nil | Node of tree * int * tree
# let t = Node (Node (Nil, 4, Nil), 1, Node (Nil, 3, Nil)) ;;
val t : tree = Node (Node (Nil, 4, Nil), 1, Node (Nil, 3, Nil))
|
Les types OCaml sont récursifs par défaut, contrairement aux fonctions ! Pas besoin du mot clé rec, je peux directement utiliser mon type dans mon type, donc.
Malheureusement, mon type d'arbre souffre d'un gros problème : j'ai été obligé de préciser le type des étiquettes (entier), celui-ci est donc figé et si je veux construire un arbre avec des flottants, je vais être obligé soit de créer un autre type d'arbre... soit d'utiliser le polymorphisme !
Polymorphisme sur les types somme
Souvenez-vous des listes en OCaml. Codons par exemple la fonction qui retourne la tête d'une liste :
Code : OCaml | # let h = function [] -> failwith "blbl" | x :: s -> x ;;
val h : 'a list -> 'a = <fun>
|
Notre fonction travaille sur des listes polymorphes, c'est-à-dire qu'on ne connait pas le type des éléments de notre liste, on sait juste que c'est une liste. OCaml précise bien que le type est polymorphe en le notant
'a. On voudrait pouvoir faire la même chose avec nos types somme. Essayons de créer un type de liste :
Code : OCaml | type maliste = Nil | Elem of int * maliste
|
Une liste, c'est soit une liste vide, soit un élément suivi d'une liste. Le problème c'est le int, on voudrait que ce soit 'a. Remplacer bêtement int par 'a ne marchera pas. Pourquoi ? Car le type de notre liste serait toujours "liste", mais celui-ci pourrait contenir des valeurs... de différents types ! Voyons voir avec un exemple, en reprenant notre fonction qui retourne la tête d'une liste, mais en ajoutant 1 à celle-ci :
Code : OCaml | # type maliste = Nil | Elem of 'a * maliste ;;
???
# let h = function Nil -> failwith "blbl" | Elem (x, s) -> x + 1 ;;
val h : maliste -> int = <fun>
# let l = Elem ("coucou", Nil) ;;
val l : maliste = Elem (1, Nil)
# h l ;;
???
|
Problem? Ici
l est bien de type
maliste, l'application
(h l) est donc correctement typée, et d'après le type de
h, devrait nous retourner un entier. Pourtant, on va se retrouver à additionner une chaîne avec un entier, et ça c'est pas correct !
Le problème réside dans le fait qu'il est nécessaire de paramétrer notre type ; de même que les listes d'entiers en OCaml sont de type
int list, notre liste devrait être de type
int maliste :
Code : OCaml | type 'a maliste = Nil | Elem of 'a * 'a maliste
|
Ici
'a s'appelle le
paramètre de type. Notre liste
maliste est paramétrée par un type polymorphe
'a. Voyons ce que nous donne l'interpréteur si on lui redonne notre code maintenant :
Code : OCaml | # let h = function Nil -> failwith "blbl" | Elem (x, s) -> x + 1 ;;
val h : int maliste -> int = <fun>
# let l = Elem ("coucou", Nil) ;;
val l : string maliste = Elem ("coucou", Nil)
# h l ;;
Error: This expression has type string maliste but an expression was expected of type int maliste
|
Et cette fois-ci on obtient bien une erreur de typage à l'application de h à l. Ouf.
Je vous laisse en exercice la création d'un type d'arbres polymorphes, et en bonus, codez un la-profondeur-d'abord-recherche (plus connu sous le nom de
DFS).