Diaporama n°15¶

Le langage OCaml - Type Somme, et opérateur match¶

Rappel¶

  • type somme : représenter plusieurs cas disjoints

  • opérateur de filtrage match

I. Type somme¶

type nom = Cons1 of t1 | Cons2 of t2 | Cons3 of t3...

  • Les Constructeurs doivent tous être différents, (et commencer par une majuscule).

  • Les Constructeurs peuvent être Constants (pas de of ... dans ce cas)

  • t1, t2 ... peuvent être des types quelconques (produit, enregistrement, tableau ...)

  • .. et même faire référence au type nom entrain d'être défini (type somme récursif)

  • Possiblité de type polymorphe type 'a nom = ...

Type somme avec constructeurs constants¶

Exercice 1 :¶

  • Définir un type nombre_etendu avec les entiers, les réels, $+\infty$ et $-\infty$
In [2]:
type nombre_etendu = Reel of float | Entier of int | PlusInf | MoinsInf
Out[2]:
type nombre_etendu = Reel of float | Entier of int | PlusInf | MoinsInf
  • Définir un type signe pour représenter les informations Positif, Negatif, Nul
In [4]:
type signe = Positif | Negatif | Nul
Out[4]:
type signe = Positif | Negatif | Nul

Exercice 1 - suite :¶

  • Définir une fonction signe_of_int:int->signe
In [5]:
let signe_of_int x = 
    if x = 0 then Nul 
    else if x > 0 then Positif
    else Negatif
Out[5]:
val signe_of_int : int -> signe = <fun>
  • Définir une fonction signe_of_float:float->signe
In [6]:
let signe_of_float x = 
    if x = 0. then Nul 
    else if x > 0. then Positif
    else Negatif
Out[6]:
val signe_of_float : float -> signe = <fun>

Exercice 1 - suite :¶

  • Définir une fonction signe_of_nombre_etendu:nombre_etendu->signe
In [7]:
let signe_of_nombre_etendu x = match x with
    | Reel t -> signe_of_float t
    | Entier n -> signe_of_int n
    | PlusInf -> Positif 
    | MoinsInf -> Negatif
Out[7]:
val signe_of_nombre_etendu : nombre_etendu -> signe = <fun>

Exercice 2 :¶

  • Comment coder les cartes d'un jeu de 32 cartes ?
  • Le plus "rustique" : une carte = un int entre 0 et 31
  • carte mod 4 : la couleur de la carte (0 pour Pique, 1 pour Coeur, 2 pour Carreau, 3 pour Trèfle)
  • carte / 4 : la hauteur de la carte (0 pour 7, 1 pour 8 ..., 7 pour Roi, 8 pour As)

ex : $13 = 3\times4 + 1$ : 10 de Coeur

  • Un peu plus "structuré" : une carte = un couple d'int :
  • première composante : entre 0 et 3 pour la couleur
  • deuxième composante : entre 0 et 7 pour la hauteur

ex : (2,1) : 8 de Carreau

  • En exploitant au maximum les possibilités des types OCaml
In [ ]:
type couleur = Pique | Coeur | Carreau | Trefle (* plusieurs cas : type somme *)
In [ ]:
type hauteur = As | Roi | Dame | Valet | Petite of int (* plusieurs cas : type somme *)
In [8]:
type carte = { h : hauteur; c : couleur } (* plusieurs informations : type enregistrement *)
Out[8]:
type couleur = Pique | Coeur | Carreau | Trefle
Out[8]:
type hauteur = As | Roi | Dame | Valet | Petite of int
Out[8]:
type carte = { h : hauteur; c : couleur; }
  • Définir le Roi de Trèfle et le 7 de Carreau
In [11]:
let c1 = {h = Roi; c = Trefle}
let c2 = {h = Petite(7); c = Carreau}
Out[11]:
val c1 : carte = {h = Roi; c = Trefle}
Out[11]:
val c2 : carte = {h = Petite 7; c = Carreau}

Exercice 2 - suite :¶

  • Comment coder un jeu de Tarot ?
    • L'excuse
    • 21 atouts de 1 à 21
    • 56 cartes (jeu classique + cavalier)
In [13]:
type couleur = Pique | Coeur | Carreau | Trefle (* plusieurs cas : type somme *)

type hauteur = Roi | Dame | Cavalier | Valet | Petite of int (* plusieurs cas : type somme *)

type carte_tarot = Classique of { h : hauteur; c : couleur } | Atout of int | Excuse

let c1 = Excuse
let c2 = Atout 21
let c3 = Classique { h = Roi; c = Trefle }
Out[13]:
type couleur = Pique | Coeur | Carreau | Trefle
Out[13]:
type hauteur = Roi | Dame | Cavalier | Valet | Petite of int
Out[13]:
type carte_tarot =
    Classique of { h : hauteur; c : couleur; }
  | Atout of int
  | Excuse
Out[13]:
val c1 : carte_tarot = Excuse
Out[13]:
val c2 : carte_tarot = Atout 21
Out[13]:
val c3 : carte_tarot = Classique {h = Roi; c = Trefle}

Type somme récursif¶

