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 abs la fonction qui à x associe -x si x < 0, sinon x.

(* Version 2*)
let abs x =
  if x < 0 then
    -x
  else
    x ;;

Soit abs la fonction qui, appliquée à x retourne -x si x < 0, sinon x.

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 :

abs est une fonction qui à tout entier (type int) 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 / 2 si x est pair,
  • 3 * x + 1 si x est impair.

Donnez une spécification de la fonction syr en CAML. L’opérateur modulo s’écrit mod.

Réponse

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.

Réponse

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 :

sum est 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 10 est d’abord évalué, et le résultat est une fonction qui à tout entier b associe 10 + 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.

Réponse

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;;
Réponse

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.

Réponse

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.

Réponse

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::q avec x pair, la liste de sortie a pour tête x et pour queue les valeurs paires de q.
  • Si la liste d’entrée est de la forme x::q avec x impair, la liste de sortie est la liste des valeurs paires de q.
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*)
Réponse

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*)
Réponse

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 w est vide alors la valeur 0 est retournée.
  • Si la liste a une tête x et une queue q, alors la valeur retournée est (h appliquée à x) plus la somme des valeurs obtenues en appliquant h aux éléments de q.
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.

Réponse

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

Réponse

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ù x est de type int, g et d de type btree, qui représente un noeud étiqueté par l’entier x et ayant g pour fils gauche et d pour fils droit.

Voici un exemple de représentation d’un arbre binaire.

image-20220108211639463

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 t est une feuille, alors x n’est dans t.
  • Ligne B : si t a une racine avec l’étiquette x alors x est dans t.
  • Ligne C : si t a une racine avec un étiquette différente de x et que x est dans son fils gauche alors x est dans t.
  • Ligne D : sinon x est dans t si 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 :

image-20220108214914615

Réponse

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.

Réponse

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 ?

Réponse

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.

Indice

let rec why x =
  if x <= 1 then 1
  else (*À compléter*)
;;

Solution

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
Indice

let rec at w i =
  match w with
  |[] -> failwith "Erreur"
  |x::q ->
      if i = 0 then (*À compléter*)
      else (*À compléter*)
;;

Réponse

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] 
Indice

let rec add w x =
  match w with
  |[] -> [x]
  |t::q -> (*À compléter*)
;;

Réponse

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
Indice

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.

Réponse

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.

Indice

let rec sz t =
  match t with
  |E -> 0
  |N(x,g,d) ->
      (*À compléter*)
;;

Réponse

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.

image-20220109173222250

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.

Indice

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*)
;;

Réponse

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

image-20220109175448506

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

Indice

let rec collect t =
  match t with
  |F x -> [x]
  |N(g,d) ->
  (*À compléter*)    
;;

Réponse

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…

image-20220109190400879

…et sa représentation :

let y = U( B( U(F), U(B(F,F)) ) );;

Vous devez spécifier deux fonctions :

  1. countb t : retourne le nombre de noeuds binaires de t.
  2. lmax t : retourne la longueur du plus long chemin (entre la racine et une feuille) de t.
Indice1

Voici la définition du type :

type ubtree = F | U of ubtree | B of ubtree * ubtree;;

Réponse1

let rec countb t =
  match t with
  |F -> 0
  |U f -> countb f
  |B(g,d) -> 1 + (countb g) + (countb d)
;;

Réponse2

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
Indice

let rec divdiv2 x =
  if(x mod 2 != 0) then x
  else (*À compléter*)
;;

Réponse

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]
Indice

let rec gen a b =
  if a = b then [a]
  else (*À compléter*)
;;

Réponse

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

Indice

let rec miroir w =
  match w with
  |[] -> []
  |x::q -> (*À compléter*)
;;

Réponse

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]
Indice

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 ?

Réponse

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.

Indice

let rec nf t =
  match t with
  |E -> 1
  |N(x,g,d) ->
      (*À compléter*)
;;

Réponse

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

image-20220109175448506

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.

Indice

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*)
;;

Réponse

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…

image-20220109183520020

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

Réponse

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…

image-20220109203846492

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

Indice1

let rec sumt tr =
  match tr with
  |L(x,[]) -> x
  |L(x,t::q) ->
      (*À compléter*)
;;

On distingue deux cas :

  1. L’arbre est une feuille d’étiquette x. Dans ce cas, la somme des valeurs de ses étiquettes est x.
  2. L’arbre a pour racine un noeud d’étiquette x ayant une liste de fils. Cette liste peut être décomposée en une tête t, qui est un arbre, et une queue q, qui est une liste d’arbres. Le résultat sera la somme de x, des valeurs de t, et de la somme des valeurs de tous les arbre de la liste q, qui est aussi la somme des valeurs de l’arbre L(0,q).

Indice2

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*)
;;

Réponse

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 :

  1. Chaque élément de la liste à trier est inséré dans un arbre binaire trié.
  2. 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.

image-20220111130220492

Vous devez décomposer votre solution en plusieurs fonctions. L’utilisation de l’opérateur de concaténation @ est autorisée.

Indice1

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ù x est un entier et t un arbre trié : retourne l’arbre trié obtenu en insérant x dans t.
  • list2tree w : retourne l’arbre trié comportant tous les éléments de la liste w.
  • 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 liste w.

Indice2

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 t est une feuille, alors l’arbre produit a une racine de valeur x et deux feuilles.
  • Sinon, si x est inférieur ou égale à la valeur y de la racine de t, on retourne un arbre avec la même racine y, le même sous arbre droit, mais un sous arbre gauche dans lequel x a é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 lequel x a été inséré par un appel récursif.

Indice3

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.

Solution

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…

image-20220112090453565

…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 :

image-20220112093042081

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.

Indice1

Le principe de n2bin est le suivant :

  • N[] se traduit en F.
  • N[u], un arbre dont la racine a un fils unique u, se traduit en B({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 de h et pour fils droit… pas la traduction de q car q est une liste de termes de type ntree et pas un terme de type ntree. Il y a une subtilité. Si q = [ N[N[]]; N[] ], c’est N[ N[N[]]; N[] ] qu’il faut traduire.

Indice2

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[] ]

image-20220112115940566

Indice3

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*)
;;

Solution

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