Les différents types de bibliothèques

Les différents types de bibliothèques

La core library: modules importés par défaut. Par exemple, le module string

#string_length;;
- : string -> int = <fun>
##close "string";;
#string_length;;
Entrée interactive:
>string_length;;
>^^^^^^^^^^^^^
L'identificateur string_length n'est pas 
défini.
##open "string";;

La standard library: modules à importer. Par exemple, le module sys ou random:

#random__init;;
- : int -> unit = <fun>
#random__int;;
- : int -> int = <fun>
##open "random";;
#init;;
- : int -> unit = <fun>

Les autres bibliothèques (graphics, unix, num, str): modules à importer dans un toplevel spécial pour que ces modules soient linkés avec le reste de Caml. Par exemple pour la bibliothèque graphique :

Unix: $ camllight camlgraph
>       Caml Light version 0.74

##open "graphics";;
#open_graph "";;     
- : unit = ()
#draw_circle 200 200 50;;   
- : unit = ()
#close_graph ();;
- : unit = ()
##close "graphics";;
#open_graph "";;     
Entrée interactive:
>open_graph "";;     
>^^^^^^^^^^
L'identificateur open_graph n'est pas défini.

à comparer avec

Unix: $ camllight
>       Caml Light version 0.74

##open "graphics";;
#open_graph "";;     
La valeur globale graphics__open_graph est 
utilisée avant d'être définie.
Veuillez charger une implémentation du 
module graphics.

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é = function x -> x * x;;
carré : int -> int = <fun>

#let polynôme = function 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 = function s -> s ^ s;;
répéter : string -> string = <fun>
#let est_vide = function 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 = function 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é = function x -> x;;
identité : 'a -> 'a = <fun>
#identité 3;;
- : int = 3
#identité true;;
- : bool = true
#identité "une chaîne";;
- : string = "une chaîne"

identité est une fonction polymorphe.

restriction du domaine de définition d'une fonction

failwith "message d'erreur"

#let H = function x ->
   if x = 1 then failwith "H: indéfini" 
   else 1 / (x - 1);;
H : int -> int = <fun>
#let prédécesseur = function y ->
   if y <= 0 
   then failwith "paramètre non naturel" 
   else y - 1;; 
prédécesseur : int -> int = <fun>
#H 5;;
- : int = 0
#H 1;;
Exception non rattrapée: Failure "H: 
indéfini"
#prédécesseur 2;;
- : int = 1

#prédécesseur (-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 = function n ->
   if n <= 0 then 1 else n*fact(n-1);;
Entrée interactive:
>  if n <= 0 then 1 else n*fact(n-1);;
>                          ^^^^
L'identificateur fact n'est pas défini.
#let rec fact = function n -> 
   if n <= 0 then 1 else n*fact(n-1);;
fact : int -> int = <fun>
#let rec fib = function n -> 
   if n <= 1 then 1 
   else fib (n-1)+fib(n-2);;
fib : int -> int = <fun>
#let rec pgcd = function a -> function 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 = function n ->
   if n=0 then true else impair (n-1)
 and impair = function 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 = function 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 = function l ->
 match l with
 | [] -> failwith "reste: liste vide"
 | x::l' -> l';;
reste : 'a list -> 'a list = <fun>
#let reste = function 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 = function l ->
 match l with 
 | [] -> false
 | x::l' -> x=0;;
zéro_en_tête : int list -> bool = <fun>
#let zéro_en_tête = function 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 = function 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 = function l ->
 match l with 
 | x1::x2::l' -> x2
 | _ -> failwith "élément2: |liste| < 2";;
élément2 : 'a list -> 'a = <fun>
#let élément2 = function 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 = function 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.

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 = function 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 
("", 3349, 3373)

Récapitulatif des filtres de listes

Dans la composition d'un filtre de listes, il peut entrer :

Les constantes (par exemple 0)
Les identificateurs (par exemple x ou l dans les fonctions sur les listes)
Le signe _ comme cas par défaut ou pour éviter de nommer un identificateur qui n'apparaît pas dans le corps de ce cas
La liste vide []
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

Longueur d'une liste

#let rec length = function 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 comme list_length.

Recherche d'un élément dans une liste

#let rec member = function e -> function 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 = function e -> function l ->
 match l with
 | [] -> false
 | x::l' -> e=x || (member e l');;
member : 'a -> 'a list -> bool = <fun>

#let rec member = function e -> function 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.

Recherche d'un élément dans une liste ordonnée

#let rec member_sort = 
   function e -> function 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 = 
   function e -> function 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

Dernier élément d'une liste

#let rec dernier = function 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

Plus grand élément d'une liste

#let rec max_list = function 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

Liste des entiers compris entre deux bornes

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 = 
   function i -> function 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]

Sous-liste des éléments pairs d'une liste

#let rec termes_pairs = function 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 = function 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]

Remplacement d'un élément d'une liste par un autre

#let rec remplace = function avant -> 
   function après -> function 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 = function avant -> 
   function après -> function 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]

Concaténation de deux lists, la fonction append

#let rec append = 
   function l1 -> function 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 = function 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 = function 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 = function (x,y) -> 
   x *. x +. y *. y;;
carré_norme : float * float -> float = 
<fun>
#let PS = 
   function (x,y) -> function (x',y') -> 
   x *. x' +. y *. y';;