Exercice 3¶

  • Définir un type iliste qui soit la liste vide, ou un maillon constitué d'un entier et d'une liste d'entier
In [1]:
type iliste = Vide | Maillon of int * iliste
Out[1]:
type iliste = Vide | Maillon of int * iliste
In [2]:
let l1 = Vide
let l2 = Maillon (3, Maillon (4, Vide))
Out[2]:
val l1 : iliste = Vide
Out[2]:
val l2 : iliste = Maillon (3, Maillon (4, Vide))
  • Définir la fonction affiche:iliste -> unit
In [3]:
let rec affiche l = match l with
  | Vide -> ()
  | Maillon (x, t) -> print_int x; print_string " "; affiche t
Out[3]:
val affiche : iliste -> unit = <fun>
In [4]:
affiche l2; print_newline ()

3 4
Out[4]:
- : unit = ()
  • Affichage avec des crochets ?
In [5]:
let affiche l = 
 let rec affiche_aux l = match l with
  | Vide -> ()
  | Maillon (x, t) -> print_int x; print_string ";"; affiche_aux t
 in print_string "["; affiche_aux l; print_string "]"
Out[5]:
val affiche : iliste -> unit = <fun>
In [6]:
affiche l2; print_newline ()

[3;4;]
Out[6]:
- : unit = ()
  • Affichage sans ; en trop ?
  • Quel motif "capture" le dernier maillon de la liste ?
  • Où le placer par rapport aux autres motifs ?
In [7]:
let affiche l = 
 let rec affiche_aux l = match l with
  | Vide -> ()
  | Maillon (x, Vide) -> print_int x
  | Maillon (x, t) -> print_int x; print_string ";"; affiche_aux t
 in print_string "["; affiche_aux l; print_string "]"
Out[7]:
val affiche : iliste -> unit = <fun>
In [8]:
affiche l2; print_newline ()

[3;4]
Out[8]:
- : unit = ()

Type somme polymorphe¶

Exercice 4¶

Le type 'a option est défini en OCaml comme un type somme. Il permet d'envisager deux cas : l'absence de valeur avec le constructeur constant None, ou la présence de valeur avec le constructeur Some

  • Donner la définition du type 'a option
In [37]:
type 'a option = None | Some of 'a
Out[37]:
type 'a option = None | Some of 'a
  • Définir une fonction last_elt:'a array->'a option qui renvoie le dernier élément d'un tableau s'il existe
  • None si le tableau est de longueur 0
  • Some x avec x dernier élément si le tableau est de longueur $> 0$
In [39]:
let last_elt tab =
    if Array.length tab = 0 then None
    else Some tab.(Array.length tab-1)
Out[39]:
val last_elt : 'a array -> 'a option = <fun>
In [41]:
last_elt [||];;
last_elt [|5.2; 4.3; -2.1|];;
Out[41]:
- : 'a option = None
Out[41]:
- : float option = Some (-2.1)

Exercice 5¶

  • Définir un type 'a liste qui soit la liste vide, ou un maillon constitué d'un élément de type 'a et d'une 'a liste
In [33]:
type 'a liste = Vide | Maillon of 'a * 'a liste
Out[33]:
type 'a liste = Vide | Maillon of 'a * 'a liste

NB : c'est une type somme récursif polymorphe

  • Définir une liste de 3 entiers, une liste de 2 chaînes de caractères
In [34]:
let l3 = Maillon (2, Maillon (5, Maillon (7, Vide)))
let l4 = Maillon ("écureuil", Maillon ("oiseau", Vide))
Out[34]:
val l3 : int liste = Maillon (2, Maillon (5, Maillon (7, Vide)))
Out[34]:
val l4 : string liste = Maillon ("écureuil", Maillon ("oiseau", Vide))
  • Ecrire la fonction (récursive) longueur:'a liste->int
  • si la liste est vide : 0
  • si la liste n'est pas vide : ...
In [43]:
let rec longueur l = match l with
  | Vide -> 0
  | Maillon (x, t) -> 1 + longueur t;;
  
longueur l3;;
longueur l4;;
Out[43]:
val longueur : 'a liste -> int = <fun>
Out[43]:
- : int = 3
Out[43]:
- : int = 2

A SAVOIR : les Listes en OCaml¶

Le type 'a list existe déjà en OCaml, et est très utilisé.

Il est défini comme un type somme :

  • [] est le Constructeur constant correspondant à la liste vide

  • :: est le Constructeur maillon sous forme d'opérateur infixe :

    • x :: l correspond à la liste dont l'élément de tête est x, suivi de la liste l

(cf TP à venir sur les listes OCaml)

II. L'opérateur de filtrage match¶

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

  • expr est l'expression à filtrer
  • p1, p2 sont des motifs (pattern) qui contraignent le type de expr
  • v1, v2 sont les valeurs calculées (elles doivent être de même type)

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

NB

  • match est un opérateur très général, qui peut s'appliquer à tout type de valeur OCaml :

    • valeur construite, le plus souvent

    • mais aussi : entier, couple, tableau, liste, enregistrement ...

  • Les constantes, Constructeurs, crochets, accolades ... sont autant de contraintes qui définissent le motif

  • Les identifiants présents dans le motif définissent de nouvelles variables

  • Le symbole _ désigne une valeur quelconque et ne définit pas de nouvelle variable

  • OCaml est capable de détecter que le filtrage n'est pas exhaustif (cas oubliés)

