CAML à l'ESISAR (TP CS-110) – Anne.Benoit@imag.fr

Chapitre 2 et Chapitre 3

 

 

1. La récursivité

Les fonctions

  • Définir une fonction récursive

# let rec (q: int*int->int)=function

(a,b) -> if a<b then 0

else 1 + q(a-b,b);;

q : int*int -> int = <fun>

On définit une fonction qui s'appelle.

Ici, le deuxième paramètre doit être strictement positif.

  • Appeler une fonction récursive

# q(17,5);;

- : int = 3

Lors de l'appel d'une fonction récursive, il y a toute une série d'appels récursifs (la fonction se réappelle). Il est souvent utile de tracer de telles fonctions pour observer et comprendre leur comportement. Il est aussi courant qu'une fonction récursive boucle indéfiniment si elle est mal définie ou bien si on l'appelle avec des paramètres ne vérifiant pas la spécification.

Le filtrage

  • Réalisation sans filtrage

# let rec (fac1: int->int) = function

n -> if n=1 then 1

else fac1(n-1) * n;;

  • Réalisation avec filtrage

# let rec (fac2: int->int) = function

1 -> 1

| n -> fac2(n-1) * n;;

Ces deux réalisations sont équivalentes. Attention cependant car l'ordre des motifs de filtrage est importante : l'interpréteur vérifie dans l’ordre si le paramètre correspond à l'élément de filtrage.

Ainsi, si le paramètre vaut 1, on exécute l'expression de la première ligne (1). Sinon, le paramètre vaut n (ça marche dans tous les cas), on exécute l'expression de la deuxième ligne (fac2(n-1)*n)

 

2. Les listes en CAML

Le type "séquence de t"
  • Définir un type liste

# type R == int list;;

Le type R est le type liste d'entiers.

Le type "t list" correspond à une séquence de t.

  • Des listes

# [1;2;3;4;5];;

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

# [(1,2);(3,4)];;

- : int*int list = [1,2 ; 3,4]

Remarque : bien noter la différence entre une liste et un N-uplet :

  • La liste se note entre crochets [] et les éléments sont séparés par des point-virgules. De plus, tous les éléments d'une liste doivent être de même type.
  • Les éléments d'un N-Uplet sont séparés par des virgules, et peuvent être de différent types.

Fonctions pré-définies

Constructeur de liste vide :

# [];;

- : 'a list = []

Ajout d'un élément à gauche :

# 1 :: [2;3;4;5];;

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

Attention : il faut ajouter un élément du même type que les autres éléments de la liste, on ajoute un seul élément à la fois, et toujours à une liste (éventuellement la liste vide)

Concaténation :

# [1;2] @ [3;4;5];;

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

Pas utilisé en TP.

Primitives rajoutées (fichier primitives.ml) :

EstVide, premier, fin

dernier, debut, ajd

Ces primitives correspondent à celles étudiées en cours.

 

 

 

 

3. Textes

Introduction

Dans la notation du cours, un texte est une séquence de caractères (liste en Caml). Cependant en Caml, il existe un type texte (string) différent des séquences de caractères.

La bibliothèque Caml a été enrichie par quelques fonctions sur les textes qui permettent une approche des textes similaire à celle des listes (fonctions disponibles dans le fichier primitives.ml)

Fonctions pré-définies

- txVide (texte vide), EstVide_tx (un texte est-il vide?)

- ajg_tx (ajout d'un caractère à gauche d'un texte),

pre_tx (premier caractère),

fin_tx (fin du texte : tout sauf le premier)

- ajd_tx (ajout d'un caractère à droite d'un texte),

der_tx (dernier caractère),

deb_tx (début du texte : tout sauf le dernier)

 

 

4. Arbres binaires

Le type "arbre binaire"

La bibliothèque Caml a été enrichie par un type générique nommé ArBin. Un arbre binaire de t est de type t ArBin (t peut être int, string, …).

Cette notation est analogue à la notation des types séquence (t list)

Plusieurs fonctions sont disponibles sur les arbres binaires (fichier primitives.ml).

Constructeurs

abV : le constructeur "arbre vide"

abNV : le constructeur "arbre non vide"

abS : arbre singleton

abS(racine) racine

abG : arbre unaire gauche

abD : arbre unaire droit

Dans tous les cas,

  • racine est un élément de type t
  • Gauche et Droit sont de type t ArBin

Testeurs

EstVide_ab, Single_ab, UnGauche_ab, UnDroit_ab, Bin_ab testent respectivement si l'arbre est vide, singleton, unaire gauche, unaire droit, binaire.

Sélecteurs

Gauche : renvoie le fils gauche d'un arbre

Droit : renvoie le fils droit d'un arbre

Racine : renvoie la racine d'un arbre

Gauche (abNV(G,r,D)) = G

Racine (abNV(G,r,D)) = r

Droit (abNV(G,r,D)) = D

 

5. Expressions arithmétiques

Une utilisation des arbres binaires

Une expression arithmétique formée à l'aide d'entiers et des opérateurs usuels (+, -, *, /) peut être représentée sous forme d'un arbre binaire non vide

Les fonctions disponibles sur les arbres binaires représentant des expressions sont disponibles dans le fichier primitives.ml. Se reporter au polycopié des TPs pour le détail!

Un exemple