PS : float * float -> float * float -> 
float = <fun>
#let proj1 = function (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 = function a -> function 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 = function a -> function 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 = function (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 = function n -> function m -> 
   if n < m then n else m;;
min : 'a -> 'a -> 'a = <fun>
#let min = function (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_d_identificateur = 
  { é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 = function d ->
   d.Jour = 25 && d.Mois = 12;;
est_Noël : date -> bool = <fun>

avec du filtrage

#let est_Noël = function 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 = function date -> 
   match date with 
   | {Jour=25; Mois=12; Année=a} -> true
   | _ -> false;;
est_Noël : date -> bool = <fun>
#let est_Noell = function date -> 
   match date with 
   | {Jour=25; Mois=12; _} -> true
   | _ -> false;;
est_Noell : date -> bool = <fun>

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 = function b -> 
 match b with
 | Cube c -> true
 | Parallélépipède (p1,p2,p3) -> false;;
est_cube : boîte -> bool = <fun>
#let est_cube = function b -> 
 match b with
 | Cube _ -> true
 | Parallélépipède _ -> false;;
est_cube : boîte -> bool = <fun>
#let est_cube  = function b -> 
 match b with
 | Cube _ -> true
 | _ -> false;;
est_cube : boîte -> bool = <fun>

#let est_printemps = function s -> 
 match s with
 | Printemps -> true
 | Été -> false
 | Automne -> false
 | Hiver -> false;;
est_printemps : saison -> bool = <fun>
#let est_printemps = function s -> 
 match s with
 | Printemps -> true
 | _ -> false;;
est_printemps : saison -> bool = <fun>
#let plus_grande_arête = function 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>

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_chaîne s i = 
   sub_string s i (string_length s-i);;
sous_chaîne : string -> int -> string = 
<fun>

#let rec char_in_string = 
   function c -> function s -> 
     not (s="") && 
     (c=s.[0] || 
      char_in_string c (sous_chaîne s 1));;
char_in_string : char -> string -> bool = 
<fun>
#let rec search = 
   function c -> function s -> 
     if c=s.[0] then 0 
     else 1+(search c (sous_chaîne s 1));;
search : char -> string -> int = <fun>
#let rec coupe = function s ->
   if char_in_string ` ` s then 
     let i = search ` ` s in
     Phrase (sub_string s 0 i, 
             coupe (sous_chaîne 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 = 
   function élém -> function a -> 
 match a with
 | 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

Arbres binaires de recherche à coefficients d'un type quelconque

#type 'a abr = 
 | Vide 
 | Noeud of 'a * 'a abr * 'a abr;;
Le type abr est défini.

Définition de type polymorphe : 'a est le paramètre de type et se lit a, alpha.

#let mon_arbre = 
   Noeud (10, 
          Noeud (5, 
                 Noeud (2,Vide, Vide), 
                 Noeud (8, Vide, Vide)),
          Noeud (30, 
                 Vide, 
                 Noeud (40, Vide, Vide)));;
mon_arbre : int abr =
 Noeud
  (10, Noeud (5, Noeud (2, Vide, Vide), 
Noeud (8, Vide, Vide)),
   Noeud (30, Vide, Noeud (40, Vide, 
Vide)))

#let rec member = 
   function élém -> function a -> 
 match a with
 | 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 : 'a -> 'a 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 dériv = 
   function s -> function exp -> 
 match exp with 
 | V nom -> 
   if s = nom then C 1 else C 0
 | C _ -> C 0
 | P (e1, e2) -> 
   P (dériv s e1, dériv s e2);;
dériv : string -> exp -> exp = <fun>
#dériv "x" mon_exp;;
- : exp = P (C 1, P (C 0, C 0))

Un peu d'ordre supérieur

Exemples simples

#let pente_en_0 = function 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 = 
   function f -> function g -> 
     function x -> g (f x);;
compose : ('a -> 'b) -> ('b -> 'c) -> 'a 
-> 'c = <fun>

Itérateurs

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

ì
í
î

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

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

Fonction sigma

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

Fonction map

#let rec noms_étudiants = 
   function liste_étudiants ->
 match liste_étudiants with
 | [] -> []
 | (nom, notes)::l -> 
 nom::(noms_étudiants l);;
noms_étudiants : ('a * 'b) list -> 'a list 
= <fun>
#let rec map = 
   function f -> function 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 = function 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 = function p -> function 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 = function l ->
   filter (function x -> (x mod 2 = 0)) l;;
termes_pairs : int list -> int list = 
<fun>
#let est_sur_axe_x = function (x,y) -> y=0.0;;
est_sur_axe_x : 'a * float -> bool = 
<fun>
#let vecteurs_axe_x = function l ->
   filter est_sur_axe_x l;;
vecteurs_axe_x : ('a * float) list -> ('a 
* float) list = <fun>

Insertion, tri

#let rec insérer = 
   function e -> function 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é = 
   function e -> function 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 = 
   function e -> function l ->
     insérer (prefix <) e l;;
insérer_ordre_croissant : 'a -> 'a list -> 
'a list = <fun>
#let insérer_ordre_décroissant = 
   insérer (prefix >);;
insérer_ordre_décroissant : '_a -> '_a 
list -> '_a list = <fun>
#let rec tri_insertion = 
   function priorité -> function 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 = 
   function l -> tri_insertion (prefix <) l;;
tri_insertion_ordre_croissant : 'a list -> 
'a list = <fun>