Exemple : filtrage sur un int et motif _¶

In [60]:
let vaut_un x = match x with
| 1 -> true
| _ -> false;;

vaut_un 3;;
vaut_un 1;;
Out[60]:
val vaut_un : int -> bool = <fun>
Out[60]:
- : bool = false
Out[60]:
- : bool = true

NB : ne pas abuser du filtrage ... surtout quand une expression conditionnelle ou booléenne suffit

In [58]:
let vaut_un x = x = 1
Out[58]:
val vaut_un : int -> bool = <fun>

NB : Détection de cas oubliés

In [70]:
let vaut_un x = match x with
| 1 -> true

File "[70]", line 1, characters 16-40:
1 | ................match x with
2 | | 1 -> true
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
0
Out[70]:
val vaut_un : int -> bool = <fun>

Exercice 6¶

  • Définir la fonction récursive fibo:int->int avec l'opérateur match
In [56]:
let rec fibo n = match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> fibo (n-1) + fibo (n-2);;

fibo 12;;
Out[56]:
val fibo : int -> int = <fun>
Out[56]:
- : int = 144

Attention à bien comprendre ce que font les motifs ...¶

  • Que dire du motif _ ?

il "matche" sur n'importe quelle valeur et ne définit aucune variable

  • Que dire du motif x ?

il "matche" sur n'importe quelle valeur, et définit une variable x liée à cette valeur

  • Que dire du motif y ?

il "matche" sur n'importe quelle valeur, et définit une variable y liée à cette valeur

  • Que dire du motif (x,y) ou x,y ?

il "matche" sur n'importe quel couple, et définit une variable x liée à la première valeur du couple, et une variable y liée à la deuxième valeur du couple

  • Que dire du motif (x,x) ou x,x ?

ce motif est incorrect : il définit deux fois une variable de même nom

Que dire des choix de motifs suivants ?¶

In [56]:
let rec fibo n = match n with
  | 0 -> 0
  | 1 -> 1
  | x -> fibo (n-1) + fibo (n-2);; (* bof...*)

fibo 12;;
Out[56]:
val fibo : int -> int = <fun>
Out[56]:
- : int = 144

La variable x n'est pas utilisée

Que dire des choix de motifs suivants ?¶

In [68]:
let rec fibo n = match n with
  | 0 -> 0
  | 1 -> 1
  | m -> fibo (m-1) + fibo (m-2);; (* bof...*)

fibo 12;;
Out[68]:
val fibo : int -> int = <fun>
Out[68]:
- : int = 144

La variable m prend la valeur de n

Que dire des choix de motifs suivants ?¶

In [68]:
let rec fibo n = match n with
  | 0 -> 0
  | 1 -> 1
  | n -> fibo (n-1) + fibo (n-2);; (* bof...*)

fibo 12;;
Out[68]:
val fibo : int -> int = <fun>
Out[68]:
- : int = 144

La nouvelle variable n prend la valeur de l'ancienne variable n

La meilleure solution :

In [56]:
let rec fibo n = match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> fibo (n-1) + fibo (n-2);; (* bien ! *)

fibo 12;;
Out[56]:
val fibo : int -> int = <fun>
Out[56]:
- : int = 144

Motifs rassemblés¶

Lorsque c'est pertinent, plusieurs motifs peuvent être regroupés. Ils doivent définir les mêmes variables

| p1 | p2 -> v

In [63]:
type nombre = Entier of int | Reel of float

let somme n1 n2 = match (n1, n2) with
| (Entier n, Entier p) -> Entier (n+p)
| (Reel s, Reel t) -> Reel (s+.t)
| (Reel s, Entier p) | (Entier p, Reel s) -> Reel (s +. float_of_int p)  (* motifs rassemblés *)
Out[63]:
type nombre = Entier of int | Reel of float
Out[63]:
val somme : nombre -> nombre -> nombre = <fun>

Motif "gardé"¶

  • | p when condition -> ...

si le motif "matche" et que la condition est vérifiée

Exercice 7¶

  • Définir la fonction abs:nombre_etendu->nombre_etendu en utilisant des motifs gardés`
In [62]:
let abs x = match x with
  | Entier n when n < 0 -> Entier (-n) (* motif gardé *)
  | Reel t when t < 0. -> Reel (-.t) (* motif gardé *)
  | _ -> x
Out[62]:
val abs : nombre -> nombre = <fun>

Opération de filtrage avec function¶

Il est possible de noter plus succinctement une fonction qui filtre son dernier paramètre, avec le mot clé function

NB : uniquement lorsqu'on a une bonne maîtrise de tout le langage OCaml

In [66]:
let abs = function
  | Entier n when n < 0 -> Entier (-n)
  | Reel t when t < 0. -> Reel (-.t)
  | x -> x
Out[66]:
val abs : nombre -> nombre = <fun>

Fin de la découverte OCaml ...¶