Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Le langage CAML
Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.
Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.
Activité de découverte B.dec
Introduction
CAML est un langage fonctionnel qui trouve ses bases théoriques, mais en partie aussi l’inspiration de sa syntaxe, dans le (\lambda)-calcul. Nous allons l’aborder avec des exemples que vous êtes invités à reproduire sur machine.
La version la plus aboutie est OCAML. Elle permet une programmation fonctionnelle et / ou impérative et orientée objet. Seul l’aspect programmation fonctionnelle pure nous intéresse dans cet enseignement.
Il existe des compilateurs en ligne, ainsi que des versions Linux, Windows, et MacOS disponibles sur .
La programmation fonctionnelle diffère de la programmation impérative sur deux points essentiels :
- Une variable représente une même valeur pendant toute sa durée de vie.
- En conséquence, il n’y a pas de boucles telles que
for,while,…
Elle s’appuie sur la récursivité pour réaliser tous les calculs et traitements qui pourraient être réalisés de manière itérative dans les langages impératifs.
B.dec1 : Fonctions non récursives à 1 paramètre
Voici un premier exemple de fonction, spécifiée de deux manières différentes.
(* Version 1 *)
let abs = fun x ->
if x < 0 then
-x
else
x ;;
Soit
absla fonction qui àxassocie-xsix < 0, sinonx.
(* Version 2*)
let abs x =
if x < 0 then
-x
else
x ;;
Soit
absla fonction qui, appliquée àxretourne-xsix < 0, sinonx.
La première formulation est directement inspirée du (\lambda)-calcul.
let abs = fun x -> if x < 0 then -x else x ;;
[\boxed{\text{abs}} = \lambda x . \boxed{\text{terme qui spécifie le calcul de }|x|}
]
L’utilisation de cette fonction ressemble à une application en (\lambda)-calcul :
À la place de…
(\boxed{\text{abs}} \; \boxed{3})
…où (\boxed{\text{abs}}) est l’abstraction spécifiant le calcul de la valeur absolue et (\boxed{3}) le terme de (\lambda)-calcul représentant l’entier 3, on écrit :
abs 3;;
Et on obtient l’affichage :
int = 3
La deuxième formulation, plus lisible, est celle que nous utiliserons dans la suite du cours.
Lors qu’on saisit dans une console CAML en mode interactif :
let abs x =
if x < 0 then
-x
else
x ;;
Le compilateur nous répond :
abs : int -> int = <fun>
Cet affichage s’interprète de la manière suivante :
absest une fonction qui à tout entier (typeint) associe un entier.
Pourtant, nous n’avons pas indiqué de type dans la spécification de la fonction. CAML a inféré ce type int.
Si on compile cette variante…
let absf x =
if x < 0. then
-.x
else
x ;;
…on obtient l’affichage :
val absf : float -> float = <fun>
Les opérations et valeurs flottantes utilisent une notation spécifique, comme par exemple -. pour la soustraction et la négation.
Mais nous ne sommes pas au bout de nos surprises. Si on saisit…
absf -.67.0;;
…on obtient un message d’erreur.
CAML interprète absf -. 67. comme (absf -.) 67.0 en vertu de **l’associativité à gauche des applications **héritée du (\lambda)-calcul.
Pour calculer la valeur absolue de -65.0, on doit écrire…
absf (-. 67.0);;
…avec pour résultat :
float = 67.
Exercice de découverte B.dec.x1
La fonction de Syracuse syr associe à tout entier x la valeur :
x / 2sixest pair,3 * x + 1sixest impair.
Donnez une spécification de la fonction syr en CAML. L’opérateur modulo s’écrit mod.
let syr x =
if x mod 2 = 0 then
x / 2
else
(3 * x) + 1;;
Donnez la ligne à saisir pour appliquer syr à 7 et l’appliquer à nouveau au résultat obtenu.
syr (syr 7);;
B.dec2 : Curryfication
En CAML, les fonctions à plusieurs paramètres n’existent pas, mais on peut les « simuler » par deux procédés dont l’un est appelé curryfication, en mémoire au mathématicien Haskell Curry (1900..1982).
Prenons l’exemple d’une fonction à 2 paramètres telle que la fonction somme…
let sum a b = a + b;;
…dont la signature est :
sum : int -> int -> int = <fun>
Cette signature, retournée par le compilateur, se lit int -> (int -> int) en vertu de l’associativité à droite des abstractions héritée du (\lambda)-calcul.
On l’interprète de la manière suivante :
sumest une fonction qui à tout entier associe (une fonction qui à tout entier associe un entier).
En CAML, une fonction peut accepter une fonction en paramètre et retourner une fonction.
Quand on écrit…
sum 10 15;;
…qui est équivalent, en vertu de l’associativité à gauche des application, à…
(sum 10) 15;;
…on obtient le résultat :
int = 25
Mais c’est le détail de cette évaluation qui est intéressant :
sum 10est d’abord évalué, et le résultat est une fonction qui à tout entierbassocie10 + b.- puis cette fonction est appliquée à 15, avec pour résultat 25.
On peut d’ailleurs décomposer les deux étapes…
let f = sum 10;;
f 15;;
…avec le même résultat.
La signature de f est :
f : int -> int = <fun>
Exercice de découverte B.dec.x2
Si saisi dans la console CAML…
sum (10 15);;
… on obtient un message d’erreur. Expliquez pourquoi.
CAML essaie d’appliquer 10 à 15, or 10 n’est pas une fonction.
Exercice de découverte B.dec.x3
Quelle est la signature de la fonction suivante ?
let f a b c = a + (b * c );;
Quel est la signature de la fonction suivante ?
f 2 2;;
La signature de f est :
int -> int -> int -> int = <fun>
L’évaluation f 2 2 a pour résultat une fonction qui a tout entier c associe 2 + (2 * c), parce que f 2 2 c retourne 2 + (2 * c).
Exercice de découverte B.dec.x4
Spécifiez la fonction m telle que m a b retourne true si b est un multiple de a et false sinon.
Voici une solution :
let m a b =
if b mod a = 0 then
true
else
false;;
Et une autre version plus concise :
let m a b = (b mod a = 0);;
Il est aussi possible de définir une fonction ayant pour seul paramètre un couple de deux entiers. Cette technique se rapproche du style des fonctions en programmation impérative (C, python,…). Elle est moins dans « l’esprit » de CAML, mais il est intéressant d’en connaître la syntaxe.
let add (a,b) = a + b;;
La signature de la fonction est :
add : int * int -> int = <fun>
La fonction s’utilise avec la syntaxe suivante :
add (10,15);;
Le résultat est :
int = 25
Attention, avec cette fonction, les syntaxes suivantes sont incorrectes :
add 10 15;;
(add 10) 15
add (10 15);;
Dans la suite, nous n’utiliserons pas cette syntaxe. Nous utiliserons le principe de la curryfication pour spécifier des fonctions à plusieurs paramètres.
B.dec3 : Listes et récursivité
Une liste peut être construite ou décomposée avec [] et ::.
Exemple :
let m = 3::[];;
let p = 7::m;;
Résultat :
m : int list = [3]
p : int list = [7;3]
La reconnaissance de motifs permet de décomposer une liste. Voici un exemple. La fonction suivante permet de calculer la longueur d’une liste.
let rec longueur w =
match w with
|[] -> 0
|x::q -> 1 + longueur q;;
Le mot clé rec est nouveau. Il indique que la fonction définie est récursive.
L’instruction match permet de réaliser un branchement qui est déterminé par la structure de la liste w. Si cette liste est vide alors la valeur de retour est 0. Si cette liste se décompose en une tête x et une queue q alors sa longueur vaut 1 plus la longueur de q, laquelle est calculée par un appel récursif.
La signature de longueur est :
longueur : a' list -> int = <fun>
Elle nous dit que nous avons une fonction qui à toute liste d’éléments d’un type 'a quelconque associe un entier.
Voici un exemple d’utilisation…
longueur [1;2;7];;
…avec pour résultat :
int = 3
Les motifs d’un match doivent couvrir toutes les possibilités. Voici une spécification incorrecte d’une fonction qui produit le dernier élément d’une liste.
let rec dernier w =
match w with
|[e] -> e;
|x::q -> dernier q;;
Le problème est qu’aucun des motifs de l’instruction match ne couvre le cas où la liste w est vide. On peut corriger en ajoutant ce cas, qui produira un message d’erreur à l’exécution.
let rec dernier w =
match w with
|[] -> failwith "Liste vide"
|[e] -> e;
|x::q -> dernier q;;
Le principe du calcul est le suivant :
- Le dernier élément d’une liste qui contient un seul élément est cet élément.
- Le dernier élément d’une liste contenant au moins deux éléments et le dernier élément de la queue de cette liste.
La signature de la fonction est…
dernier : 'a list -> 'a = <fun>
…i.e., une fonction qui a toute liste d’éléments d’un type quelconque 'a associe un élément de type 'a.
Exercice de découverte B.dec.x5
Spécifiez une fonction sum telle que si w est une liste d’entiers alors sum w retourne la somme des valeurs de w.
let rec sum w =
match w with
|[] -> 0
|x::q -> x + (sum q);;
Examinons maintenant une fonction qui construit et retourne une liste. La fonction pVals ci-dessous produit la liste des valeurs paires d’une liste d’entier w.
let rec pVals w =
match w with
|[] -> []
|x::q ->
if x mod 2 = 0 then
x::(pVals q)
else
pVals q;;
- Si la liste d’entrée est vide, la liste de sortie aussi.
- Si la liste d’entrée est de la forme
x::qavecxpair, la liste de sortie a pour têtexet pour queue les valeurs paires deq. - Si la liste d’entrée est de la forme
x::qavecximpair, la liste de sortie est la liste des valeurs paires deq.
Exercice de découverte B.dec.x6
Complétez la spécification de la fonction gen telle que si n est un entier positif ou nul et x une valeur d’un type quelconque, alors gen n x retourne une liste contenant n occurrences de x.
Par exemple…
gen 4 7;;
…produit le résultat :
[7;7;7;7]
Voici le code à compléter :
let rec gen n x =
if n = 0 then (*À compléter*)
else (*À compléter*)
let rec gen n x =
if n = 0 then []
else x::(gen (n-1) x);;
Exercice de découverte B.dec.x7
Réalisez une fonction d telle que d w retourne true si w est une liste qui contient au moins deux valeurs identiques consécutives, et false sinon.
Voici quelques exemples :
d [2;5;3;3;3;1];; ---> true
d [2;5;3;3;1];; ---> true
d [2;5;3;1];; ---> false
Voici le code à compléter :
let rec d w =
match w with
|[] -> false
|[x] -> false
|a::b::q ->
(*À compléter*)
let rec d w =
match w with
|[] -> false
|[x] -> false
|a::b::q ->
if a = b then true
else d (b::q);;
B.dec4 : Fonctions d’ordre supérieur
On parle de fonction d’ordre supérieur lorsqu’au moins un des paramètres d’une fonction est une fonction.
Voici un exemple de fonction qui accepte en paramètre une fonction f et une liste w, qui retourne la somme des valeurs obtenues en appliquant f à chaque élément de w.
let rec sigma f w =
match w with
|[] -> 0
|x::q -> f x + sigma f q;;
Par exemple, si on spécifie une fonction h qui calcule le carré d’un entier…
let h x = x * x;;
…alors l’appel…
sigma h [1;2;3];;
…retourne la valeur (14), c’est à dire (1^2 + 2^2 + 3^2).
Le principe suivant est utilisé :
- Si la liste
west vide alors la valeur 0 est retournée. - Si la liste a une tête
xet une queueq, alors la valeur retournée est (happliquée àx) plus la somme des valeurs obtenues en appliquanthaux éléments deq.
Exercice de découverte B.dec.x8
On reprend la fonction longueur, vue dans une section précédente, qui calcule la longueur d’une liste.
let rec longueur w =
match w with
|[] -> 0
|x::q -> 1 + longueur q;;
On définit la liste de liste suivante :
let t = [[1;2];[7];[3;5;1]];;
Utilisez la fonction sigma pour calculer la somme des longueurs des listes situées dans la liste t.
sigma longueur t;;
Exercice de découverte B.dec.x9
Spécifiez une fonction fof telle que si h est une fonction de signature 'a -> 'a et x une valeur de type 'a, alors fof h x retourne la valeur obtenue en appliquant h deux fois de suite à x.
Par exemple, si h est la fonction qui à tout entier (x) associe (x^2)…
let h x = x * x;;
…alors fof h 2 retourne 16 (2 au carré au carré).
let fof h x =
h (h x);;
B.dec5 : Variantes et application aux arbres
Une variante est un type définit par compositions, possiblement récursives, de types existants.
Voici un exemple de définition d’un type btree permettant de représenter des arbres binaires dont les noeuds sont étiquetés par des entiers.
type btree = E | N of int * btree * btree;;
Un objet de type btree est :
- Soit
E, qui représente une feuille, - Soit
N(x,g,d), oùxest de typeint,getdde typebtree, qui représente un noeud étiqueté par l’entierxet ayantgpour fils gauche etdpour fils droit.
Voici un exemple de représentation d’un arbre binaire.

