Partie I
Un survol du langage

#let une_constante = 1;;
une_constante : int = 1
#let une_constante = 3.4 in 
   une_constante+.1.2;;
- : float = 4.6
#let carré = function x -> x*x;;
carré : int -> int = <fun>
#let carré (x) = x*x;;
carré : int -> int = <fun>
#let carré x = x*x;;
carré : int -> int = <fun>
#carré (25);;
- : int = 625
#carré 36;;
- : int = 1296
#let rec fact = function n ->
   if n <= 0 then 1 else n*fact(n-1);;
fact : int -> int = <fun>

#let une_variable = ref true;;
une_variable : bool ref = ref true
#une_variable := false;;
- : unit = ()
#une_variable;;
- : bool ref = ref false
#une_constante := 5;;
Entrée interactive:
>une_constante := 5;;
>^^^^^^^^^^^^^
Cette expression est de type int,
mais est utilisée avec le type 'a ref.
#prefix := ;;
- : 'a ref -> 'a -> unit = <fun>

#sys__getenv;;
- : string -> string = <fun>
#getenv;;
Entrée interactive:
>getenv;;
>^^^^^^
L'identificateur getenv n'est pas défini.

##open "sys";;
#getenv;;
- : string -> string = <fun>
#getenv "DISPLAY";;
- : string = ":0.0"
#getenv "PRINTER";;
Exception non rattrapée: Not_found

##close "sys";;
#getenv;; 
Entrée interactive:
>getenv;; 
>^^^^^^
L'identificateur getenv n'est pas défini.

#9, 9.0, "9", `9`;;
- : int * float * string * char = 9, 9.0, 
"9", `9`
#let somme = function (x, y) -> x+y;;
somme : int * int -> int = <fun>
#let diagonale = function x -> (x, x);;
diagonale : 'a -> 'a * 'a = <fun>
#diagonale 2, diagonale 1.3 ;;
- : (int * int) * (float * float) = (2, 
2), (1.3, 1.3)
#let first = function (x, y) -> x;;
first : 'a * 'b -> 'a = <fun>
#first (1, 3);;
- : int = 1
#let (prem, sec) =  (1, 1.0);;
prem : int = 1
sec : float = 1.0

#type étudiant = {nom : string; âge : int};;
Le type étudiant est défini.
#let lambda = {nom = "LA"; âge = 20};;
lambda : étudiant = {nom = "LA"; âge = 
20}
#let anniv1 = function x -> 
   {nom = x.nom; âge = x.âge+1};;
anniv1 : étudiant -> étudiant = <fun>
#let anniv2 x = match x with
 | {nom = n; âge = a} -> 
   {nom = n; âge = a+1};;
anniv2 : étudiant -> étudiant = <fun>
#anniv1 lambda, lambda;;
- : étudiant * étudiant = {nom = "LA"; âge 
= 21}, {nom = "LA"; âge = 20}

#type couleur = 
 | Coeur | Pique | Carreau | Trèfle;;
Le type couleur est défini.
#type carte = 
 | Dame of couleur 
 | Petit of int*couleur 
 | Joker;;
Le type carte est défini.
#let valeurfoo c = match c with
 | Dame _ -> 20
 | Petit (10, c)-> 10
 | Petit (x, y) -> 
   if x = 9 & y = Coeur then 11 else 0
 | Joker -> 1;;
valeurfoo : carte -> int = <fun>
#let dameCoeur = Dame Coeur 
 and petit = Petit (7, Pique);;
dameCoeur : carte = Dame Coeur
petit : carte = Petit (7, Pique)
#valeurfoo petit;;
- : int = 0

#type exp = 
 | V of string | C of int | P of exp*exp;;
Le type exp est défini.
#let rec eval e = match e with
 | V _ -> 0
 | C n -> n
 | P (e1, e2) -> (eval e1)+(eval e2);;
eval : exp -> int = <fun>
#let une_exp = P (P (V "x", C 25), C 10);;
une_exp : exp = P (P (V "x", C 25), C 10)
#eval une_exp;;
- : int = 35

#for i = 0 to 9 do
   print_int i
 done;;
0123456789- : unit = ()
#let v=[|1;2;3|];;
v : int vect = [|1; 2; 3|]
#v.(2);;
- : int = 3
#for i = 0 to vect_length v-1 do
   print_int v.(i)
 done;;
