Exercices

abstraction concrète

Exercice 1

Rechercher pourquoi les identificateurs suivants ne sont pas valides.
1_un
_deux
'trois
8A
carre d'as
function
then.
Solution

Manuel : Identificateurs


Exercice 2

Soit une session Caml dans un environnement Ei, on effectue les définitions suivantes :
1. # let a = 30;; 
2. # let b = a + 20;; 
3. # let a = b + 5;; 
4. # a;; 
5. # b;; 
6. # let c = 8 in c * c + a + b;; 
7. # let a = 2 in a * a + a * b + b;; 
Décrire l'environnement à chaque définition. Quelles sont les valeurs associées aux identificateurs a, b et c, après la dernière définition ?

Solution

Manuel : Type et valeur des expressions
Manuel : Définitions et environnement


Exercice 3

Depuis l'environnement Eo, on entre la phrase Caml suivante :
#let taux = 2 in 
   let alpha = 5 in 
     let coef = taux * alpha + alpha in 
       taux * alpha + coef * alpha ;;  
Décrire le nouvel environnement. Quel est le résultat affiché ?

Solution

Manuel : Type et valeur des expressions
Manuel : Définitions et environnement


Exercice 4

Au cours d'une session Caml, dans un environnement Env, on effectue les deux définitions suivantes :
1. # let a = 
       let a = 3 and b = 2 in 
         let a = a + b and b = a - b in a * a - b * b ;; 
2. # let b = 2 in a * a + a * b + b;;
Qu'affiche le système interactif après chaque évaluation ?

Solution

Manuel : Type et valeur des expressions
Manuel : Définitions et environnement


Exercice 5

Typer les expressions Caml suivantes :
1. (c + 4) <= (8 - x) 
2. ("a" ^ "b") = c
3. (4 < 8) = ("a" = "b")
4. ("a" + 5) = ("a" + 5)
Solution

Type et valeur des expressions
Définitions et environnement


Exercice 6

En utilisant les définitions emboîtées en Caml, et avec x=5, calculer l'expression mathématique :
A = x5 - 2x4 + 3x3 - 4x2 + 5x - 6


Solution

Définitions et environnement


Exercice 7

Dans un environnement Eo, on effectue la définition :
 #let taux = 2 in 
   let alpha = 5 in  
     let coef = taux * alpha + alpha in  
       let a = taux * alpha + coef * alpha;; 
Décrire le nouvel environnement. Quel est le résultat affiché ?

Solution

Type et valeur des expressions
Définitions et environnement


Exercice 8

Au cours d'une session Caml, E est l'environnement initial.
Typer, évaluer les phrases Caml suivantes et indiquer l'environnement résultant :
1. # let a = 5 ;; 
2. # let a = a + a ;; 
3. # let v = (a = 10) ;; 
4. # let f = function x -> x*x + a*a ;; 
5. # f 2 ;; 
6. # f f 2 ;; 
7. # let rec h = function  
		0 -> 1  
	|	1 -> 1  
	|	n -> (f(n-2) + 1) * f(n-1) ;; 
8. # h 7 ;; 
9. # let gamma = 
       function a -> function b -> a*b ;; 
10.# let z = gamma 5 ;; 
11.# gamma 8 4 ;; 
12.# z (z 2) ;;  
Solution

Type et valeur des expressions
Définitions et environnement
Fonctions


Exercice 9

Typer, évaluer les phrases Caml suivantes :
1. # let Y = function x -> function y -> function z -> y ;; 
2. # let H = function u -> function x -> u x x ;;
3. # H (function x -> fun y -> x+y) 4 ;;
Solution

Type et valeur des expressions
Définitions et environnement
Fonctions


Exercice 10