let t = N(5, N(3,E,E), E);;
Il faut bien comprendre que la syntaxe…
N of int * btree * btree
…dans la définition du type correspond à…
N({valeur de type int}, {valeur de type btree}, {valeur de type btree})
…lors de l’utilisation.
Voici un exemple de fonction qui vérifie si un entier x est une des étiquettes d’un arbre t.
let rec member x t =
match t with
|E -> false (*Ligne A*)
|N(y, left, right) ->
if x = y then true (*Ligne B*)
else if member x left then true (*Ligne C*)
else member x right;; (*Ligne D*)
- Ligne A : si
test une feuille, alorsxn’est danst. - Ligne B : si
ta une racine avec l’étiquettexalorsxest danst. - Ligne C : si
ta une racine avec un étiquette différente dexet quexest dans son fils gauche alorsxest danst. - Ligne D : sinon
xest danstsi et seulement si il est dans son fils droit.
Voici des exemples d’utilisation avec l’arbre t définit précédemment :
member 4 t;; ---> false
member 3 t;; ---> true
Exercice de découverte B.dec.x10
Définissez un type arbre permettant de représenter des arbres binaires dont les noeuds ne sont pas étiquetés et les feuilles sont étiquetées avec des entiers. Représentez avec ce type l’arbre suivant :

