Diaporama n°14

Le langage OCaml - Définitions de types

Le point sur les types en OCaml

Rappel :

Quels sont les types OCaml déjà rencontrés ?

• types de base : int bool float char string

• fonction : t1 -> t2

• produit : t1 * t2 * ...

• référence : 'a ref

• tableau : 'a array

I. Renommer un type existant

II. "Forcer" un type

III. Définir un type polymorphe

IV. Définir un type "enregistrement"

V. Exemple de type "somme" et "filtrage par motifs"

NB : diaporama suivant :

• type somme et filtrage par motifs (spécificité OCaml)

• le type option (cas particulier de type somme)

• les listes (listes "chaînées", cas particulier de type somme)

I. Renommer un type existant

• type nom = type_existant

• c'est l'équivalent d'un typedef en C

• permet d'améliorer la lisibilité du code (?)

Exercice / Exemple 1 :

on souhaite manipuler des fonctions mathématiques classiques : $\mathbb{R}\rightarrow \mathbb{R}$

• Définir un nouveau type fct_reelle correspondant à ces fonctions

type fct_reelle = float -> float (* définition d'un nouveau type *)

type fct_reelle = float -> float

NB : remarquer la sortie du "TopLevel"

• on a défini un nouveau type qui s'appelle fct_reelle et qui vaut ...

• Définir la fonction compose qui réalise la composée de deux fonctions f et g
• Définir par composition f1 correspondant à la fonction $x\mapsto e^{\sqrt{x}}$

let compose f g = fun x -> f (g x)

let f1 = compose exp sqrt

type fct_reelle = float -> float

val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

val f1 : float -> float = <fun>

NB : dans la sortie du "TopLevel", les indications de type ne sont pas très lisibles ...

Le typeur OCaml a inféré le type le plus général, et n'a pas utilisé le nouveau type défini

II. "Forcer" un type

En OCaml, le programmeur a la possiblité d'indiquer / spécifier / "forcer" le type des variables.

let f arg1 arg2 = ... devient

let f (arg1 : type1) (arg2 : type2) : type = ... indiquant le type des paramètres et le type de la valeur calculée

• Le typeur doit s'adapter à ces contraintes supplémentaires.

let compose (f:fct_reelle) (g:fct_reelle) : fct_reelle = fun x -> f (g x);;

let compose (f:fct_reelle) (g:fct_reelle) : fct_reelle indique que :

• f est de type fct_reelle,
• g est de type fct_reelle,
• le résultat sera de type fct_reelle

type fct_reelle = float -> float;;

let compose (f:fct_reelle) (g:fct_reelle) : fct_reelle = fun x -> f (g x);;

let f1 = compose exp sqrt;;

type fct_reelle = float -> float

val compose : fct_reelle -> fct_reelle -> fct_reelle = <fun>

val f1 : fct_reelle = <fun>

NB : les indications de type sont maintenant plus lisibles

III. Définir un type polymorphe

• type 'a nom = type_existant : avec 'a variable de type

• type ('a, 'b) nom = type_existant : avec 'a 'b variables de type

• ...

Exercice / Exemple 2 :

En OCaml, les n-uplets (type produit) sont hétérogènes.

• Définir un type 'a triplet correspondant à un triplet homogène polymorphe

(* sans forçage des types *)

type 'a triplet = 'a * 'a * 'a;;

type 'a triplet = 'a * 'a * 'a

• Définir les fonctions compo1 compo2 compo3 permettant de récupérer les éléments du triplet

let compo1 (x, y, z) = x;;
let compo2 (x, y, z) = y;;
let compo3 (x, y, z) = z;;

val compo1 : 'a * 'b * 'c -> 'a = <fun>

val compo2 : 'a * 'b * 'c -> 'b = <fun>

val compo3 : 'a * 'b * 'c -> 'c = <fun>

• Définir la fonction est_croissant qui détermine si les éléments d'un triplet sont dans l'ordre croissant

let est_croissant (x, y, z) = x <= y && y <= z;;

val est_croissant : 'a * 'a * 'a -> bool = <fun>

• Définir un int triplet, un float triplet et tester la fonction est_croissant

let t1 = (1, 2, 3);;
let t2 = (1.3, 1.1, 1.0);;

est_croissant t1;;
est_croissant t2;;

val est_croissant : 'a * 'a * 'a -> bool = <fun>

val t1 : int * int * int = (1, 2, 3)

val t2 : float * float * float = (1.3, 1.1, 1.)

- : bool = true

- : bool = false

(* avec forçage des types : c'est plus lisible *)
type 'a triplet = 'a * 'a * 'a;;

let compo1 ((x, y, z):'a triplet) = x;;
let compo2 ((x, y, z):'a triplet) = y;;
let compo3 ((x, y, z):'a triplet) = z;;
let est_croissant ((x, y, z):'a triplet) = x <= y && y <= z;;
let t1 : 'a triplet = (1, 2, 3);;
let t2 : 'a triplet = (1.3, 1.1, 1.0);;

est_croissant t1;;
est_croissant t2;;

type 'a triplet = 'a * 'a * 'a

val compo1 : 'a triplet -> 'a = <fun>

val compo2 : 'a triplet -> 'a = <fun>

val compo3 : 'a triplet -> 'a = <fun>

val est_croissant : 'a triplet -> bool = <fun>

val t1 : int triplet = (1, 2, 3)

val t2 : float triplet = (1.3, 1.1, 1.)

- : bool = true

- : bool = false

IV. Type Enregistrement

enregistrement (record) = ensemble de valeurs nommées et typées

• type nom = { champ0 : type0; champ1 : type1 ...} : définition d'un type enregistrement

• { champ0 = expr0; champ1 = expr1 ... } : valeur de type

NB : l'ordre des champs n'est pas important, mais tous les champs doivent avoir une valeur

• v.champ0 : accès à un champ

NB enregistrement

• enregistrement OCaml $\simeq$ struct en C

• c'est en quelque sorte un type tuple type0 * type1 * ... dont les composantes aurait un nom

• un champ est a priori non modifiable (cf mot clé mutable)

Exemple / Exercice 3

• Définir un type personne permettant de représenter le nom, le prénom et l'âge d'un individu

type personne = {nom : string; prenom : string; age : int} (* type enregistrement *)

type personne = { nom : string; prenom : string; age : int; }

• Définir une personne p1 appelée Tryphon Tournesol, agé de 61 ans, et une personne p2 appelée Archibald Haddock agé de 53 ans

let p1 = {nom = "Tournesol"; prenom = "Tryphon"; age = 61} (* définition d'une valeur *)

let p2 = {prenom = "Archibald"; age = 53; nom = "Haddock" } (* l'ordre de champ est sans importance *)

val p1 : personne = {nom = "Tournesol"; prenom = "Tryphon"; age = 61}

val p2 : personne = {nom = "Haddock"; prenom = "Archibald"; age = 53}

• Définir Tintin 22 ans ?

let p3 = {prenom = "Tintin"; age = 22;} (* Erreur : un enregistrement doit avoir tous ses champs définis *)

File "[21]", line 1, characters 9-39:
1 | let p3 = {prenom = "Tintin"; age = 22;} (* Erreur : un enregistrement doit avoir tous ses champs définis *)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: Some record fields are undefined: nom

let p3 = {prenom = "Tintin"; nom = ""; age = 22;}

val p3 : personne = {nom = ""; prenom = "Tintin"; age = 22}

• Définir une fonction phrase_presentation qui prend en paramètre une personne et renvoie une chaîne de caractères "Bonjour, je m'appelle ... et j'ai ... ans"

let phrase_presentation p = (* type inféré *)
"Bonjour, je m'appelle " ^ p.prenom ^ " " ^ p.nom ^ 
" et j'ai " ^ (string_of_int p.age) ^" ans";;

val phrase_presentation : personne -> string = <fun>

NB : le typeur infère p : personne à partir des accès aux champs

Dans le doute, on peut spécifier le type

let phrase_presentation (p : personne) =  (* type indiqué par le programmeur *)
"Bonjour, je m'appelle " ^ p.prenom ^ " " ^ p.nom ^ 
" et j'ai " ^ (string_of_int p.age) ^" ans";;

val phrase_presentation : personne -> string = <fun>

• Définir un tableau contenant les 3 personnes (quel est son type ?)

• Afficher la phrase de présentation pour chacun d'eux (avec une boucle for)

let tab = [|p1; p2; p3|];;

for i = 0 to Array.length tab -1 do
    print_endline (phrase_presentation tab.(i))
done;;

val tab : personne array =
  [|{nom = "Tournesol"; prenom = "Tryphon"; age = 61};
    {nom = "Haddock"; prenom = "Archibald"; age = 53};
    {nom = ""; prenom = "Tintin"; age = 22}|]

Bonjour, je m'appelle Tryphon Tournesol et j'ai 61 ans
Bonjour, je m'appelle Archibald Haddock et j'ai 53 ans
Bonjour, je m'appelle Tintin  et j'ai 22 ans

- : unit = ()

• Définir une fonction naissance qui prend un nom et un prenom en paramètres et renvoie une personne d'âge 0

let naissance prenom nom = {prenom = prenom; nom = nom; age = 0};;

let p = naissance "mp2i" "gaylu";;

val naissance : string -> string -> personne = <fun>

val p : personne = {nom = "gaylu"; prenom = "mp2i"; age = 0}

let naissance p n = {prenom = p; nom = n; age = 0};;

let pers = naissance "mp2i" "gaylu";;

val naissance : string -> string -> personne = <fun>

val pers : personne = {nom = "gaylu"; prenom = "mp2i"; age = 0}

Le champ d'un enregistrement n'est a priori pas modifiable

p.age <- p.age + 1

File "[32]", line 1, characters 0-18:
1 | p.age <- p.age + 1
    ^^^^^^^^^^^^^^^^^^
Error: The record field age is not mutable

Exercice (en TP) :

Définir un type pour les nombres complexes avec deux champs re et im, et les opérations associées (addition, produit, module ...)

Champ modifiable (mutable)

Pour rendre un champ modifiable, il faut l'avoir déclaré mutable

• type nom = { champ0 : type0; mutable champ1 : type1 ...} : définition d'un type enregistrement avec champ1 modifiable

• { champ0 = expr0; champ1 = expr1 ... } : valeur de type (pas de changement)

• v.champ0 : accès au champ (pas de changement)

• v.champ1 <- expr : modification d'un champ mutable

NB cf modification d'un élément de tableau tab.(i) <- expr

type personne = {nom : string; prenom : string; mutable age : int} (* champ mutable *)

type personne = { nom : string; prenom : string; mutable age : int; }

let p1 = {nom = "mp2i"; prenom = "Limoges"; age = 0};;

p1.age <- p1.age + 1;;

p1;;

val p1 : personne = {nom = "mp2i"; prenom = "Limoges"; age = 0}

- : unit = ()

- : personne = {nom = "mp2i"; prenom = "Limoges"; age = 1}

Enregistrement polymorphe

un ou plusieurs champs peuvent être polymorphes ...

• type 'a nom = { ... }

• type ('a,'b) nom = { ... }

• ...

NB : retour sur les références

Une référence est un enregistrement polymorphe à champ mutable

???

Une référence est un enregistrement polymorphe à champ mutable

ref;;

- : 'a -> 'a ref = <fun>

NB: la fonction ref crée une référence de type 'a ref (polymorphe)

let x = ref 0;

val x : int ref = {contents = 0}

NB: x est un enregistrement à un seul champ contents

x.contents <- 9;; (* utilisation anormale d'une référence *)
x;;
x.contents;;

- : unit = ()

- : int ref = {contents = 9}

- : int = 9

NB: le champ contents est mutable

NB : Les références sont des enregistrements polymorphes à champ mutable

On utilise bien sûr les notations habituelles pour les références

let x = ref 0;; (* utilisation normale d'une référence *)
x := 9;;
x;;
!x;;

val x : int ref = {contents = 0}

- : unit = ()

- : int ref = {contents = 9}

- : int = 9

Exercice (en TP) :

Reproduire le mécanisme des références OCaml :

• Définir un type enregistrement polymorphe 'a myref ayant un champ mutable contenu
• Définir une fonction myref : 'a -> 'a myref qui crée une référence
• Définir une fonction set : 'a myref -> a -> unit qui modifie le contenu de la référence
• Définir une fonction get : 'a myref -> 'a qui renvoie la valeur du contenu

Type récursif ?

En C, on peut définir des structures récursives ... en OCaml ?

type 'a maillon = {valeur : 'a ; suivant : 'a maillon}  (* bug ...*)

let m = {valeur = 12; suivant = ????}

NB : en OCaml, les valeurs sont définies d'emblée. Il nous faudrait donc un maillon pour pouvoir définir un maillon ...

ATTENTION : NULL n'existe pas en OCaml ... on peut s'en sortir avec un type option (cf plus tard) ou un type somme (à suivre)

V. Type somme et Filtrage (exemple)

aussi appelé

type énuméré, type union, type construit, ou type algébrique

Principe :

Il s'agit d'un type qui correspond à plusieurs autres types

type nom = t1 | t2 | t3 ... (Notation incorrecte)

Une valeur d'un tel type pourrait être du type t1 ou du type t2 ou du type t3.

Pour pouvoir distinguer ces différents cas, on utilise des Constructeurs qui vont nous permettre de définir et manipuler de telles valeurs.

Définir un type somme

(Notation correcte)

type nom = Constructeur1 of t1 | Constructeur2 of t2 | Constructeur3 of t3 ...

Exemple / Exercice 4

• Définir un type nombre pour représenter les int et les float. On choisira de noms de Constructeurs pertinents.

type nombre = Entier of int | Reel of float;;

type nombre = Entier of int | Reel of float

Définir une valeur construite

Pour définir une valeur de type nombre, on utilise le Constructeur adapté, un peu comme une fonction.

type nombre = Entier of int | Reel of float;;

let n1 = Entier 4;;
let n2 = Reel (-1.0);;

type nombre = Entier of int | Reel of float

val n1 : nombre = Entier 4

val n2 : nombre = Reel (-1.)

NB : notre type nombre englobe deux sortes de valeurs :

• les entiers, constuits avec le Constructeur Entier
• les réels, construits avec le Constructeur Reel

NB :

• un Constructeur commence toujours par une lettre Majuscule

  • rappel : les noms de types, variables, fonctions commencent par une lettre minuscule
  • rappel : les noms de modules commencent par un majuscule (Random, Array ...)

• Un Constructeur n'est pas un fonction

Entier;; (* INCORRECT. ce n'est pas une fonction de type int -> nombre *)

File "[97]", line 1, characters 0-6:
1 | Entier;; (* INCORRECT. ce n'est pas une fonction de type int -> nombre *)
    ^^^^^^
Error: The constructor Entier expects 1 argument(s),
       but is applied here to 0 argument(s)

Exemple / Exercice 4 - suite

• Implémenter la fonction abs : nombre -> nombre qui renvoie la valeur absolue d'un nombre.

On devra obtenir :

Entier (-5) -> Entier (5)

Reel (1.0) -> Reel (1.0)

let abs x = ???

On veut tester x = Reel (t) ou x = Entier (n) ?? comment faire ???

L'opérateur de filtrage match

match expr with | p1 -> v1 | p2 -> v2 | ...

• expr est l'expression à filtrer
• p1, p2 sont des motifs (pattern)
• v1, v2 sont les valeurs calculées

C'est le premier motif qui s'apparie à expr (qui "matche") qui donne la valeur à renvoyer

L'opérateur de filtrage (pattern matching) match est un outil très puissant.

C'est une spécificité d'OCaml qui permet de :

• distinguer plusieurs cas
• déconstruire des valeurs Ocaml
• de manière très succincte

(* Exemple opérateur match *)
let abs x = match x with
  | Entier n -> if n < 0 then Entier (-n) else x
  | Reel t -> if t < 0. then Reel (-.t) else x

val abs : nombre -> nombre = <fun>

abs (Entier (-4));;

abs (Reel 1.);;

- : nombre = Entier 4

- : nombre = Reel 1.

Qu'est-ce qu'un motif ?

C'est une "valeur à trous".

Les identifiants (hors Constructeurs) qui apparaissent dans le motif définissent de nouvelles variables utilisables dans la valeur associée au motif.

(* Exemple opérateur match *)
let abs x = match x with
  | Entier n -> if n < 0 then Entier (-n) else x
  | Reel t -> if t < 0. then Reel (-.t) else x

val abs : nombre -> nombre = <fun>

• Si x vaut Entier (-4), le premier motif "matche" et la variable n:int est liée à -4

• Si x vaut Reel 1., le premier motif "ne matche pas", le second "matche" et la variable t:float est liée à 1.

Typage ?

match expr with | p1 -> v1 | p2 -> v2 | ...

• expr est l'expression à filtrer
• les motifs p1, p2 contraignent le type de expr
• les variables définies par le motif sont typées
• v1, v2 doivent être de mêmes types (c'est le type de l'expression complète)

Quelle différence entre ces deux versions ?

(* Version 1 *)
let abs x = match x with
  | Entier n -> if n < 0 then Entier (-n) else x
  | Reel t -> if t < 0. then Reel (-.t) else x

(* Version 2 *)
let abs x = match x with
  | Entier n -> if n < 0 then Entier (-n) else Entier n
  | Reel t -> if t < 0. then Reel (-.t) else Reel t

Dans la version 2, on construit systématiquement une nouvelle valeur

La version 1 est plus économe en mémoire

L'opérateur match peut s'appliquer à toute valeur OCaml

Exemple / Exercice 4 - suite

• Implémenter la fonction somme : nombre -> nombre -> nombre qui renvoie la somme de deux nombres.

On filtrera sur le couple des paramètres

let somme x y = match (x,y) with
  | (Entier n, Entier p) -> Entier (n + p)
  | ...

Le motif (Entier n, Entier p) matchera sur un couple d'Entiers et définit deux variables n et p de type int

| (Reel s, Reel t) -> ...

matchera sur un couple de Reels et définit deux variables s et t de type float

let somme x y = match (x,y) with  (* CODE INCORRECT *)
  | (Entier n, Entier p) -> Entier (n + p)
  | (Reel s, Reel t) -> Reel (s +. t)

File "[34]", line 1, characters 16-113:
1 | ................match (x,y) with
2 |   | (Entier n, Entier p) -> Entier (n + p)
3 |   | (Reel s, Reel t) -> Reel (s +. t)
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
((Reel _, Entier _)|(Entier _, Reel _))

val somme : nombre -> nombre -> nombre = <fun>

OCaml détecte que certains cas n'ont pas été envisagés (avertissement à la compilation)

somme (Entier 3) (Reel 1.5);; (** erreur à l'exécution **)

Exception: Match_failure ("[32]", 1, 16).
Called from file "toplevel/toploop.ml", line 208, characters 17-27

let somme x y = match (x,y) with (* CODE CORRECT *)
  | (Entier n, Entier p) -> Entier (n + p)
  | (Reel s, Reel t) -> Reel (s +. t)
  | (Entier n, Reel s) -> Reel (s +. float_of_int n)
  | (Reel s, Entier n) -> Reel (s +. float_of_int n)

val somme : nombre -> nombre -> nombre = <fun>

somme (Entier 3) (Reel 1.5);;

- : nombre = Reel 4.5

NB : les deux derniers cas sont très proches. On peut regrouper les deux derniers motifs.

let somme x y = match (x,y) with (* CODE CORRECT *)
  | (Entier n, Entier p) -> Entier (n + p)
  | (Reel s, Reel t) -> Reel (s +. t)
  | (Entier n, Reel s)  | (Reel s, Entier n) -> Reel (s +. float_of_int n)

val somme : nombre -> nombre -> nombre = <fun>

NB : attention à la cohérence des noms des variables définies par les deux derniers motifs

A suivre ...