Au cours d'une session Caml, Env est l'environnement initial, et les définitions suivantes sont effectuées :
1)#let a = 5 ;; 
2)#let b = 3 ;; 
3)#a,b ;; 
4)#let alpha x   = let a = 2 in a * x + b ;; 
5)#alpha 7 ;; 
6)#let béta  x   = let b = 2 in a * x + b ;; 
7)#béta 7 ;; 
8)#let gamma a b = let x = 7 in a * x + b ;; 
9)#gamma a b ;; 
10)#let a,b,x = 2,1,3 ;; 
11)#alpha x , béta x , gamma a b ;;  
1) Evaluer et typer chacune des définitions
2) Décrire l'évolution de l'environnement à chaque étape
3) Décrire les fermetures des fonctions

Solution

Type et valeur des expressions
Définitions et environnement
Fonctions


Exercice 11

Typer et évaluer les définitions Caml suivantes :
1) #let h = function f -> function g -> g f ;; 
2) #let x = h 4 ;;
3) #let t = h 4 (function x -> x + 2) ;;
Solution

Type et valeur des expressions
Définitions et environnement
Fonctions


Exercice 12

Déclarer les fonctions suivantes en Caml :
1. Fonction suivant : à un nombre entier n on fait correspondre l'entier (n+1)
2. Fonction precedent : à un nombre entier n on fait correspondre l'entier (n-1)
3. Fonction double : à un nombre entier n on fait correspondre l'entier 2*n

Solution

Définitions et environnement
Fonctions


Exercice 13

Construire, en Caml, la fonction base permettant de calculer la valeur de base de décompte selon la règle de gestion :
Si le plafond est inférieur au salaire,
alors la base de décompte est égale au plafond,
sinon la base de décompte est égale au salaire.
Syntaxe = base salaire plafond
Typage = base : int -> int -> int

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions


Exercice 14

Ecrire, en Caml, une fonction int_of_base, du type : int -> string -> int.
L'application(int_of_base n s) reçoit deux arguments :
- un entier n indiquant la base du nombre représenté par s
- et une chaîne de caractères s représentant un nombre en base n,
et renvoie un entier, le nombre représenté par s (en base n) converti en base 10.

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions


Exercice 15

Ecrire, en Caml, une fonction base_of_int, du type : int -> int -> string.
L'application(base_of_int n x) reçoit deux arguments :
- un entier n indiquant la base du nombre à retourner par la fonction
- et un entier x correspondant à un nombre en base 10, à convertir en base n,
et renvoie une chaîne de caractères représentant le nombre x en base n.

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions


Exercice 16

Ecrire, en Caml, une fonction convbase, du type : int -> int -> string -> string.
L'application(convbase b1 b2 s) reçoit 3 arguments :
- un entier b1 indiquant la base du nombre représenté par s
- un entier b2 indiquant la base du nombre à retourner par la fonction
- et une chaîne de caractères s représentant un nombre en base b1,
et renvoie une chaîne de caractères représentant le nombre s en base b2.

Solution

Type et valeur des expressions
Expressions conditionnelles
Fonctions


Exercice 17

Au cours d'une autre session Caml, examiner la définition suivante, et indiquer si le filtrage est exhaustif,
1. # let rec h = function 
		(5,_) -> 0 
	|	(_,5) -> 1 
	|	(x,9) -> x 
	|	(x,y) -> y ;; 
Dans la suite de la même session indiquer le type et la valeur des expressions :
2. # h(5,5), h(0,5), h(5,9), h(9,5) ;; 
3. # h(9,4), h(4,9), h(11,9), h(7,8) ;; 
4. # h(h(5,9),h(9,9)), h(h(9,7),h(5,9)) ;;  
Solution

Fonctions
Le filtrage


Exercice 18

Soit une session Caml dans un environnement E, typer et évaluer les phrases suivantes :
1. # let a = 80;; 
2. # let b = a + 20;; 
3. # let a = b + 50 in a + a * 3 ;; 
4. # let a = let b = 50 in a + b * 3 
     and b = let b = 50 in let a = 20 in a + b * 3 ;; 