type arbre = F of int | N of arbre * arbre;;
let a = N(N(F(3),F(5)),F(8));;
Exercice de découverte B.dec.x11
Spécifiez une fonction sum permettant de calculer la somme des valeurs des feuilles d’un arbre du type défini dans l’exercice précédent.
let rec sum t =
match t with
|F(x) -> x
|N(g,d) -> (sum g) + (sum d);;
B.dec6 : Compléments
Instruction let in
Il peut être utile de placer dans une nouvelle variable le résultat d’un calcul qui pourra être utilisé plusieurs fois par la suite.
L’instruction let ... in permet de le faire, comme dans cet exemple de calcul du minimum d’une liste.
let rec min w =
match w with
|[] -> failwith "Erreur"
|[x] -> x
|t::q -> let m = min q in
if t < m then t else m;;
Si la liste comporte plusieurs éléments, on compare le premier au minimum de tous les éléments suivant, calculé par un appel récursif.
L’utilisation du let ... in n’a rien d’anecdotique. On peut réaliser le programme sans, mais au prix d’une perte d’efficacité à l’exécution.
La version de min présentée ci-dessus s’exécute en temps linéaire.
Mais la version ci-dessous, sans let ... in, s’exécute en temps exponentiel dans le pire des cas !
let rec min w =
match w with
|[] -> failwith "Erreur"
|[x] -> x
|t::q ->
if t < min q then t else min q;;
Exercice de découverte B.dec.x12
Comment faut-il ordonner les valeurs dans la liste pour que le deuxième version de min s’exécute en temps linéaire, et comment faut-il les ordonner pour qu’elle s’exécute en temps exponentiel ?
Si la liste est en ordre croissant, la fonction s’exécute en temps linéaire car chaque appel réalise un seul appel récursif.
Si la liste est en ordre décroissant, la fonction s’exécute en temps exponentiel car chaque appel réalise 2 appels récursifs distincts (pour calculer deux fois la même chose).
Variables modifiables
Ce qui est présenté rapidement ici sort du scope de cet enseignement mais peut avoir une utilité, par exemple pour compter le nombre d’appel récursifs lors de l’exécution d’une fonction. Voici un exemple avec la deuxième version de la fonction min vue précédemment.
let count = ref 0;; (*Ligne A*)
let rec min3 w =
( (*Ligne B*)
count := !count + 1; (*Ligne C*)
match w with
|[] -> failwith "Erreur"
|[x] -> x
|t::q ->
if t < min3 q then t else min3 q
);; (*Ligne D*)
min3 [6;5;4;3;2;1];; (*Ligne E*)
!count;; (*Ligne F*)
En ligne A, on déclare une variable globale count de type référence initialisée à 0. Le contenu de cette variable pourra changer au cours du temps.
En ligne B, on définit une séquence, qui se termine en ligne D, avec la syntaxe (bloc1; bloc2). Chaque bloc est évalué successivement. Le résultat de l’évaluation de la séquence est celui de l’évaluation de son dernier bloc. On peut avoir plus de deux blocs.
En ligne C, le premier bloc de la séquence récupère le contenu !count de la variable globale, lui ajoute 1 et place le résultat dans la variable. Le but est de compter le nombre d’appels de la fonction.
Entre les lignes C et D, on a le code de la fonction min présenté précédemment.
En ligne E, on appelle la fonction pour calculer le minimum d’une liste.
En ligne F, on affiche la valeur du compteur.
Le résultat de l’exécution est :
int = 1
int = 63
La première valeur est le résultat de l’appel à min, la deuxième est la valeur du compteur. On a réalisé 63 appels à la fonction pour calculer le minimum d’une liste de 6 valeurs.
Concaténation de listes
On peut spécifier une fonction récursive qui réalise la concaténation de deux listes. Cela sera laissé en exercice dans la partie entraînement.
Mais CAML dispose d’un opérateur de concaténation de liste représenté par le symbole @. Cet exemple…
[1;3] @ [5;7];;
…produit le résultat :
list = [1;3;5;7]
Activité d’entraînement B.ent
Cette activité est essentielle. C’est grâce à elle que vous apprendrez vraiment à comprendre et utiliser les notions vues précédemment. Elle se décompose en deux itérations : ent1, ent2. Vous devez réaliser au moins une itération et évaluer votre niveau de réussite.
Si vous avez eu beaucoup de difficulté à traiter les exercices et fait beaucoup d’erreurs, vous devrez traiter à nouveau l’activité de découverte précédente, en laissant passer au moins une nuit, avant de revenir à cette activité d’entraînement en réalisant à nouveau la première l’itération. Vous devez aussi essayer d’identifier les points de blocage et demander à votre enseignant de vous aider à les surmonter.
Si vous avez réussi certains exercices, mais échoué à d’autres, vous devrez d’abord comprendre ce qui vous a conduit à des erreurs et / ou ce qui vous a bloqué. Si vous avez des doutes, des difficultés, essayez de trouver les réponses dans les présentations et explications de l’activité de découverte et demandez toute l’aide nécessaire à votre enseignant. Ensuite, vous devrez réaliser l’itération suivante après au moins une nuit de sommeil et au plus une semaine.
Si vous avez réussi presque tous les exercices et que vos rares erreurs sont dues à l’inattention, vous devriez revenir traiter l’itération suivante après un délai de plusieurs semaines.
Si besoin, après avoir traité la deuxième itération, vous pouvez revenir à la première. Vous pouvez aussi traiter des annales d’évaluations de l’unité d’enseignement.
Itération B.ent1
Exercice d’entrainement B.ent1.1
Spécifiez la fonction why telle que si x est un entier positif alors why x retourne la valeur de la somme 1 + 2 + 3 + ... + x.
let rec why x =
if x <= 1 then 1
else (*À compléter*)
;;
let rec why x =
if x <= 1 then 1
else x + why (x-1)
;;
Exercice d’entrainement B.ent1.2
Spécifiez une fonction at qui, appliquée à une liste w et un entier i positif ou nul, retourne l’élément situé en position i dans w. Les positions sont numérotées à partir de 0. On suppose que i est compris entre 0 et la longueur de w moins 1.
let s = [3;5;6;7;7];;
at s 2;; ---> 6
let rec at w i =
match w with
|[] -> failwith "Erreur"
|x::q ->
if i = 0 then (*À compléter*)
else (*À compléter*)
;;
let rec at w i =
match w with
|[] -> failwith "Erreur"
|x::q ->
if i = 0 then x
else at q (i-1)
;;
Exercice d’entrainement B.ent1.3
Spécifiez la fonction add qui, appliquée à une liste w d’éléments d’un type quelconque 'a et à une valeur x de type 'a, retourne la liste obtenue en ajoutant x à la fin de w. Vous ne devez pas utiliser l’opérateur de concaténation @.
add [1;2;4] 7;; ---> [1;2;4;7]
let rec add w x =
match w with
|[] -> [x]
|t::q -> (*À compléter*)
;;
let rec add w x =
match w with
|[] -> [x]
|t::q -> t :: (add q x)
;;
Exercice d’entrainement B.ent1.4
Spécifiez la fonction pref qui, appliquée à une liste p et une liste w, retourne true si et seulement si la liste p est un préfixe de la liste w, c’est à dire si w commence par p ou si p est vide.
pref [1;2;3] [1;2;3;4;5];; ---> true
perf [1;2;2] [1;2;3;4;5];; ---> false
let rec pref p w =
match p with
|[] -> true (*Ligne A*)
|tp::qp -> (*Ligne B*)
match w with
|[] -> (*À compléter*)
|tw::qw ->
(*À compléter*)
;;
La liste vide est un préfixe de n’importe quelle liste (ligne A).
Si la, liste p n’est pas vide (ligne B), alors il faut, pour que p soit préfixe de w, que w ne soit pas vide et que w commence par le même élément que p et que la queue de p soit un préfixe de la queue de w.
let rec pref p w =
match p with
|[] -> true
|tp::qp ->
match w with
|[] -> false
|tw::qw ->
if tw = tp then
pref qp qw
else
false
;;
Exercice d’entrainement B.ent1.5
On utilise le type btree définit plus haut.
type btree = E | N of int * btree * btree;;
Spécifiez la fonction sz qui, appliquée à un arbre t de type btree, retourne le nombre de noeuds de t.
let rec sz t =
match t with
|E -> 0
|N(x,g,d) ->
(*À compléter*)
;;
let rec sz t =
match t with
|E -> 0
|N(x,g,d) ->
(sz g) + (sz d) + 1
;;
Exercice d’entrainement B.ent1.6
On utilise le type btree définit plus haut.
type btree = E | N of int * btree * btree;;
On appelle chemin une suite de noeuds qui part de la racine et aboutit à une feuille. On définit le poids d’un chemin comme la somme des valeurs de ses noeuds.
Voici un exemple d’arbre avec les poids de ses chemins.