123- : unit = ()
#let i = ref 0 in
 while !i < vect_length v do
    print_int v.(!i); incr i
 done;;
123- : unit = ()

Partie II
Présentation détaillée du langage

• 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é)

• 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;;
  

  ou

  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.

• 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

• 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
  | filtre1 -> exp1
  ...
  | filtren -> expn
  

  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.

• 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.

• 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
  

• 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>
  

• 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))
    

• 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

  ì í î

  u0 = a, un+1 = f(un)

  #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>
  

• modélisation de la notion de case mémoire: on peut consulter son contenu courant et modifier son contenu.
• correspond presque à la notion de variable dans les langages impératifs classiques, Pascal par exemple.
• utilisées comme des compteurs ou des accumulateurs dont le contenu évolue au cours du calcul.

Création et type

#let compteur = ref (0);;
compteur : int ref = ref 0

Consultation du contenu courant (déréférencement)

#!compteur;;
- : int = 0

Modification du contenu (affectation, effet de bord)

#compteur:=2;;
- : unit = ()
#!compteur;;
- : int = 2

#let incrémente c = c := !c+1;;
incrémente : int ref -> unit = <fun>
#incrémente compteur; !compteur;;
- : int = 3

---

Figure 0.1 : Les principales notions sur les vecteurs

---

Création et type

#[|1; 2; 3|];;
- : int vect = [|1; 2; 3|]
#make_vect 4 2;;
- : int vect = [|2; 2; 2; 2|]
#let r = make_vect 3 "Bonjour";;
r : string vect = [|"Bonjour"; "Bonjour"; 
"Bonjour"|]

Consultation du contenu courant

#r;;
- : string vect = [|"Bonjour"; "Bonjour"; 
"Bonjour"|]
#r.(0);;
- : string = "Bonjour"

Modification du contenu