5. # let c = 8 in c * c + a + b;; 
Solution

Type et valeur des expressions
Définitions et environnement


Exercice 19

Typer et évaluer les phrases Caml suivantes :
1. # (17 + 4*7) <= (58 - 3*12) ;; 
2. # ("a" ^ "b"), (5+2) = 7, 0 ;; 
3. # function x -> (4 < x) = ("a" = "b") ;; 
4. # ("a" + 5) = ("a" + 5) ;; 
5. # (function x -> snd(x)), (function x -> fst(x)) ;; 
6. # let f = function (x,y) -> y*y ;; 
7. # let g = function (a,b,u) -> u(b,a) ;; 
8. # g (0,5,f) ;; 
9. # function _ -> 0 ;; 
10.# function x -> (function f -> f(x)) ;; 
Solution

Type et valeur des expressions
Définitions et environnement
Le type produit vectoriel
Fonctions


Exercice 20

En utilisant les fonctions pré définies string_length et sub_string, construire les fonctions de chaînes de caractères suivantes :

hd_str : string -> string
hd_str s renvoie la chaîne formée par le premier caractère de la chaîne s fournie en argument, si s est la chaine vide, le résultat est la chaîne vide.

tl_str : string -> string
tl_str renvoie la chaîne formée par tous les caractères de la chaîne s fournie en argument, sauf le premier, si la chaîne fournie en argument est vide, le résultat est la chaîne vide.

A partir des fonctions hd_str et tl_str imaginer une fonction renverse :
renverse s : string -> string
renverse s renvoie la chaîne s fournie en argument, renversée.
Par exemple, renverse "abcd" renvoie "dcba".

En utilisant la fonction renverse définir la fonction est_palindrome :
est_palindrome : string -> bool
est_palindrome s renvoie true si la chaîne s fournie en argument est un palindrome, false sinon.

Solution

Fonctions
La récursivité
Le filtrage
Le type somme


Exercice 21

Dans un programme Caml on définit un type nombre qui regroupe des valeurs entières, réelles et complexes (les nombres complexes seront représentés comme des couples de nombres réels).
a) Construire une définition du type nombre en Caml.
b) Définir une fonction carré à un arguments, permettant de calculer le carré du nombre fourni en argument avec le type nombre :
syntaxe = carré x
typage = carré : nombre -> nombre
Règles de calcul appliquées : (les expressions suivantes ne sont pas des expressions Caml)
R1 : Le carré d'un entier m est un entier = m2
R2 : Le carré d'un réel x est un réel = x2
R3 : Le carré d'un complexe (a,b) est un complexe = (a2-b2, 2ab)

Solution

Fonctions
Le filtrage


Exercice 22