Spécifiez la fonction maxPath qui, appliquée à un arbre t, retourne le poids d’un chemin de t de poids maximum. Dans le cas de l’exemple, la valeur est 20.
let rec maxPath t =
match t with
|E -> 0
|N(x,g,d) ->
let p1 = maxPath g in
let p2 = maxPath d in
(*À compléter*)
;;
let rec maxPath t =
match t with
|E -> 0
|N(x,g,d) ->
let p1 = maxPath g in
let p2 = maxPath d in
if p1 > p2 then x + p1
else x + p2
;;
Exercice d’entrainement B.ent1.7
On utilise le type tree suivant, qui représente des arbres dont les feuilles sont étiquetées par des entiers et les noeuds ne sont pas étiquetés.
type tree = F of int | N of tree * tree;;
Voici un exemple :
let a = N(N(F 3, F 5),N(N(F 1, F 2), N(F 2, F 7)));;

Spécifiez la fonction collect qui, appliquée à un arbre t, retourne la liste des valeurs des étiquettes des feuilles. Avec l’exemple, cela donne la liste [3;5;1;2;2;7]. Vous pouvez utiliser l’opérateur de concaténation @.
let rec collect t =
match t with
|F x -> [x]
|N(g,d) ->
(*À compléter*)
;;
let rec collect t =
match t with
|F x -> [x]
|N(g,d) ->
(collect g) @ (collect d)
;;
Exercice d’entrainement B.ent1.8
Définissez un type ubtree permettant de représenter des arbres ayant des feuilles, des noeuds unaires et des noeuds binaires. Les noeuds et les feuilles ne sont pas étiquetées.
Voici un exemple d’arbre de type ubtree…

