La programmation fonctionnelle

La programmation fonctionnelle

Expressions et valeurs

types de base
- int (entiers relatifs: 3, -4; opérateurs: +, -, *, /, mod, ...)
- float (flottants: 0.5, 3.4E4, 4.3e-2; opérateurs: +., -., *., /., exp, log, sin, ...)
- bool (valeurs de vérité: true, false; opérateurs: && (« et »), || (« ou »), not (« non »); opérateurs de comparaison <, <=, >, >= produisent des résultats booléens et s'appliquent sur des entiers ou des flottants; opérateur d'égalité =)
- string (chaîne de caractères, portion de texte encadrée par des guillemets: "salut les copains", ""; opérations: ^ (concaténation, mise bout à bout de deux chaînes), etc.)

déclarations globales

On parle de déclaration, définition ou de liaison.

let ident = expression;;

#let s = 1 + 2 + 3;;
s : int = 6
#let s_carré = s * s;;
s_carré : int = 36
#s_carré;;
- : int = 36

#s_carré - rintintin;;
Entrée interactive:
>s_carré - rintintin;;
> ^^^^^^^^^
L'identificateur rintintin n'est pas 
défini.
#let s = 3 * 3;;
s : int = 9
#s_carré;;
- : int = 36
#let s = "pourquoi pas une chaine";;
s : string = "pourquoi pas une chaine"
#s^"!!!";;
- : string = "pourquoi pas une chaine!!!"

déclarations locales

let ident = expr1 in expr2;;

#let x = 5 * 5 in x + 2;;
- : int = 27
#x;;
Entrée interactive:
>x;;
>^
L'identificateur x n'est pas défini.
#let x = 3;;
x : int = 3
#let x = 5 * 5 in x + 2;;
- : int = 27
#x;;
- : int = 3
#(2*3+6) * (2*3+6) + 2 * (2*3+6) + 5;;
- : int = 173
#let a = 2*3+6 in a * a + 2 * a + 5;;
- : int = 173
#let z=3 in 
   let t=z+1 in z+t+1;;
- : int = 8

déclarations simultanées

globales

let ident1 = expr1
and ident2 = expr2;;

ou locales

let ident1 = expr1
and ident2 = expr2 in
expr;;

#let x = 1;;
x : int = 1
#let x = x+1 and y = x;;
x : int = 2
y : int = 1

expressions conditionnelles