Un centre de formation propose des formations donnant lieu à des stages :
Une formation est représentée en Caml par une paire dont le premier élément est son numéro de code formation (entier), et son deuxième élément : un enregistrement défini par :
- un intitulé de la formation (libellé de 25 caractères),
- un nombre de séances de formation,
- un niveau de progression, représenté par un littéral : Initiation ou Perfectionnement,
- le nombre maximum de stagiaires,
et le tarif de formation (nombre réel).
1) Définir les types de données niveau_de_progression et formation.
2) La journée de travail est découpée en deux sessions : la session du matin et la session de l'après-midi.
Chaque séance de stage mobilise une session complete, soit le matin , soit l'après-midi.
La session est simplement représentée par un littéral : MATIN ou APRES_MIDI.
Une séance de stage est définie par :
la date de la séance, la session, le code salle de formation affectée à la séance (les salles ont un code formé par la lettre correspondant au batiment A ou B, suivie d'un simple numéro de salle).
Un stage correspondant à une formation programmée dans un calendrier, il est défini par :
le code du stage : numéro du stage dans l'année, le code de la formation correspondante, le nom du formateur (libellé de 25 caractères), et la liste des séances.
Donner, en Caml, une définition des types de données date, code_salle, session_type et séance :

Solution

Le type produit vectoriel
Le type somme
Les listes


Exercice 23

On considère les éléments d'un ensemble fini A comme étant les ceux d'une liste CAML.
Ecrire une fonction parties qui retourne une liste correspondant à l'ensemble P(A) des parties de A.

syntaxe = parties liste
typage = parties : 'a list -> 'a list list

exemple :
#parties [1; 2; 3; 4] ;;
- : int list list = [[1; 2; 3; 4]; [1; 2; 3]; [1; 2; 4]; [1; 2]; [1; 3; 4]; [1; 3]; [1; 4]; [1]; [2; 3; 4]; [2; 3]; [2; 4]; [2]; [3; 4]; [3]; [4]; []]

Solution

Fonctions
La récursivité
Le filtrage
Le type somme
Les listes


Exercice 24

On considère les éléments d'un ensemble fini A comme étant les ceux d'une liste CAML.
Ecrire une fonction lister_sous_liste qui retourne toutes les listes de n éléments extraites d'une liste donnée, au sens des ensembles, c'est-à-dire que deux listes contenant les mêmes éléments placés dans un ordre différent, sont identiques.

syntaxe = lister_sous_liste nombre liste
typage = lister_sous_liste : int -> 'a list -> 'a list list

exemple :
#liste_sous_liste 2 [1; 2; 3; 4] ;;
- : int list list = [[4; 3]; [3; 2]; [4; 2]; [2; 1]; [3; 1]; [4; 1]]

Solution

Fonctions
La récursivité
Le filtrage
Le type somme
Les listes


Exercice 25

On considère les éléments d'un ensemble fini A comme étant les ceux d'une liste CAML.
Ecrire une fonction permuter qui retourne une liste de toutes les permutations d'une liste donnée.
syntaxe : permuter liste
typage : permuter : 'a list -> 'a list list

exemple :
#permuter [1; 2; 3] ;;
- : int list list = [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 2; 1]; [3; 1; 2]]

Solution
Fonctions
La récursivité
Le filtrage
Le type somme
Les listes


Exercice 26

La fonction Caml prédéfinie assoc permet de rechercher un élément dans une liste de paires, à partir de la valeur du premier terme a de la paire (a,b) selon la syntaxe assoc a liste.
Si la fonction échoue elle déclenche l'exception Not_found.
Selon le même principe, définir une fonction récursive assoc_r en Caml définissant et en utilisant l'exception Non_trouvé

Solution

Le type produit vectoriel
Fonctions
La récursivité
Le filtrage
Le type somme
Les listes
Les exceptions


Exercice 27

Dans les définitions Caml suivantes, on construit la fonction entrer_entier pour contrôler la saisie des nombres entiers dans un intervalle délimité par une borne inférieure et une borne supérieure [borne_inf, borne_sup] :
(* affichage d'un message sur la ligne suivante *) 

#let message m = 
  print_newline (); 
  print_string m ;; 
message : string -> unit =  

(* entrée de donnée précédée de l'affichage d'un message *) 

#let demande question = 
  message (question^" : ") ; 
  read_line () ;; 
demande : string -> string =  

(* entrée de donnée contrôlée *) 

#let rec entrer_entier x (borne_inf, borne_sup)= 
  let q = x^" (min="^(string_of_int borne_inf) 
           ^", max="^(string_of_int borne_sup)^")" in 
  try 
    let n = int_of_string (demande q) in 
    if (nborne_sup) then raise erreur_bornes 
    else n 
  with 
    Failure "int_of_string" -> 
	message "Erreur de saisie : entrer un nombre entier." ; 
	entrer_entier x (borne_inf, borne_sup) 
  | erreur_bornes -> 
	message "Erreur de saisie : bornes non respectées." ; 
	entrer_entier x (borne_inf, borne_sup) ;; 
entrer_entier : string -> int * int -> int =  
a) - commenter l'utilisation de l'exception Caml prédéfinie :
Failure "int_of_string".
b) - déclarer les autres exceptions utilisées et indiquer leur rôle.
Solution