…et sa représentation :
let y = U( B( U(F), U(B(F,F)) ) );;
Vous devez spécifier deux fonctions :
countb t: retourne le nombre de noeuds binaires det.lmax t: retourne la longueur du plus long chemin (entre la racine et une feuille) de t.
Voici la définition du type :
type ubtree = F | U of ubtree | B of ubtree * ubtree;;
let rec countb t =
match t with
|F -> 0
|U f -> countb f
|B(g,d) -> 1 + (countb g) + (countb d)
;;
let rec lmax t =
match t with
|F -> 0
|U f -> (lmax f) + 1
|B(g,d) ->
let m1 = lmax d in
let m2 = lmax g in
if m1>m2 then m1+1
else m2+1
;;
Itération A.ent2
Exercice d’entrainement B.ent2.1
Spécifiez la fonction divdiv2 qui à tout entier x positif associe l’entier obtenu en divisant x par 2 autant de fois que nécessaire pour obtenir une valeur impaire.
divdiv 2 7;; ---> 7
divdiv 2 10;; ---> 5
divdiv 2 320;; ---> 7
let rec divdiv2 x =
if(x mod 2 != 0) then x
else (*À compléter*)
;;
let rec divdiv2 x =
if(x mod 2 != 0) then x
else divdiv2 (x/2)
;;
Exercice d’entrainement B.ent2.2
Spécifiez une fonction gen qui, appliquée à un entier positif a et une entier b supérieur ou égal à a, retourne la liste des entiers compris entre a et b.
gen 1 4;; ---> [1;2;3;4]
let rec gen a b =
if a = b then [a]
else (*À compléter*)
;;
let rec gen a b =
if a = b then [a]
else a :: gen (a+1) b
;;
Exercice d’entrainement B.ent2.3
Spécifiez une fonction miroir qui, appliquée à une liste w, retourne la liste miroir de w, c’est à dire comportant les mêmes éléments dans l’ordre inverse.
miroir [1;2;3;4];; ---> [4;3;2;1]
Vous pouvez utiliser l’opérateur de concaténation @.
let rec miroir w =
match w with
|[] -> []
|x::q -> (*À compléter*)
;;
let rec miroir w =
match w with
|[] -> []
|x::q -> (miroir q) @ [x]
;;
Exercice d’entrainement B.ent2.4
Spécifiez la fonction concat qui, appliquée à une liste a et une liste b, retourne la liste obtenue par concaténation de a et b. Vous ne devez pas utiliser l’opérateur de concaténation @. Vous ne devez pas appeler d’autre fonction.
concat [1;2] [3;4];; ---> [1;2;3;4]
let rec concat a b =
match a with
|[] -> b
|ta::qa ->
(*À compléter*)
;;
Si a est vide alors le résultat est b. Dans le cas contraire, quel est le premier élément du résultat ? Comment obtenir la queue du résultat ?
let rec concat a b =
match a with
|[] -> b
|ta::qa ->
ta :: (concat qa b)
;;
Exercice d’entrainement B.ent2.5
On utilise le type btree définit plus haut.
type btree = E | N of int * btree * btree;;
Spécifiez la fonction nf qui, appliquée à un arbre t de type btree, retourne le nombre de feuilles de t.
let rec nf t =
match t with
|E -> 1
|N(x,g,d) ->
(*À compléter*)
;;
let rec nf t =
match t with
|E -> 1
|N(x,g,d) ->
(nf g) + (nf d)
;;
Exercice d’entrainement B.ent2.6
On utilise le type tree suivant, qui représente des arbres dont les feuilles sont étiquetées par des entiers et les noeuds ne sont pas étiquetés.
type tree = F of int | N of tree * tree;;
Voici un exemple :
let a = N(N(F 3, F 5),N(N(F 1, F 2), N(F 2, F 7)));;