#r.(1) <- "tout"; r.(2) <- "le monde!";;
- : unit = ()
#r;;
- : string vect = [|"Bonjour"; "tout"; "le 
monde!"|]

Création, types et dimensions

#[|[|1; 2; 3|]; [|4; 5; 6|]; [|7; 8; 9|]|];;
- : int vect vect = [|[|1; 2; 3|]; [|4; 5; 
6|]; [|7; 8; 9|]|]
#make_matrix 2 1 "Bonjour";;
- : string vect vect = [|[|"Bonjour"|]; 
[|"Bonjour"|]|]
#let M = make_matrix 2 3 0;;
M : int vect vect = [|[|0; 0; 0|]; [|0; 0; 
0|]|]
#(* nombre de lignes *)
 vect_length M;; 
- : int = 2
#(* nombre de colonnes *)
 vect_length M.(0);; 
- : int = 3

Consultation du contenu courant

#M;;
- : int vect vect = [|[|0; 0; 0|]; [|0; 0; 
0|]|]
#M.(0).(2);;
- : int = 0

Modification du contenu

#M.(1).(0) <- 2; M.(1).(2) <- 5;;
- : unit = ()
#M;;
- : int vect vect = [|[|0; 0; 0|]; [|2; 0; 
5|]|]

#print_string "Bonjour "; 
 print_string "tout le monde !";;
Bonjour tout le monde !- : unit = ()
#print_string;;
- : string -> unit = <fun>
#1+2;3;;
Entrée interactive:
>1+2;3;;
>^^^
Attention: cette expression est de type 
int,
mais est utilisée avec le type unit.
- : int = 3

• Syntaxe:
  while condition do actions done
  for ident = début to fin do actions done
  for ident = début downto fin do actions done
• Exemples:

  #for i = 0 to 9 do print_int i done;;
  0123456789- : unit = ()
  #let i = ref 0 in
   while !i <= 9 do
      print_int !i; incr i
   done;;
  0123456789- : unit = ()
  #for i = 9 downto 0 do print_int i done;;
  9876543210- : unit = ()
  #for i = 0 to (vect_length r)-1 do
     print_string r.(i); print_string " "
   done;;
  Bonjour tout le monde! - : unit = ()
  

  #for i = 0 to (vect_length M)-1 do
     for j = 0 to (vect_length M.(0))-1 do
     print_int M.(i).(j); print_string " "
     done;
     print_newline ()
   done;;
  0 0 0 
  2 0 5 
  - : unit = ()
  

• Réponse propre quand il n'y a pas de réponse pertinente
• failwith déjà vu
• Des exceptions nommées (plus précis pour récupérer, etc.)
• Un mécanisme de traitement d'exceptions doit permettre de réaliser trois actions :
  • déclarer une exception (si elle n'est pas prédéfinie);
  • déclenche, lever, signaler une exception;
  • traiter l'exception.
• Les exceptions prédéfinies

  exception Division_by_zero
  exception Out_of_memory
  exception Invalid_argument of string
  exception Failure of string
  exception Not_found
  

• Deux levées d'exceptions prédéfinies

  value failwith : string -> 'a
  value invalid_arg : string -> 'a
  

• Exemples de levée des exceptions prédéfinies

  #(* Par des opérations prédéfinies *)
   1/0;;
  Exception non rattrapée: Division_by_zero
  #hd [];;
  Exception non rattrapée: Failure "hd"
  #[|1;2;3|].(10);;
  Exception non rattrapée: Invalid_argument 
  "vect_item"
  #(* Par des fonctions que l'on définit *)
   let rec member nom liste = match liste with
   | [] -> raise Not_found
   | e::l -> e=nom || member nom l;;  
  member : 'a -> 'a list -> bool = <fun>
  #member 1 [1;2;3];;
  - : bool = true
  #member 4 [1;2;3];;
  Exception non rattrapée: Not_found
  #let chiffre1 n =
     if n < 10 then n else 
     raise (Invalid_argument (string_of_int n));;
  chiffre1 : int -> int = <fun>
  #chiffre1 12;;
  Exception non rattrapée: Invalid_argument 
  "12"
  #let chiffre2 n =
     if n < 10 then n else 
     invalid_arg (string_of_int n);;
  chiffre2 : int -> int = <fun>
  #chiffre2 12;;
  Exception non rattrapée: Invalid_argument 
  "12"
  #let chiffre3 n =
     if n < 10 then n else 
     failwith "chiffre3: argument > 10";;
  chiffre3 : int -> int = <fun>
  #chiffre3 12;;
  Exception non rattrapée: Failure 
  "chiffre3: argument > 10"
  #let chiffre4 n =
     if n < 10 then n else 
     raise (Failure "chiffre4: argument > 10");;
  chiffre4 : int -> int = <fun>
  #chiffre4 12;;
  Exception non rattrapée: Failure 
  "chiffre4: argument > 10"
  

• Déclaration (exception) et type (exn, type somme prédéfini extensible)

  #(* Sans argument *)
   exception Stop;;
  L'exception Stop est définie.
  #Stop;;
  - : exn = Stop
  #(* Avec argument *)
   exception Trouvé of int;;
  L'exception Trouvé est définie.
  #Trouvé;;
  - : int -> exn = <fun>
  #Match_failure;;
  - : string * int * int -> exn = <fun>
  

• Levée (raise)

  ... 
  raise exception 
  ...
  

  #let search e v =
     for i = 0 to vect_length v - 1 do
       if v.(i)=e then raise (Trouvé i)
     done;;
  search : 'a -> 'a vect -> unit = <fun>
  #let search e v =
     let i = ref 0 in
     while true do 
       if v.(!i)=e then raise (Trouvé !i);
       i := !i+1
     done;;
  search : 'a -> 'a vect -> unit = <fun>
  #search "B" [|"A";"B";"C";"D"|];;
  Exception non rattrapée: Trouvé 1
  #search "E" [|"A";"B";"C";"D"|];;
  Exception non rattrapée: Invalid_argument 
  "vect_item"
  #let failwith s = raise (Failure s);;
  failwith : string -> 'a = <fun>
  

  Une levée d'exception est un effet de bord.
• Rattrapage ou récupération (try ... with)

  try expression with 
  | exception_1 -> expression_1
  | exception_2 -> expression_2
  | :
  | exception_n -> expression_n
  

  On appelle l'expression try ... with le traite-exception de l'exception exception_j.
  
  Chaque expression_i peut lever à nouveau une des exceptions exception_j.

  #(* Sous-vecteur d'un vecteur v commençant 
      à la première occurrence de l'élément e
      dans v *)
   let sous_vecteur e v =
     try search e v;[|"impossible"|] with
     | Trouvé i -> 
       sub_vect v i (vect_length v - i)
     | Invalid_argument "vect_item" -> [||];;
  sous_vecteur : string -> string vect -> 
  string vect = <fun>
  #sous_vecteur "B" [|"A";"B";"C";"D"|];;
  - : string vect = [|"B"; "C"; "D"|]
  #sous_vecteur "E" [|"A";"B";"C";"D"|];;
  - : string vect = [||]
  #let sans_doublons v = 
     try 
       for i = 0 to vect_length v - 1 do
         if v.(i)=v.(i+1) then raise Stop
       done; true 
     with Stop -> false;;
  sans_doublons : 'a vect -> bool = <fun>
  

  #exception absent of int;;
  L'exception absent est définie.
  #let rec trouve_nom numero amphi = 
   match amphi with
   | [] -> raise (absent numero)
   | (x,n)::reste -> 
     if n=numero then x 
     else trouve_nom numero reste;;
  trouve_nom : int -> ('a * int) list -> 'a 
  = <fun>
  #let verif = function (numero, amphi) ->
     try (trouve_nom numero amphi) with
     | absent p -> "chercher_à_la_scolarité";;
  verif : int * (string * int) list -> 
  string = <fun>
  

  #exception erreur of int;;
  L'exception erreur est définie.
  #exception signal of string;;
  L'exception signal est définie.
  #let f_qui_déclenche = function x ->
     if x < 0 then raise (erreur (-x)) else 
     if x=0 
        then raise (signal "reprise au vol") 
     else x;; 
  f_qui_déclenche : int -> int = <fun>
  #f_qui_déclenche (-4);;
  Exception non rattrapée: erreur 4
  #f_qui_déclenche 2;;
  - : int = 2
  #let récupère = function x ->
     try f_qui_déclenche x with
     | erreur 0 -> 0 
     | erreur y -> 25-y+3*x 
     | signal _ -> 100*x+1;;
  récupère : int -> int = <fun>
  #(récupère 2),(récupère (-4)),(récupère 0);;
  - : int * int * int = 2, 9, 1
  

• Les exceptions comme style de programmation
  • à la place de sentinelles, permet notamment d'interrompre des boucles parcourant toute une structure dès que l'on a trouvé dans la structure un élément vérifiant une propriété donnée

    #let sans_doublons v = 
       let i = ref 0 
       and t = ref false in
       while !i < vect_length v && not !t do
         if v.(!i)=v.(!i+1) then t := true;
         i := !i+1
       done; !t;;
    sans_doublons : 'a vect -> bool = <fun>
    #let rec member_rec e l = match l with
     | [] -> raise Not_found
     | e'::l' -> 
       if e=e' then raise Stop 
       else member_rec e l';;
    member_rec : 'a -> 'a list -> 'b = <fun>
    #let member e l = 
       try member_rec e l with
       | Not_found -> false
       | Stop -> true;;
    member : 'a -> 'a list -> bool = <fun>
    #member 2 [1;2;3];;
    - : bool = true
    #member 4 [1;2;3];;
    - : bool = false
    #let rec member x l = 
       try x = hd l or member x (tl l)  
       with Failure "hd" -> false;;
    member : 'a -> 'a list -> bool = <fun>
    #member 2 [1;2;3];;
    - : bool = true
    #member 4 [1;2;3];;
    - : bool = false
    

  
  

• Utiliser ce qui paraît le plus simple, le plus naturel.
• Même si votre expérience est surtout impérative, ne pas oublier que le style fonctionnel est souvent plus compact ou plus facile à comprendre.

#let rec fact = function n ->
   if n <= 0 then 1 else n*fact(n-1);;
fact : int -> int = <fun>
#let fact_imp = function n ->
   let temp = ref 1 in
     for i = 1 to n do
       temp :=!temp*i
     done;
   !temp ;;
fact_imp : int -> int = <fun>
#let rec fib1 = function n ->
   if n <= 1 then 1 
   else fib1(n-1)+fib1(n-2);;
fib1 : int -> int = <fun>
#let fib2 = function n ->
   let (cour, prec, temp) = 
       (ref 1, ref 1, ref 1) in
     for i = 1 to n-1 do
       temp := !cour;
       cour := !cour + !prec;
       prec := !temp
     done; !cour;;
fib2 : int -> int = <fun>
#let fib3 = function p ->
   let rec fib_accu prec cour n = 
     if p = n then cour
     else fib_accu cour (prec+cour) n+1 in
   if p <= 1 then 1 else fib_accu 1 1 1;;
fib3 : int -> int = <fun>

Partie III
Un exemple complet
complément sur les types polymorphes

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

#type 'a arbre = Vide | Noeud of 'a arbre_non_vide
 and 'a arbre_non_vide = 
   { Étiquette: 'a; 
     Fils_gauche: 'a arbre; 
     Fils_droit: 'a arbre };;
Le type arbre est défini.
Le type arbre_non_vide est défini.

#type ('a, 'b) arbre = 
 | Vide | Feuille of 'b | Noeud of ('a, 'b) arbre_non_vide
 and ('a, 'b) arbre_non_vide = 
   { Étiquette: 'a; 
     Fils_gauche: ('a, 'b) arbre; 
     Fils_droit: ('a, 'b) arbre };;
Le type arbre est défini.
Le type arbre_non_vide est défini.

---

Figure 0.2 : mon_arbre

---

#let mon_arbre = Noeud 
   {Étiquette = 10;
    Fils_gauche = Noeud 
      {Étiquette = 5; 
       Fils_gauche = Feuille 2; Fils_droit = Feuille 8}; 
    Fils_droit = Noeud 
      {Étiquette = 30; 
       Fils_gauche = Vide; Fils_droit = Feuille 40}};;
mon_arbre : (int, int) arbre = Noeud ...

#let mon_arbre = Noeud 
   {Étiquette = 10;
    Fils_gauche = Noeud 
      {Étiquette = 5; 
       Fils_gauche = Noeud 
         {Étiquette = 2; 
          Fils_gauche = Vide; Fils_droit = Vide};
       Fils_droit = Noeud 
         {Étiquette = 8; 
          Fils_gauche = Vide; Fils_droit = Vide}}; 
    Fils_droit = Noeud 
      {Étiquette = 30; 
       Fils_gauche = Vide; 
       Fils_droit = Noeud 
         {Étiquette = 40; 
          Fils_gauche = Vide; Fils_droit = Vide}}};;
mon_arbre : (int, 'a) arbre = Noeud ...

---

Figure 0.3 : mon_expr

---

#type op = 
 | Addition | Soustraction | Multiplication | Division;;
Le type op est défini.

#let mon_expr = Noeud
   {Étiquette = Addition; 
    Fils_gauche = Noeud
      {Étiquette = Multiplication; 
       Fils_gauche = Feuille 1; Fils_droit = Feuille 2};
    Fils_droit = Noeud
      {Étiquette = Soustraction; 
       Fils_gauche = Feuille 3;
       Fils_droit = Noeud 
         {Étiquette = Division; 
          Fils_gauche = Feuille 4; Fils_droit = Feuille 5}}};;
mon_expr : (op, int) arbre = Noeud ...

#let rec print_arbre print_étiquette print_feuille arbre = 
 match arbre with
 | Vide -> ()
 | Feuille f -> print_feuille f
 | Noeud {Étiquette = e;Fils_gauche = fg;Fils_droit = fd} ->
     print_string "(";
     print_arbre print_étiquette print_feuille fg;
     print_étiquette e; 
     print_arbre print_étiquette print_feuille fd;
     print_string ")";;
print_arbre : ('a -> 'b) -> ('c -> unit) -> ('a, 'c) arbre 
-> unit = <fun>
#print_arbre print_int print_int mon_arbre;;
(((2)5(8))10(30(40)))- : unit = ()

#let print_op op = match op with
 | Addition -> print_string "+"
 | Soustraction -> print_string "-"
 | Multiplication -> print_string "*"
 | Division -> print_string "/";;
print_op : op -> unit = <fun>
#print_arbre print_op print_int mon_expr;;
((1*2)+(3-(4/5)))- : unit = ()

#let rec insérer_arbre x arbre = match arbre with
 | Vide -> Feuille x
 | Feuille y -> 
     if x < y 
     then Noeud {Étiquette = y; Fils_gauche = Feuille x; 
                 Fils_droit = Vide} 
     else Noeud {Étiquette = y; Fils_gauche = Vide; 
                 Fils_droit = Feuille x}
 | Noeud {Étiquette = e;Fils_gauche = fg;Fils_droit = fd} ->  
     if x < e 
     then Noeud {Étiquette = e; 
                 Fils_gauche = insérer_arbre x fg; 
                 Fils_droit = fd}
     else Noeud {Étiquette = e; Fils_gauche = fg; 
                 Fils_droit = insérer_arbre x fd};;
insérer_arbre : 'a -> ('a, 'a) arbre -> ('a, 'a) arbre = 
<fun>
#let rec arbre_of_list l = match l with 
 | [] -> Vide
 | x::l' -> insérer_arbre x (arbre_of_list l');;
arbre_of_list : 'a list -> ('a, 'a) arbre = <fun>
#print_arbre print_int print_int 
   (arbre_of_list [ 2; 5; 4; 6; 3; 7; 1; 8; 0; 5 ]);;
((0(1(234)))5(((56)7)8))- : unit = ()
#let rec list_of_arbre arbre = match arbre with
 | Vide -> []
 | Feuille f -> [f]
 | Noeud {Étiquette = e;Fils_gauche = fg;Fils_droit = fd} ->
     (list_of_arbre fg)@[e]@(list_of_arbre fd);;
list_of_arbre : ('a, 'a) arbre -> 'a list = <fun>
#let tri l = list_of_arbre (arbre_of_list l);;
tri : 'a list -> 'a list = <fun>
#tri [ 2; 5; 4; 6; 3; 7; 1; 8; 0; 5 ];;
- : int list = [0; 1; 2; 3; 4; 5; 5; 6; 7; 8]

#let rec insérer_arbre ordre x arbre = match arbre with
 | Vide -> Feuille x
 | Feuille y -> 
     if ordre x y 
     then Noeud {Étiquette = y; Fils_gauche = Feuille x; 
                 Fils_droit = Vide } 
     else Noeud {Étiquette = y; Fils_gauche = Vide; 
                 Fils_droit = Feuille x }
 | Noeud {Étiquette = e;Fils_gauche = fg;Fils_droit = fd} ->  
     if ordre x e 
     then Noeud {Étiquette = e; 
                 Fils_gauche = insérer_arbre ordre x fg; 
                 Fils_droit = fd}
     else Noeud {Étiquette = e; Fils_gauche = fg; 
                 Fils_droit = insérer_arbre ordre x fd};;
insérer_arbre :
 ('a -> 'a -> bool) -> 'a -> ('a, 'a) arbre -> ('a, 'a) 
arbre = <fun>

#let rec arbre_of_list ordre l = match l with 
 | [] -> Vide
 | x::l' -> insérer_arbre ordre x (arbre_of_list ordre l');;
arbre_of_list : ('a -> 'a -> bool) -> 'a list -> ('a, 'a) 
arbre = <fun>
#let rec list_of_arbre arbre = match arbre with
 | Vide -> []
 | Feuille f -> [f]
 | Noeud a ->
     (list_of_arbre a.Fils_gauche)@
     [a.Étiquette]@
     (list_of_arbre a.Fils_droit);;
list_of_arbre : ('a, 'a) arbre -> 'a list = <fun>
#let tri ordre l = list_of_arbre (arbre_of_list ordre l);;
tri : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun>
#tri (prefix <) [ 2; 5; 4; 6; 3; 7; 1; 8; 0; 5 ];;
- : int list = [0; 1; 2; 3; 4; 5; 5; 6; 7; 8]
#tri (prefix >) [ 2; 5; 4; 6; 3; 7; 1; 8; 0; 5 ];;
- : int list = [8; 7; 6; 5; 5; 4; 3; 2; 1; 0]

#let rec évaluation arbre = match arbre with
 | Vide -> 0
 | Feuille i -> i
 | Noeud a ->
     let efg = évaluation a.Fils_gauche 
     and efd = évaluation a.Fils_droit in
     match a.Étiquette with 
     | Addition -> efg + efd
     | Soustraction -> efg - efd
     | Multiplication -> efg * efd
     | Division -> efg / efd;;
évaluation : (op, int) arbre -> int = <fun>
#évaluation mon_expr;;
- : int = 5

#type constructeur = 
 | Variable | Constante | Plus | Multiplié;;
Le type constructeur est défini.
#let mon_exp = Noeud 
   {Étiquette = Plus; 
    Fils_gauche = Noeud 
      {Étiquette = Variable;
       Fils_gauche = Feuille 1; Fils_droit = Vide}; 
    Fils_droit = Noeud 
      {Étiquette = Plus; 
       Fils_gauche = Noeud 
         {Étiquette = Variable; Fils_gauche = Feuille 1;
          Fils_droit = Vide}; 
       Fils_droit = Noeud 
         {Étiquette = Constante; Fils_gauche = Feuille 3;
          Fils_droit = Vide}}};;
mon_exp : (constructeur, int) arbre = Noeud ...

Ce document a été traduit de L^AT_EX par H^EV^EA.