Fonctions
La récursivité
Le filtrage
Les exceptions


Exercice 28

Soit le module Caml suivant :
(* pile.ml *) 
let global_pile = ref ([]:int list);; 
let init_pile () = 
  global_pile := [] 
and empiler x = 
  global_pile := x :: !global_pile 
and depiler () = 
  match !global_pile with 
    [] -> print_string "pile vide\\n" 
  | x::R -> global_pile := R 
and afficher () = 
  !global_pile;;  
établir son interface pour exporter uniquement les fonctions init_pile, afficher, empiler et depiler, en dissimulant la variable globale global_pile.

Solution

Programmation modulaire


Exercice 29

Comment faut-il modifier la fonction entrer_entier de l'exercice 27 pour éviter le passage des arguments lors de chaque appel récursif.

Solution

Les exceptions
Programmation fonctionnelle et machines à états
Les types de données mutables et la mémoire
La séquentialité


Exercice 30

Soit une session Caml dans un environnement E, typer et évaluer les phrases suivantes :
1. #let alpha = function a -> function b -> function c -> 
      let  rec gamma = function 
        [] -> [] 
      | x::R -> if x = a then b::(gamma R) else x::(gamma R) 
      in gamma c ;; 
2. #let delta = alpha 5 8 ;; 
3. #delta([ 1; 5; 8; 9; 5; 4; 1; 3; 5; 9; 4]) ;;  
4. #let rec omega a = function [] -> 0 
      | x::R -> (a * x) + (omega (a+1) R) ;; 
5. #let epsilon = alpha 9 1 [ 1; 5; 8; 9; 5; 8; 1; 1; 5; 9] 
      in omega 0 (alpha 8 1(delta epsilon));; 

Solution

Type et valeur des expressions
Définitions et environnement
Expressions conditionnelles
Le type produit vectoriel
Fonctions


Exercice 31

Construire une fonction Caml équivalente à la fonction alpha de l'exercice 2.10, en utilisant la fonction prédéfinie map.

Solution

Fonctions
La récursivité
Le filtrage
Le type somme
Les listes


Exercice 32

A ) On souhaite traiter des k_listes dont les éléments, les kAtomes, sont construits à partir :
- des valeurs Null et Tout,
- d'entiers,
- de caractères,
- ou de k_listes.
La k_liste principale est de niveau 0.
Une k_liste quelconque définie comme élément d'une k_liste de niveau n est de niveau (n+1), et ses élément sont des éléments de niveau (n+1) de la k_liste qui la contient.
La profondeur d'une k_liste est donnée par le niveau le plus élevé de ses éléments.
1) Définir un type permettant de représenter les kAtomes en Caml.
2) Définir une fonction pour déterminer la profondeur d'une k_liste.
B ) L'application substituer k1 k2 listeK permet de remplacer chaque élément k1 de la k_liste listeK par un élément k2, quel que soit son niveau dans la liste listeK.
A partir du type kAtome défini dans l'exercice 3, écrire une définition de la fonction substituer.
C ) Etablir le module d'interface permettant d'exporter le type kAtome et la fonction substituer.

Solution

Type et valeur des expressions
Les modules
La programmation modulaire
Fonctions
La récursivité
Le filtrage
Le type somme
Les listes


Exercice 33