Spécifiez la fonction minLeaf qui, appliquée à un arbre t, retourne la plus petite valeur d’une feuille. Dans le cas de l’exemple, la valeur est 1.
let rec minLeaf t =
match t with
|F x -> (*À compléter*)
|N(g,d) ->
let m1 = minLeaf g in
let m2 = minLeaf d in
(*À compléter*)
;;
let rec minLeaf t =
match t with
|F x -> x
|N(g,d) ->
let m1 = minLeaf g in
let m2 = minLeaf d in
if m1 > m2 then m2
else m1
;;
Exercice d’entrainement B.ent2.7
On utilise le type btree définit ainsi.
type btree = E | N of int * btree * btree;;
La liste des noeuds d’un arbre en ordre préfixe est constituée le l’étiquette racine, suivie de la liste des noeuds du fils gauche en ordre préfixe, suivie de la liste des noeuds du fils droit en ordre préfixe.
Dans le cas de l’arbre suivant…

…on obtient la liste [5;15;2;3;5].
Spécifiez la fonction prefx qui, appliquée à un arbre t, retourne la liste de ses noeuds en ordre préfixe.
let rec prefx t =
match t with
|E -> []
|N(x,g,d) ->
x :: (prefx g) @ (prefx d)
;;
Exercice d’entrainement B.ent2.8
On s’intéresse aux arbres constitués de noeud étiquetés par des entiers pouvant avoir aucun, un ou plusieurs fils. On les représente avec le type suivant. Les noeuds n’ayant aucun fils jouent le rôle des feuilles.
type nTree = L of int * nTree list;;
Voici un exemple d’un tel arbre…