if condition then expression1 else expression2
utilisation des parenthèses (priorités des opérateurs, levée d'ambiguité)

Fonctions

fonction d'une variable, définition, application

anonyme

  function paramètre -> 
  expression_du_corps_de_la_fonction;;

#function a -> if a < 0 then -a else a;;
- : int -> int = <fun>

nommée

let nom_de_la_fonction = 
  function paramètre ->
  expression_du_corps_de_la_fonction;;

let nom_de_la_fonction paramètre = 
  expression_du_corps_de_la_fonction;;

#let abs = function a -> 
   if a < 0 then -a else a;;
abs : int -> int = <fun>
#let abs a = if a < 0 then -a else a;;
abs : int -> int = <fun>
#let carré x = x * x;;
carré : int -> int = <fun>
#let polynôme x =
   let a = 2 
   and b = -3 
   and c = 5 in a * x * x + b * x + c;;
polynôme : int -> int = <fun>
#let répéter s = s ^ s;;
répéter : string -> string = <fun>
#let est_vide s = 
   s = "";;
est_vide : string -> bool = <fun>

appliquée

#carré 5;;
- : int = 25
#carré(5);;
- : int = 25
#carré (4 - 5);;
- : int = 1
#carré 4 - 5;; 
- : int = 11
#répéter "cou";;
- : string = "coucou"

fonctions à plusieurs arguments

let nom_de_la_fonction p1 ... pn = 
  expression_du_corps_de_la_fonction;;
let nom_de_la_fonction = 
  function p1 -> ... -> function pn -> 
  expression_du_corps_de_la_fonction;;

#let surface_rectangle long large = 
   long *. large;;
surface_rectangle : float -> float -> 
float = <fun>
#let surface_rectangle = 
   function long -> 
     function large -> long *. large;;
surface_rectangle : float -> float -> 
float = <fun>
#surface_rectangle 1.4 2.4;;
- : float = 3.36

portée statique

#let const=3;;
const : int = 3
#let f x = x*const;;
f : int -> int = <fun>
#f 1;;
- : int = 3
#let const=6;;
const : int = 6
#f 1;;
- : int = 3

type d'une fonction (t1 -> t2)

function x -> expr est de type t1 -> t2, si t1 est le type du paramètre formel x et t2 le type de l'expression expr.

#let identité x = x;;
identité : 'a -> 'a = <fun>
#identité 3;;
- : int = 3
#identité true;;
- : bool = true
#identité "une chaine";;
- : string = "une chaine"

identité est une fonction polymorphe.

restriction du domaine de définition d'une fonction

failwith "message d'erreur"

#let H x = 
   if x = 1 then failwith "H: indéfini" 
   else 1 / (x - 1);;
H : int -> int = <fun>
#let prédecesseur y = 
   if y <= 0 
   then failwith "paramètre non naturel" 
   else y - 1;; 
prédecesseur : int -> int = <fun>
#H 5;;
- : int = 0
#H 1;;
Exception non rattrapée: Failure "H: 
indéfini"
#prédecesseur 2;;
- : int = 1
#prédecesseur (-5);;
Exception non rattrapée: Failure 
"paramètre non naturel"
#carré (H (3-abs(2)));;
Exception non rattrapée: Failure "H: 
indéfini"
#failwith;;
- : string -> 'a = <fun>

Il existe aussi le mot-clé fun qui est équivalent à function dans les cas simples (un seul argument, etc.), mais diffère subtilement par ailleurs avec une sémantique plus floue. fun ne sera pas utilisé dans ce cours.

Fonctions récursives

syntaxe: let rec

exemples classiques: factorielle, suite de Fibonacci, pgcd d'entiers

#let fact n = 
   if n <= 0 then 1 else n*fact(n-1);;
fact : int -> int = <fun>
#let rec fact n = 
   if n <= 0 then 1 else n*fact(n-1);;
fact : int -> int = <fun>
#let rec fib n = 
   if n <= 1 then 1 
   else fib (n-1)+fib(n-2);;
fib : int -> int = <fun>
#let rec pgcd a b = 
   if b = 0 then abs a 
   else pgcd b (a mod b);;
pgcd : int -> int -> int = <fun>

un exemple de fonctions mutuellement récursives: pair et impair

#let rec pair n = 
   if n=0 then true else impair (n-1)
 and impair n = 
   if n=0 then false else pair (n-1);;
pair : int -> bool = <fun>
impair : int -> bool = <fun>
#impair 10;;
- : bool = false
#pair 10;;
- : bool = true
#impair 11;;
- : bool = true
#pair 11;;
- : bool = false

définition d'une fonction récursive:
- un ou plusieurs cas de base (calcul direct du résultat sans rappeler la fonction)
- cas récursifs qui se rapprochent à chaque itération des cas de base

Listes (début du filtrage)

un type de données prédéfini, qui n'utilise pas de pointeurs, avec une importante bibliothèque de fonctions prédéfinies!
Une liste est une suite (ordonnée) de valeurs de même nature de longueur non prédéfinie.
Syntaxe ([],[v1;...;vn]

Type Une liste de valeurs de type t est de type t list.

#[1; 2; 3];;
- : int list = [1; 2; 3]
#[true; 1 < 2];;
- : bool list = [true; true]
#[(function x -> x+2); succ; abs];;
- : (int -> int) list = [<fun>; <fun>; 
<fun>]
#[1; 2; "trois"];;
Entrée interactive:
>[1; 2; "trois"];;
>^^^^^^^^^^^^^^^
Cette expression est de type string list,
mais est utilisée avec le type int list.

#[[1; 2]; [2; 3; 4]; [9]];;
- : int list list = [[1; 2]; [2; 3; 4]; 
[9]]

La liste vide pourra être considérée comme une liste d'entiers, une liste de chaînes, une liste d'objets de type t pour tout type t selon le contexte d'utilisation.

#if (1>2) then [1] else [];;
- : int list = []
#[["a"; "b"]; []; ["c"]] ;;
- : string list list = [["a"; "b"]; []; 
["c"]]
#[];;
- : 'a list = []

L'opérateur ::

L'opérateur prédéfini noté :: se lit souvent cons (prononcer le s final). Il s'agit d'un opérateur infixe permettant de construire une nouvelle liste à partir d'une liste l et d'un élément x. L'expression x::l dénote la liste composée de l'élément x puis des éléments de l. Si l est de type t list, x doit être de type t.
```
#1::[2];;
- : int list = [1; 2]
#true::[2];;
Entrée interactive:
>true::[2];;
> ^^^
Cette expression est de type int list,
mais est utilisée avec le type bool list.
#1::(2::(3::[]));;
- : int list = [1; 2; 3]
```

Fonctions simples manipulant des listes

La fonction tête « si la liste l est vide alors le calcul échoue en affichant la chaîne de caractères "tête: liste vide", si la liste n'est pas vide alors appelons x son premier élément et l' la liste de ses autres éléments, la valeur de l'expression est alors x ».
```
#let tête l = match l with
 | [] -> failwith "tête: liste vide"
 | x::l' -> x;;
tête : 'a list -> 'a = <fun>
#tête [];;
Exception non rattrapée: Failure "tête: 
liste vide"
#tête [1; 2; 3];;
- : int = 1
```
La fonction tête est disponible en Caml sous le nom hd.

La fonction reste

#let reste l = match l with
 | [] -> failwith "reste: liste vide"
 | x::l' -> l';;
reste : 'a list -> 'a list = <fun>
#let reste l = match l with
 | [] -> failwith "reste: liste vide"
 | _::l' -> l';;
reste : 'a list -> 'a list = <fun>
#reste [];;
Exception non rattrapée: Failure "reste: 
liste vide"
#reste [1; 2; 3];;
- : int list = [2; 3]

La fonction reste est disponible en Caml sous le nom tl.

La fonction zéro_en_tête

#let zéro_en_tête l = match l with 
 | [] -> false
 | x::l' -> x=0;;
zéro_en_tête : int list -> bool = <fun>
#let zéro_en_tête l = match l with
 | 0::_ -> true
 | _ -> false;;
zéro_en_tête : int list -> bool = <fun>
#zéro_en_tête [];;
- : bool = false
#zéro_en_tête [1; 2; 3];;
- : bool = false
#zéro_en_tête [0; 1; 2; 3];;
- : bool = true
#let zéro_en_tête l = match l with
 | _ -> false
 | 0::_ -> true;;
Entrée interactive:
>| 0::_ -> true;;
> ^^^^
Attention: ce cas de filtrage est 
inutile.
zéro_en_tête : int list -> bool = <fun>
#zéro_en_tête [0; 1; 2; 3];;
- : bool = false

La fonction élément2

#let élément2 l = match l with 
 | x1::x2::l' -> x2
 | _ -> failwith "élément2: |liste| < 2";;
élément2 : 'a list -> 'a = <fun>
#let élément2 l = match l with
 | _::x2::_ -> x2
 | _ -> failwith "élément2: |liste| < 2";;
élément2 : 'a list -> 'a = <fun>
#élément2 [];;
Exception non rattrapée: Failure 
"élément2: |liste| < 2"
#élément2 [1];;
Exception non rattrapée: Failure 
"élément2: |liste| < 2"
#élément2 [1;2;3];;
- : int = 2
#let élément2 l = tête (reste l);;
élément2 : 'a list -> 'a = <fun>
#élément2 [];;
Exception non rattrapée: Failure "reste: 
liste vide"
#élément2 [1];;
Exception non rattrapée: Failure "tête: 
liste vide"
#élément2 [1;2;3];;
- : int = 2

Filtrage

On appelle filtrage ou analyse de cas une expression qui décrit un calcul selon la forme que prend une autre expression.

On appelle filtre ou motif la description de la forme attendue. Dans les exemples précédents, il s'agit par exemple de [], x::l, _, x::_, x1::x2::_. Le filtre permet non seulement de préciser la forme attendue mais aussi d'extraire et de nommer certaines parties d'une valeur. C'est en ce sens que le filtrage est une opération très puissante ; sans cet outil, le programmeur est amené à imbriquer moult if ... then ... else ... et à utiliser des fonctions auxiliaires pour accèder aux composantes de la valeur filtrée.

Un filtrage apparaît comme une suite de cas tous composés d'un filtre et d'une expression. Chaque cas est syntaxiquement noté

| filtre -> expression. Le premier « | » peut être omis. Donc un filtrage prend la forme syntaxique générale suivante
```
match exp with
| filtre₁ -> exp₁
...
| filtre_n -> exp_n
```
où exp, exp₁, ..., exp_n sont des expressions et filtre₁, ..., filtre_n sont des filtres.

exp₁, ..., exp_n doivent toutes avoir le même type et filtre₁, ..., filtre_n doivent tous être des filtres du type de exp. Il faut que tous les filtres recouvrent tous les cas possibles.
```
#let tête_imparfaite l = match l with
 | x::_ -> x;;
Entrée interactive:
>........................match l with
>| x::_ -> x..
Attention: ce filtrage n'est pas 
exhaustif.
tête_imparfaite : 'a list -> 'a = <fun>
#tête_imparfaite [1;2;3];;
- : int = 1
#tête_imparfaite [];;
Exception non rattrapée: Match_failure 
("", 4429, 4453)
```
Récapitulatif des filtres de listes

Dans la composition d'un filtre de listes, il peut entrer :
1. Les constantes (par exemple 0)
2. Les variables (par exemple x ou l dans les fonctions sur les listes)
3. Le signe _ comme cas par défaut ou pour éviter de nommer une variable qui n'apparaît pas dans le corps de ce cas
4. La liste vide []
5. Et enfin un filtre défini par le constructeur :: avec un élément que l'on peut lui-même filtrer et une liste que l'on peut filtrer elle aussi (filtre::filtre).
Attention, si l'identificateur x est défini, le filtre x::_ ne filtre pas les listes commençant par x, mais toutes les listes en nommant x son premier élément indépendamment de l'identificateur x préexistant et dans l'expression associée au filtre x correspond au premier élément de la liste filtrée. Si on veut filtrer les listes commençant par x, alors il faut écrire y::_ when y=x. Le when condition s'appelle la garde du filtre.

Fonctions récursives manipulant des listes

#let rec length l = match l with
 | [] -> 0
 | _::l' -> 1+(length l');;
length : 'a list -> int = <fun>
#length [1; 2; 3];;
- : int = 3

La fonction length est prédéfinie sous le nom de list_length en Caml.

#let rec member e l = match l with
 | [] -> false
 | x::l' -> 
   if e=x then true else member e l';;
member : 'a -> 'a list -> bool = <fun>
#let rec member e l = match l with
 | [] -> false
 | x::l' -> e=x || (member e l');;