Si on considère que Pn(x) est un polynôme de degré n. Une manière de représenter les polynômes :
Pn(x)=anxn+...+aixi +...+a0x0
dont la syntaxe en ASCII peut être décrite par :
Pn(x)= an*x^n+...+ai*x^i +...+a0*x^0
consiste à utiliser les listes de paires (d,c) formées par le degré d = i et par le coefficient c = ai de chaque monôme M(x)= ai*x^i.
A) Ecrire une liste de paires comme représentation du polynôme :
A = 2*x^5-8*x^3+3*x^2-x-7.
B) Ecrire le polynôme B correspondant à la représentation suivante :
B = [(4,8);(0,9);(1,-5);(3,7)].
C) Construire la fonction qui détermine le degré n d'un polynôme Pn(x) donné.
D) Sachant que la dérivée d'un monôme M(x)= ai*x^i correspond à :
M'(x)= 0 quand i = 0
sinon M'(x)= i*ai*x^(i-1), quand i <> 0.
Ecrire la fonction Caml deriver_poly permettant de calculer la dérivée d'un polynôme Pn(x).
E) Ecrire une fonction de conversion de tout polynôme Pn(x) en chaîne de caractère représentant ce polynôme sous sa forme normale, c'est-à-dire comme la somme algébrique de monômes ai*x^i rangés dans l'ordre des degrés décroissants.
Solution

Le type produit vectoriel
Le filtrage
Les listes


Exercice 34

Typer et évaleuer les phrases de la session Caml suivante :
1)#let a = ref (5 - 3 * 2) ;; 
2)#let b = 
	 let x = 3 and y = 4, 2 in 
	 !a + (snd y) * x, !a*x + fst y ;; 
3)#let h = function x -> function y -> ( y * (x y) ) ;; 
4)#a := h (fun x -> x + x) 5 ;; 
5)#a;;  
Solution

Type et valeur des expressions
Définitions et environnement
Le type produit vectoriel
Fonctions


Exercice 35

Définir en Caml une fonction génère_numéro qui génère automatiquement un numéro de séquence, à partir de 0.
A chaque appel de la fonction le numéro de séquence est incrémenté de la valeur du pas : 1.
syntaxe = génère_numéro ()
typage = génère_numéro : unit -> int

Solution

Les types de données mutables et la mémoire


Exercice 36

Le stock est représenté par un tableau d'articles où chaque article est décrit par un type produit composé des 3 éléments : Le code de l'article est son indice de position dans le tableau suivant,
#let table_articles = 
[|("Guitare", 3500, 45); 
  ("Banjo",	 2300, 18); 
  ("Ukulele", 1800, 34);
  ................ 
  ("Flûte à bec", 1100,	 55) |] ;; 
1) Ecrire une fonction entrée_en_stock à deux arguments code et qte, qui retrouve l'article correspondant à code et ajoute qte à la quantité en stock, le résultat est la valeur de l'article modifié.
syntaxe : entrée_en_stock code qte
typage : entrée_en_stock int -> int -> int

2) Ecrire une fonction sortie_de_stock à deux arguments code et qte, qui retrouve l'article correspondant à code et retire qte à la quantité en stock si qte est inférieur ou egal à cette quantité, sinon la fonction renvoie une exception erreur_sortie_stock indiquant en message l'excédent de qte par rapport à la quantité en stock.
Le résultat est la valeur de l'article modifié.
syntaxe : sortie_de_stock code qte
typage : sortie_de_stock int -> int -> int

Solution

Type et valeur des expressions
Le type produit vectoriel
Le type somme
Le polymorphisme


Exercice 37

Dans une facture doivent figurer les informations suivantes :
- nom_client : le nom du client
- date_facture : la date de facture est representée par un type produit composé de 3 valeurs entières : le jour, le mois, l'année
- livré : indication si la livraison a déjà été effectuée ou non
- règlement : le mode de règlement :
. si le client règle au comptant : valeur COMPTANT suivi d'une mention Chèque ou Espèce ou Carte_bancaire
. si le client règle à crédit : valeur CREDIT
- liste_achats : la liste des lignes d'achats effectués par le client.
Chaque ligne d'achat mentionne :
. code : le code de l'article (valeurs entières),
. quantité : la quantité achetée (valeurs entières).
Définir les types mention, mode_règlement, ligne_achat, et facture.
Solution

Le type produit vectoriel
Le type somme
Les listes