…et sa représentation :
let q = L(5,[ L(7,[L(0,[]);L(0,[])]); L(3,[L(0,[])]); L(0,[]) ]);;
Spécifiez une fonction sumt qui, appliquée à un arbre t de type nTree, retourne la somme des valeurs des étiquettes de cet arbre.
let rec sumt tr =
match tr with
|L(x,[]) -> x
|L(x,t::q) ->
(*À compléter*)
;;
On distingue deux cas :
- L’arbre est une feuille d’étiquette
x. Dans ce cas, la somme des valeurs de ses étiquettes estx. - L’arbre a pour racine un noeud d’étiquette
xayant une liste de fils. Cette liste peut être décomposée en une têtet, qui est un arbre, et une queueq, qui est une liste d’arbres. Le résultat sera la somme dex, des valeurs det, et de la somme des valeurs de tous les arbre de la listeq, qui est aussi la somme des valeurs de l’arbreL(0,q).
let rec sumt tr =
match tr with
|L(x,[]) -> x
|L(x,t::q) ->
let s1 = sumt t in
let s2 = sumt (*À compléter*) in
(*À compléter*)
;;
let rec sumt tr =
match tr with
|L(x,[]) -> x
|L(x,t::q) ->
let s1 = sumt t in
let s2 = sumt (L(0,q)) in
s1 + s2 + x
;;
Le terme L(0,q) doit être mis entre parenthèses pour qu’il ne soit pas interprété comme L appliqué à (0,q).
Activité B.top
Cette activité propose des exercices de consolidation qui ne doivent être abordés que par les personnes apprenantes maîtrisant bien la partie A et les parties suivantes disponibles.
Par exemple, si les parties actuellement disponibles sont A et B, vous devez d’abord maîtriser la parie B avant de faire cette activité de consolidation de la partie A.
B.top1
Exercice de consolidation B.top1
Vous devez spécifier une fonction tri qui, appliquée à une liste d’entiers w, retourne la liste des éléments de w triés en ordre croissant.
Exemple d’utilisation :
tri [17;5;1;45;2;1;3;24];; ---> [1;1;2;3;5;17;24;45]
Le tri réalisé doit être basé sur le principe suivant :
- Chaque élément de la liste à trier est inséré dans un arbre binaire trié.
- L’arbre trié est converti e n liste.
Un arbre binaire trié est un arbre binaire dont les noeuds sont étiquetés par des entiers, dont les feuilles n’ont pas d’étiquette, et qui a les propriété suivantes.
- Toutes les étiquettes du fils gauche d’un arbre trié sont au plus égales à l’étiquette de sa racine.
- Toutes les étiquettes de son fils droit sont supérieures à l’étiquette de sa racine.
- Les sous arbres d’un arbre binaire trié sont des arbres binaires triés.
Voici un exemple du processus de tri d’une liste.