member : 'a -> 'a list -> bool = <fun>
#let rec member e l = match l with
 | [] -> false
 | x::_ when x=e -> true 
 | _::l' -> member e l';;
member : 'a -> 'a list -> bool = <fun>
#member 0 [1; 2; 3];;
- : bool = false
#member 2 [1; 2; 3];;
- : bool = true
#member 2 [3; 2; 1];;
- : bool = true

La fonction member est prédéfinie sous le nom de mem en Caml.

#let rec member_sort e l = match l with
 | [] -> false
 | x::l' -> 
   e=x || (x<e && (member_sort e l'));;
member_sort : 'a -> 'a list -> bool = 
<fun>
#let rec member_sort e l = match l with
 | [] -> false
 | x::_ when x=e -> true
 | x::_ when x>e -> false
 | _::l' -> member_sort e l';;
member_sort : 'a -> 'a list -> bool = 
<fun>
#member_sort 0 [1; 2; 3];;
- : bool = false
#member_sort 2 [1; 2; 3];;
- : bool = true
#member_sort 2 [3; 2; 1];;
- : bool = false
#let rec dernier l = match l with
 | [] -> failwith "dernier: liste vide"
 | [x] -> x
 | _::l' -> dernier l';;
dernier : 'a list -> 'a = <fun>
#dernier [3; 2; 4; 5; 1];;
- : int = 1
#let rec max_list l = match l with
 | [] -> failwith "max_list: liste vide"
 | [x] -> x
 | x::l' -> max x (max_list l');;
max_list : 'a list -> 'a = <fun>
#max_list [3; 2; 4; 5; 1];;
- : int = 5

Fonctions récursives produisant des listes

On suppose que i < j et on écrit la liste des entiers compris entre i et j. Cette liste se décompose ainsi


[i; i+1; ...; j] º i::[i+1; ...; j]

#let rec intervalle i j = 
   if i = j then [i] 
   else i::(intervalle (i+1) j);;
intervalle : int -> int -> int list = 
<fun>
#intervalle 1 10;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 
10]

#let rec termes_pairs l = match l with
 | [] -> []
 | x::l' ->  
   if x mod 2 = 0 then x::(termes_pairs l') 
   else (termes_pairs l');;
termes_pairs : int list -> int list = 
<fun>
#let rec termes_pairs l = match l with
 | [] -> []
 | x::l' when x mod 2 = 0 -> 
   x::(termes_pairs l') 
 | _::l' -> (termes_pairs l');;
termes_pairs : int list -> int list = 
<fun>
#termes_pairs [1; 2; 3; 4; 5];;
- : int list = [2; 4]

#let rec remplace avant après l = 
 match l with
 | [] -> []
 | x::l' -> 
   if x = avant 
      then après::(remplace avant après l') 
   else x::(remplace avant après l');;
remplace : 'a -> 'a -> 'a list -> 'a list 
= <fun>
#let rec remplace avant après l = 
 match l with
 | [] -> []
 | x::l' when x=avant -> 
   après::(remplace avant après l') 
 | x::l' -> x::(remplace avant après l');;
remplace : 'a -> 'a -> 'a list -> 'a list 
= <fun>
#remplace 1 (-1) [1; 2; 1; 4; 100];;
- : int list = [-1; 2; -1; 4; 100]

#let rec append l1 l2 = match l1 with
 | [] -> l2
 | x::l'1 -> x::(append l'1 l2);; 
append : 'a list -> 'a list -> 'a list = 
<fun>
#append ["a"; "b"; "c"] ["d"; "ef"];;
- : string list = ["a"; "b"; "c"; "d"; 
"ef"]
#append [1; 2; 3] [];;
- : int list = [1; 2; 3]
#let l = [3; 4];;
l : int list = [3; 4]
#append l l;;
- : int list = [3; 4; 3; 4]
#l;;
- : int list = [3; 4]

Cette fonction est prédéfinie dans le système : (append l1 l2) s'écrit l1 @ l2 en utilisant la primitive de Caml Light.

Types produits

une représentation simple des données composées:
- une date est décrite par un jour, un mois et une année
- un rationnel se compose d'un numérateur et d'un dénominateur...
- on veut les représenter comme un tout (addition de deux rationnels, etc.)
- élément d'un produit cartésien

syntaxe et type: (x₁,x₂,...,x_n) est de type t₁*t₂*...*t_n où t_i est le type de x_i.

#let paire1 = (1, "toto");;
paire1 : int * string = 1, "toto"
#let paire2 = (succ, "une fonction");;
paire2 : (int -> int) * string = <fun>, 
"une fonction"
#(succ 5, let s = "ab" in s ^" "^s);;      
- : int * string = 6, "ab ab"

paramètres ou résultat de fonctions

#let axe_des_x n = (n, 0.0);;
axe_des_x : 'a -> 'a * float = <fun>
#axe_des_x 1.5;;
- : float * float = 1.5, 0.0
#let carré_norme v = match v with 
   | (x,y) -> x *. x +. y *. y;;
carré_norme : float * float -> float = 
<fun>
#carré_norme (2.0, 3.0);;
- : float = 13.0
#let carré_norme (x,y) = x *. x +. y *. y;;
carré_norme : float * float -> float = 
<fun>
#let PS (x,y) (x',y') = x *. x' +. y *. y';;
PS : float * float -> float * float -> 
float = <fun>
#let proj1 (x,y) = x;;
proj1 : 'a * 'b -> 'a = <fun>
#proj1 (2,3);;
- : int = 2
#proj1 ("toto", true);;
- : string = "toto"
#proj1 ((3,4), 5);;
- : int * int = 3, 4
#proj1 (proj1 ((3,4), 5));;
- : int = 3

Un exemple de fonction récursive retournant une paire

#let rec div a b = 
   if b=0 then failwith "diviseur nul" else 
   if a<b then (0,a) else 
   match div (a-b) b with 
   | (q,r) -> (q+1,r);;
div : int -> int -> int * int = <fun>
#let rec div a b = 
   if b=0 then failwith "diviseur nul" else 
   if a<b then (0,a) else 
   let (q,r) = div (a-b) b in (q+1,r);;
div : int -> int -> int * int = <fun>

let déstructurant.

Les n-uplets

#let carré_norme (x, y, z) = 
   x *. x +. y *. y +. z *. z;;
carré_norme : float * float * float -> 
float = <fun>
#let proj1 (x, y, z) = x;;
proj1 : 'a * 'b * 'c -> 'a = <fun>

fonction à n arguments versus fonction à un argument n-uplet
```
#let min n m = if n < m then n else m;;
min : 'a -> 'a -> 'a = <fun>
#let min (n, m) = if n < m then n else m;;
min : 'a * 'a -> 'a = <fun>
```
- n-uplets plus naturels en mathématiques
- fonction à plusieurs arguments traditionnelle en programmation fonctionnelle
- utilisation de la forme la plus naturelle ou appropriée au problème.

Types enregistrements

les premiers types à déclarer, une syntaxe proche de Pascal et de C

déclaration du type

type nom_du_type = 
  { étiquette_1:type_de_étiquette_1;
    étiquette_2:type_de_étiquette_2;
                 :
    étiquette_n:type_de_étiquette_n
  };;

déclaration d'un élément de ce type

let nom_de_variable = 
  { étiquette_1 = valeur_de_étiquette_1;
    étiquette_2 = valeur_de_étiquette_2;
                  :
    étiquette_n = valeur_de_étiquette_n
  };;

Les étiquettes doivent être toutes différentes.

exemple

#type date = 
   {Jour: int; Mois: int; Année: int};;
Le type date est défini.
#let Noël_99 = 
   {Jour=25; Mois=12; Année=1999};;
Noël_99 : date = {Jour = 25; Mois = 12; 
Année = 1999}
#let Noël_99_bis = 
   {Année=1999; Mois=12; Jour=25};;
Noël_99_bis : date = {Jour = 25; Mois = 
12; Année = 1999}
#Noël_99 = Noël_99_bis;;
- : bool = true
#Noël_99.Mois;;
- : int = 12
#let est_Noël d = 
   d.Jour = 25 && d.Mois = 12;;
est_Noël : date -> bool = <fun>

avec du filtrage

#let est_Noël date = match date with
   | {Jour=j; Mois=m; Année=a} -> 
       j=25 && m=12;;
est_Noël : date -> bool = <fun>
#let est_Noël date = 
   match date with 
   | {Jour=25; Mois=12; Année=a} -> true
   | _ -> false;;
est_Noël : date -> bool = <fun>
#let est_Noel date = 
   match date with 
   | {Jour=25; Mois=12; _} -> true
   | _ -> false;;
est_Noel : date -> bool = <fun>

Attention si on utilise la même étiquette dans un autre type enregistrement, alors on ne peut plus construire de nouvel élément du premier type.

#type an = {Année: int};;
Le type an est défini.
#let Noël_99 = 
   {Jour=25; Mois=12; Année=1999};;
Entrée interactive:
> {Jour=25; Mois=12; Année=1999};;
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L'étiquette Année n'appartient pas au type 
date.
#est_Noel Noël_99_bis;;
- : bool = true

Types sommes

une notion nouvelle: comment réunir des choux et des carottes en disant proprement que ce sont tous des légumes !
il s'agit d'union disjointe d'ensembles

déclaration

    type nom_du_type = 
    | Constructeur_1 [oftype_1]
    | Constructeur_2 [oftype_2]
                    :
    | Constructeur_n [oftype_n];;

of type_i optionnel (constructeur constant).

Les constructeurs doivent être tous différents.

exemples

#type saison = 
   Printemps | Été | Automne | Hiver;;
Le type saison est défini.
#type boîte = 
 | Cube of float 
 | Parallélépipède of float*float*float;;
Le type boîte est défini.
#Automne;;
- : saison = Automne
#Cube;;
- : float -> boîte = <fun>
#Cube 2.5;;
- : boîte = Cube 2.5

filtrage

#let est_cube b = match b with
 | Cube c -> true
 | Parallélépipède (p1,p2,p3) -> false;;
est_cube : boîte -> bool = <fun>
#let est_cube b = match b with
 | Cube _ -> true
 | Parallélépipède _ -> false;;
est_cube : boîte -> bool = <fun>
#let est_cube b = match b with
 | Cube _ -> true
 | _ -> false;;
est_cube : boîte -> bool = <fun>
#let est_printemps s = match s with
 | Printemps -> true
 | Été -> false
 | Automne -> false
 | Hiver -> false;;
est_printemps : saison -> bool = <fun>
#let est_printemps s = match s with
 | Printemps -> true
 | _ -> false;;
est_printemps : saison -> bool = <fun>
#let plus_grande_arête b = match b with
 | Cube c -> c
 | Parallélépipède (p1,p2,p3) -> 
     max (max p1 p2) p3;;
plus_grande_arête : boîte -> float = 
<fun>

De même que pour les types enregistrements, si on utilise le nom d'un constructeur dans la définition d'un autre type somme, alors on ne peut plus créer d'élément de l'ancien type somme avec ce constructeur-là.

#type type1 = Titi11 | Titi12 of int;;
Le type type1 est défini.
#type type2 = Titi21 | Titi12 of string;;
Le type type2 est défini.
#type type3 = Titi11 | Titi32 of float;;
Le type type3 est défini.
#Titi11;;
- : type3 = Titi11
#Titi12;;
- : string -> type2 = <fun>

Types récursifs

un type est récursif si sa définition contient au moins une occurrence de son nom.
La notion de type récursif apparaît naturellement à la suite du chapitre sur les types sommes car un type récursif se définit à l'aide d'un type somme.

De même que la définition d'une fonction récursive contient au moins un cas non récursif que l'on a appelé cas de base) pour assurer la terminaison, il faut que la définition d'un type récursif contienne au moins un constructeur non récursif.

Par exemple:
```
#type type_vide = C of type_vide;;
Le type type_vide est défini.
```
est une déclaration de type valide en Caml, mais il est impossible de construire aucune valeur de ce type.

exemples

Phrases (listes)

#type phrase = 
 | Point | Phrase of string * phrase;;
Le type phrase est défini.
#let sous_chaine s i = 
   sub_string s i (string_length s-i);;
sous_chaine : string -> int -> string = 
<fun>
#let rec char_in_string c s = 
   not (s="") && 
   (c=s.[0] || 
    char_in_string c (sous_chaine s 1));;
char_in_string : char -> string -> bool = 
<fun>
#let rec search c s = 
   if c=s.[0] then 0 
   else 1+(search c (sous_chaine s 1));;
search : char -> string -> int = <fun>
#let rec coupe s =
   if char_in_string ` ` s then 
     let i = search ` ` s in
     Phrase (sub_string s 0 i, 
             coupe (sous_chaine s (i+1)))
   else 
     Phrase (
       sub_string s 0 (string_length s-1), 
       Point);;
coupe : string -> phrase = <fun>

#coupe "Une phrase se découpe en mots.";;
- : phrase =
 Phrase
 ("Une",
 Phrase
 ("phrase",
 Phrase ("se", Phrase ("découpe", 
Phrase ("en", Phrase ("mots", Point))))))

On peut comparer le type phrase au type string list où la liste vide serait dénotée Point.

Arbres binaires de recherche à coefficients entiers

Tous les éléments présents dans le sous-arbre droit sad d'un noeud Noeud(elem, sag, sad) sont supérieurs à elem et tous ceux présents dans le sous-arbre gauche sag sont inférieurs à elem.

#type abr = 
 | Vide 
 | Noeud of int * abr * abr;;
Le type abr est défini.
#let mon_arbre = 
   Noeud (10, 
          Noeud (5, 
                 Noeud (2,Vide, Vide), 
                 Noeud (8, Vide, Vide)),
          Noeud (30, 
                 Vide, 
                 Noeud (40, Vide, Vide)));;
mon_arbre : abr =
 Noeud
 (10, Noeud (5, Noeud (2, Vide, Vide), 
Noeud (8, Vide, Vide)),
 Noeud (30, Vide, Noeud (40, Vide, 
Vide)))

#let rec member élém = function 
 | Vide -> false
 | Noeud (e, _, _) when e = élém -> true
 | Noeud (e, sag, _) when élém < e -> 
   member élém sag 
 | Noeud (e, _, sad) -> member élém sad;;
member : int -> abr -> bool = <fun>
#member 2 mon_arbre;;
- : bool = true

Expressions arithmétiques (arbres de syntaxe abstraite)

#type exp = 
 | V of string | C of int 
 | P of exp * exp;;
Le type exp est défini.
#let mon_exp = P (V "x", P (V "y", C 3));;
mon_exp : exp = P (V "x", P (V "y", C 3))
#let rec deriv = function s -> function
 | V nom -> 
   if s = nom then C 1 else C 0
 | C _ -> C 0
 | P (e1, e2) -> 
   P (deriv s e1, deriv s e2);;
deriv : string -> exp -> exp = <fun>
#deriv "x" mon_exp;;
- : exp = P (C 1, P (C 0, C 0))

Un peu d'ordre supérieur

Exemples simples

#let pente_en_0 f = (f(0.01)-.f(0.))/.0.01;;
pente_en_0 : (float -> float) -> float = 
<fun>
#let dérivée f = function x -> 
   (f(x+.0.001)-.f(x))/.0.001;;
dérivée : (float -> float) -> float -> 
float = <fun>
#let compose f g = function x -> g (f x);;
compose : ('a -> 'b) -> ('b -> 'c) -> 'a 
-> 'c = <fun>

Itérateurs

Calcul du n-ième terme d'une suite définie récursivement

ì
í
î

u₀	=	a,
u_n+1	=	f(u_n)

#let rec iter n f a =
   if n = 0 then a else f (iter (n-1) f a);;
iter : int -> ('a -> 'a) -> 'a -> 'a = 
<fun>
#let puissance p n = 
   iter n (function x -> p*x) 1;;
puissance : int -> int -> int = <fun>
#puissance 2 15;;
- : int = 32768

Fonction sigma

#let rec somme n = 
   if n = 0 then 0 else n+(somme (n-1));;
somme : int -> int = <fun>
#let rec somme_carrés n = 
   if n = 0 then 0 
   else (n*n)+(somme_carrés (n-1));;
somme_carrés : int -> int = <fun>
#let rec sigma f n = 
   if n = 0 then 0 
   else f (n)+(sigma f (n-1));;
sigma : (int -> int) -> int -> int = 
<fun>
#let somme n = sigma (function n -> n) n;;
somme : int -> int = <fun>
#let somme_carrés n = 
   sigma (function n -> n*n) n;;
somme_carrés : int -> int = <fun>

Fonction map

#let rec noms_étudiants liste_étudiants = 
   match liste_étudiants with
   | [] -> []
   | (nom, notes)::l -> 
     nom::(noms_étudiants l);;
noms_étudiants : ('a * 'b) list -> 'a list 
= <fun>
#let rec map f liste = 
   match liste with
   | [] -> []
   | x::l -> (f x)::(map f l);;
map : ('a -> 'b) -> 'a list -> 'b list = 
<fun>
#map (function x -> x*x) [1; 2; 3; 4; 5; 6];;
- : int list = [1; 4; 9; 16; 25; 36]
#let noms_étudiants l =
   map (function (nom, note) -> nom) l;;
noms_étudiants : ('a * 'b) list -> 'a list 
= <fun>

Cette fonctionnelle map est prédéfinie en Caml.

Algorithmes paramétrés par un prédicat

Fonction filter

#let rec filter p l = match l with
 | [] -> []
 | x::l' -> 
   if (p x) then x::(filter p l') 
   else (filter p l');;
filter : ('a -> bool) -> 'a list -> 'a 
list = <fun>
#let termes_pairs l = 
   filter (function x -> (x mod 2 = 0)) l;;
termes_pairs : int list -> int list = 
<fun>
#let est_sur_axe_x (x,y) = y=0.0;;
est_sur_axe_x : 'a * float -> bool = 
<fun>
#let vecteurs_axe_x l = 
   filter est_sur_axe_x l;;
vecteurs_axe_x : ('a * float) list -> ('a 
* float) list = <fun>

Insertion, tri

#let rec insérer e l = match l with
 | [] -> [e]
 | x::l' -> 
   if e < x then e::l 
   else x::(insérer e l');;
insérer : 'a -> 'a list -> 'a list = 
<fun>
#let rec insérer priorité e l = 
   match l with
   | [] -> [e]
   | x::l' -> 
     if priorité x e 
        then x::(insérer priorité e l') 
     else e::l;;
insérer : ('a -> 'a -> bool) -> 'a -> 'a 
list -> 'a list = <fun>
#let insérer_ordre_croissant e l = 
   insérer (prefix <) e l;;
insérer_ordre_croissant : 'a -> 'a list -> 
'a list = <fun>
#let insérer_ordre_décroissant e l = 
   insérer (prefix >) e l;;
insérer_ordre_décroissant : 'a -> 'a list 
-> 'a list = <fun>
#let rec tri_insertion priorité liste = 
   match liste with 
   | [] -> [] 
   | e::l -> 
     insérer priorité e 
             (tri_insertion priorité l);;
tri_insertion : ('a -> 'a -> bool) -> 'a 
list -> 'a list = <fun>
#let tri_insertion_ordre_croissant l = 
   tri_insertion (prefix <) l;;
tri_insertion_ordre_croissant : 'a list -> 
'a list = <fun>