Vous devez décomposer votre solution en plusieurs fonctions. L’utilisation de l’opérateur de concaténation @ est autorisée.
On crée un type :
type stree = L | N of int * stree * stree;;
On peut décomposer le programme en 4 fonctions :
insert x t, oùxest un entier ettun arbre trié : retourne l’arbre trié obtenu en insérantxdanst.list2tree w: retourne l’arbre trié comportant tous les éléments de la listew.tree2list t: retourne la liste croissante des valeurs des étiquettes de l’arbre triét.tri w: retourne la liste triée des éléments de la listew.
Voici une version à compéter de la fonction insert.
let rec insert x t =
match t with
|L -> N(x,L,L)
|N(y,g,d) ->
if x<=y then (*À compléter*)
else N (*À compléter*)
;;
Le principe est le suivant :
- Si
test une feuille, alors l’arbre produit a une racine de valeurxet deux feuilles. - Sinon, si
xest inférieur ou égale à la valeuryde la racine det, on retourne un arbre avec la même raciney, le même sous arbre droit, mais un sous arbre gauche dans lequelxa été inséré par un appel récursif. - Sinon, on retourne un arbre avec la même racine
y, le même sous arbre gauche, mais un sous arbre droit dans lequelxa été inséré par un appel récursif.
Voici la fonction insert complète et des versions incomplètes des fonctions list2tree et tree2list.
let rec insert x t =
match t with
|L -> N(x,L,L)
|N(y,g,d) ->
if x<=y then N(y,(insert x g),d)
else N(y,g,(insert x d))
;;
let rec list2tree w =
match w with
|[] -> L
|x::q -> (*À compléter*)
;;
let rec tree2list t =
match t with
|L -> []
|N(x,g,d) ->
(*À compléter*)
;;
Dans list2tree, on construit une arbre en insérant la tête de w dans l’arbre trié contenant les éléments de la queue de w.
type stree = L | N of int * stree * stree;;
let rec insert x t =
match t with
|L -> N(x,L,L)
|N(y,g,d) ->
if x<=y then N(y,(insert x g),d)
else N(y,g,(insert x d))
;;
let rec list2tree w =
match w with
|[] -> L
|x::q -> insert x (list2tree q)
;;
let rec tree2list t =
match t with
|L -> []
|N(x,g,d) ->
(tree2list g) @ x::(tree2list d)
;;
let tri w =
tree2list (list2tree w)
;;
B.top2
Exercice de consolidation B.top2
On définit un type…
type ntree = N of ntree list;;
…qui permet de représenter des arbres sans étiquette dont chaque noeud possède un nombre arbitraire de fils.
N([]) représente une feuille. On peut se dispenser des parenthèses et écrire N[] pour une meilleure lisibilité.
Voici une exemple d’arbre de type ntree…

…et sa représentation :
let tt = N[ N[N[];N[]]; N[N[]]; N[] ];;
On définit également le type…
type bintree = E | F | B of bintree * bintree;;
…qui représente un arbre binaire non étiqueté avec deux sortes de feuilles identifiées par les symboles E et F.
On peut établir une correspondance bijective entre les deux représentations comme indiqué dans cet exemple :

Vous devez spécifier la fonction n2bin qui traduit un arbre de type ntree en un arbre de type bintree et la fonction bin2n qui fait la traduction dans l’autres sens.
Attention, tout terme de type ntree doit pouvoir être traduit en type bintree, mais certains termes de type bintree ne correspondent à aucun arbre valide de type ntree.
Par exemple, le terme E ne correspond à aucun arbre de type ntree. Le symbole E sert uniquement à terminer le chaînage des fils droits des noeuds binaires dont les fils gauches correspondent à des fils de l’arbre de type ntree correspondant. Référez vous à l’exemple ci-dessus.
De même, le fils droit d’un noeud binaire d’un arbre de type bintree représentant un arbre de type ntree ne peut jamais être le terme F.
Commencez par la fonction n2bin qui est plus facile.
Le principe de n2bin est le suivant :
N[]se traduit enF.N[u], un arbre dont la racine a un fils unique u, se traduit enB({traduction de u}, E).- La traduction de
N(h::q), un arbre dont la racine a au moins 2 fils, a pour fils gauche la traduction dehet pour fils droit… pas la traduction deqcarqest une liste de termes de typentreeet pas un terme de typentree. Il y a une subtilité. Siq = [ N[N[]]; N[] ], c’estN[ N[N[]]; N[] ]qu’il faut traduire.
Voici la spécification de n2bin.
let rec n2bin t =
match t with
|N[] -> F
|N[u] -> B(n2bin u, E)
|N(h::q) -> B(n2bin h, n2bin (N q))
;;
Vous devez maintenant spécifier bin2n, qui est plus difficile. Examinons quelques cas sur lesquels vous pouvez vous appuyer.
bin2n E;; ---> (*Impossible, ne correspond à aucun terme de type ntree*)
bin2n F;; ---> N[]
bin2n (B(F,E)) ---> N[N[]]
bin2n (B( B(F,E), B(F,E) )) ---> N[ N[N[]] ; N[] ]

let rec bin2n t =
match t with
|E -> failwith "Erreur"
|F -> N[]
|B(g,E) -> (*À compléter*)
|B(g,d) ->
let t1 = bin2n g in
let t2 = bin2n d in
match t2 with
|N[] -> failwith "Erreur"
|N(h::q) -> (*À compléter*)
;;
type ntree = N of ntree list;;
type bintree = E | F | B of bintree * bintree;;
let rec n2bin t =
match t with
|N[] -> F
|N[u] -> B(n2bin u, E)
|N(h::q) -> B(n2bin h, n2bin (N q))
;;
let rec bin2n t =
match t with
|E -> failwith "Erreur"
|F -> N[]
|B(g,E) -> N[bin2n g]
|B(g,d) ->
let t1 = bin2n g in
let t2 = bin2n d in
match t2 with
|N[] -> failwith "Erreur"
|N(h::q) -> N(t1::h::q)
;;
let tt = N[ N[N[];N[]]; N[N[]]; N[] ];;
n2bin tt;;