Solutions

abstraction concrète

Solution de l'exercice 1

Les identificateurs 1_un, 8A, _deux, 'trois, ne commencent pas par une lettre de l'alphabet, carre d'as comporte un caractère espace non admis dans un identificateur, quant à function et then, ce sont des mots réservés du langage Caml.

Solution de l'exercice 2

AFFICHAGE ENVIRONNEMENT 1. a : int = 30 E1 = (a,30) Ei 2. b : int = 50 E2 = (b,50)(a,30) Ei 3. a : int = 55 E3 = (a,55)(b,50)(a,30) Ei 4. - : int = 55 E4 = (a,55)(b,50)(a,30) Ei 5. - : int = 50 E5 = (a,55)(b,50)(a,30) Ei 6. - : int = 169 E6 = (a,55)(b,50)(a,30) Ei 7. - : int = 154 E7 = (a,55)(b,50)(a,30) Ei

Solution de l'exercice 3

AFFICHAGE ENVIRONNEMENT a : int = 85 E1 = E0 (inchangé)

Solution de l'exercice 4

1. a : int = 24 2. - : int = 626

Solution de l'exercice 5

1. (c + 4) <= (8 - x) Posons e1=(c+4), e2=(8-x) l'expression (c + 4) <= (8 - x) devient e1 <= e2 On sait que (prefix +) est du type int -> int -> int si c est du type int et x est du type int alors e1 est du type int et e2 est du type int e1 et e2 sont du même type et (prefix <=) est du type 'a -> 'a -> bool) donc e1 <= e2 est du type bool sinon erreur 2. ("a" ^ "b") = c Posons e=("a" ^ "b") l'expression ("a" ^ "b") = c devient e = c On sait que (prefix ^) est du type string -> string -> string alors e est du type string si c est du type string alors e et c sont du même type et (prefix <=) est du type 'a -> 'a -> bool) donc e = c est du type bool sinon erreur 3. (4 < 8) = ("a" = "b") Posons e1=(4 < 8), e2=("a" = "b") l'expression (4 < 8) = ("a" = "b") devient e1 = e2 On sait que (prefix <) est du type 'a -> 'a -> bool donc e1 est du type bool et (prefix =) est du type 'a -> 'a -> bool donc e2 est du type bool e1 et e2 sont du même type donc e1 = e2 est du type bool 4. ("a" + 5) = ("a" + 5) On sait que (prefix +) est du type int -> int -> int et "a" est du type string incompatible avec int #"a"+5;; Toplevel input: >"a"+5;; >^^^ This expression has type string, but is used with type int.

Solution de l'exercice 6

# let x=5 in let x2=x*x in let x3=x2*x in let x4=x3*x in let x5=x4*x in x5-2*x4+3*x3-4*x2+5*x-6 ;; - : int = 2169

Solution de l'exercice 7

La phrase est mal construite et syntaxiquement incorrecte. Le système interactif renvoie un message d'erreur en indiquant la position à partir de laquelle l'erreur est effective. Ici la dernière définition devrait être suivi par une expression d'un niveau plus global.
#let taux = 2 in
        let alpha = 5 in
                let coef = taux * alpha + alpha in
                let a = taux * alpha + coef * alpha;;
> Toplevel input:
>               let a = taux * alpha + coef * alpha;;
>                                                  ^^
> Syntax error.


Solution de l'exercice 8

AFFICHAGE ENVIRONNEMENT 1. a : int = 5 E1 = (a,5) E 2. a : int = 10 E2 = (a,10)(a,5) E 3. v : bool = true E3 = (v,true)(a,10)(a,5) E 4. f : int -> int = <fun> E4 = (f, «x~>f(x),E3»)(v,true)(a,10)(a,5) E 5. - : int = 104 E5 = E4 6. erreur E6 = E4 > Toplevel input: >f f 2 ;; >^ > Expression of type int -> int > cannot be used with type int -> 'a -> 'b 7. h : int -> int = <fun> E7 = (h, «x~>h(x),E6»)(f, «x~>f(x),E3»)(v,true)(a,10)(a,5) E 8. - : int = 17136 E8 = E7 9. gamma : int -> int -> int = <fun> E9 = (gamma, «(x,y)~>gamma(x,y),E8»)(h, «x~>h(x),E6»)(f, «x~>f(x),E3»)(v,true)(a,10)(a,5) E 10. z : int -> int = <fun> E10 = (z, «x~>z(x),E9»)(gamma, «(x,y)~>gamma(x,y),E8»)(h, «x~>h(x),E6»)(f, «x~>f(x),E3»)(v,true)(a,10)(a,5) E 11. - : int = 32 E11 = E10 12. - : int = 50 E12 = E10

Solution de l'exercice 9

1. Y : 'a -> 'b -> 'c -> 'b = <fun>
2. H : ('a -> 'a -> 'b) -> 'a -> 'b = <fun>
3. - : int = 8

Solution de l'exercice 10

AFFICHAGE ENVIRONNEMENT E = environnement initial 1)#let a = 5 ;; a : int = 5 E1 = (a,5)E 2)#let b = 3 ;; b : int = 3 E2 = (b,3)E1 3)#a,b ;; - : int * int = 5, 3 E3 = E2 4)#let alpha x = let a=2 in a * x + b ;; alpha : int -> int = <fun> E4 = (alpha,Falpha)E3 avec Falpha = valeur fonctionnelle de alpha Falpha = «x~>alpha(x),Ealpha» où Ealpha = (a,2)E3 5)#alpha 7 ;; - : int = 17 E5 = E4 6)#let béta x = let b=2 in a * x + b ;; béta : int -> int = <fun> E6 = (béta, «x~>béta(x),Fbéta»)E5 avec Fbéta = valeur fonctionnelle de béta Fbéta = «x~>béta(x),Ebéta» où Ebéta = (b,2)E5 7)#béta 7 ;; - : int = 37 E7 = E6 8)#let gamma a b = let x = 7 in a * x + b ;; gamma : int -> int -> int = <fun> E8 = (gamma,Fgamma)E7 avec Fgamma = valeur fonctionnelle de gamma Fgamma = «a,b~>gamma(a,b),Egamma» où Egamma = (x,7)E7 valeur fonctionnelle évaluée dans Egamma = a,b~>(a * 7 + b) 9) #gamma a b ;; - : int = 38 E9 = E8 où E8 = (gamma,Fgamma)(béta,Fbéta)(alpha,Falpha)(b,3)(a,5) E 10) #let a,b,x = 2,1,3 ;; a : int = 2 b : int = 1 x : int = 3 E10 = (a,2)(b,1)(x,3)E9 11) #alpha x , béta x , gamma a b ;; - : int * int * int = 9, 17, 15 E11 = E10

Solution de l'exercice 11

1)#let h = function f -> function g -> g f ;; h : 'a -> ('a -> 'b) -> 'b = <fun> 2)#let x = h 4 ;; x : (int -> 'a) -> 'a = <fun> 3)#let t = h 4 (function x -> x + 2) ;; t : int = 6

Solution de l'exercice 12

1.# let suivant = function n -> n + 1 ;; suivant : int -> int = <fun> # suivant 4 ;; - : int = 5 2.# let precedent = function n -> n - 1 ;; precedent : int -> int = <fun> # precedent 4 ;; - : int = 3 3.# let double = function n -> 2 * n ;; double : int -> int = <fun> # double 4 ;; - : int = 8

Solution de l'exercice 13

# let base = function salaire -> function plafond -> if plafond < salaire then plafond else salaire ;; base : int -> int -> int = <fun> (* cas 1 : salaire >= plafond *) # base 120000 45000 ;; - : int = 45000 (* cas 2 : salaire < plafond *) # base 30000 45000 ;; - : int = 30000

Solution de l'exercice 14

(* int_of_base : conversion d'un nombre base b quelconque en nombre base dix *)
(* int_of_base : int -> string -> int *)
let rec int_of_base b s = match s with
	"" -> 0
   |	s -> let l = string_length s - 1 in
	     let n = int_of_char (nth_char s l) in
	     let x = if n>57 then n-55 else n-48 in
		x + int_of_base b (sub_string s 0 l) * b;;

#int_of_base 16 "A" ;;
- : int = 10
#int_of_base 8 "14" ;;
- : int = 12


Solution de l'exercice 15

(* base_of_int : conversion d'un nombre base dix en nombre base b quelconque *)
(* base_of_int : int -> int -> string *)
let rec base_of_int b x =
	let car n = if n > 9
		then make_string 1 (char_of_int (n+55))
		else make_string 1 (char_of_int (n+48))
	in
	if x < b then car x else (base_of_int b (x / b))^(car (x mod b)) ;;

#base_of_int 2 12 ;;
- : string = "1100"
#base_of_int 16 250 ;;
- : string = "FA"


Solution de l'exercice 16

(* convbase : conversion d'un nombre base b1 quelconque en nombre base b2 quelconque *)
(* on utilise les fonctions définies dans les exercices int_of_base cf. exercice 1.13 base_of_int cf. exercice 1.14 *)
(* convbase : int -> int -> string -> string *)
let convbase b1 b2 s = base_of_int b2 (int_of_base b1 s) ;;

(* EXEMPLE DE SESSION *)

#convbase 2 16 "1001100111111011";;
- : string = "99FB"
#convbase 16 10 "99FB";;
- : string = "39419"
#convbase 16 8 "A5";;
- : string = "245"
#convbase 8 10 "245";;
- : string = "165"
#convbase 8 2 "245";;
- : string = "10100101"
#convbase 10 2 "39419";;
- : string = "1001100111111011"


Solution de l'exercice 17

1.#let rec h = function (5,_) -> 0 | (_,5) -> 1 | (x,9) -> x | (x,y) -> y ;; h : int * int -> int = <fun> Le filtrage de cette fonction est exhaustif. 2. #h (5,5) , h (0,5) , h (5,9) , h (9,5) ;; - : int * int * int * int = 0, 1, 0, 1 3. #h (9,4) , h (4,9) , h (11,9) , h (7,8) ;; - : int * int * int * int = 4, 4, 11, 8 4. #h (h (5,9),h (9,9)) , h (h (9,7),h (5,9)) ;; - : int * int = 0, 0

Solution de l'exercice 18

1.#let a = 80;; a : int = 80 2.#let b = a + 20;; b : int = 100 3.#let a = b + 50 in a + a * 3 ;; - : int = 600 4.#let a = let b = 50 in a + b * 3 ;; and b = let b = 50 in let a = 20 in a + b * 3 ;; a : int = 230 b : int = 170 5.#let c = 8 in c * c + a + b;; - : int = 464

Solution de l'exercice 19

1.#(17 + 4*7) <= (58 - 3*12) ;; - : bool = false 2.#("a" ^ "b"), (5+2) = 7, 0 ;; - : string * bool * int = "ab", true, 0 3.#function x -> (4 < x) = ("a" = "b") ;; - : int -> bool = <fun> 4.#("a" + 5) = ("a" + 5) ;; > Toplevel input: >("a" + 5) = ("a" + 5) ;; > ^^^ > Expression of type string > cannot be used with type int 5.#(function x -> snd(x)), (function x -> fst(x)) ;; - : ('a * 'b -> 'b) * ('c * 'd -> 'c) = <fun>, <fun> 6.#let f = function (x,y) -> y*y ;; f : 'a * int -> int = <fun> 7.#let g = function (a,b,u) -> u(b,a) ;; g : 'a * 'b * ('b * 'a -> 'c) -> 'c = <fun> 8.#g (0,5,f) ;; - : int = 0 9.#function _ -> 0 ;; - : 'a -> int = <fun> 10.#function x -> (function f -> f(x)) ;; - : 'a -> ('a -> 'b) -> 'b = <fun>

Solution de l'exercice 20

let hd_str = function "" -> "" | s -> sub_string s 0 1 and tl_str = function "" -> "" | s -> sub_string s 1 (string_length s - 1);; let rec renverse = function "" -> "" | s -> (renverse (tl_str s))^(hd_str s);; let est_palindrome = function s -> s = renverse s ;; #hd_str "XYZ";; - : string = "X" #tl_str "XYZ";; - : string = "YZ" #renverse "Vieille ville" ;; - : string = "elliv ellieiV" #est_palindrome "oui" ;; - : bool = false #est_palindrome "non" ;; - : bool = true

Solution de l'exercice 21

a) définition du type nombre : #type nombre = Entier of int | Réel of float | Complexe of float * float ;; Type nombre defined. b) fonction carré: #let carré = function Entier x -> Entier (x*x) | Réel x -> Réel (x*.x) | Complexe (a,b) -> Complexe (a*.a-.b*.b,2.0*.a*.b) ;; carré : nombre -> nombre = <fun> Exemples : #carré (Entier 4) ;; - : nombre = Entier 16 #carré (Réel (sin 43.16)) ;; - : nombre = Réel 0.536865503132 #carré (Complexe (cos 43.16, sin 43.16)) ;; - : nombre = Complexe (-0.073731006263, -0.997278165165)

Solution de l'exercice 22

1) #type niveau_de_progression = Initiation | Perfectionnement;; Type niveau_de_progression defined. #type enreg_formation = { intitulé : string; nombre_de_séances : int; niveau : niveau_de_progression; nombre_maximum_de_stagiaires : int; tarif : float};; Type enreg_formation defined. #type formation == (int * enreg_formation );; Type formation defined. 2) #type jour == int and mois == int and annee == int and session_type = MATIN | APRES_MIDI and code_salle = A of int | B of int and date_type = { nj : jour; nm : mois; na : annee } and seance = { date : date_type; session : session_type; salle : code_salle };; Type jour defined. Type mois defined. Type annee defined. Type session_type defined. Type code_salle defined. Type date_type defined. Type seance defined.

Solution de l'exercice 23

1ère approche :

On a recours à une fonction annexe de construction des listes nommée cons et définie par :
#let cons = function a -> function R -> a::R ;;
cons : 'a -> 'a list -> 'a list = <fun>
1) Examinons la liste L(n-1) =[2; 3], la liste des parties de L(n-1) est donné par :
P(L(n-1)) = [[]; [2]; [3]; [2; 3]]
2) Examinons la liste L(n) =[1; 2; 3], la liste des parties de L(n) est donné par :
P(L(n)) = [[]; [2]; [3]; [2; 3]; [1]; [1; 2]; [1; 3]; [1; 2; 3]]
ce qui revient à écrire P(L(n)) = [[]; [2]; [3]; [2; 3]; 1::[]; 1::[2]; 1::[3]; 1::[2; 3]]

on remarque que pour construire la liste des parties d'une liste L(n) de n éléments P(L(n)) on se sert de la liste construite à partir de la liste des parties d'une liste à n-1 éléments L(n-1) obtenue en retirant un élément x quelconque de L(n), on obtient ainsi A = P(L(n-1)), puis on construit une seconde liste B en ajoutant l'élément x en tête de liste pour chacun des éléments de A avec la fonction cons de construction de listes, on obtient ainsi B = (map (cons x) A ). La liste des parties recherchée est alors produite par la concaténation des listes A et B, ce qui dans notre exemple donne :
P(L(n)) = append (P(L(n-1))) (map (cons 1) (P(L(n-1))) )
Alors la fonction principale est définie simplement par :
#let rec parties = function
    []->[[]]
  | x::R -> let P = parties R in P@(map (cons x) P) ;;
parties : 'a list -> 'a list list = <fun> 
ou encore en incorporant la fonction annexe dans la fonction principale :
#let parties liste =
   let f a l = a::l in
     let rec part = function []->[[]]
       | x::R -> let p = part R in p@(map (f x) p) in
   part liste;;
parties : 'a list -> 'a list list = <fun>
 Exemple d'application de la fonction:
#parties [1; 2; 3; 4] ;;
- : int list list = [[]; [4]; [3]; [3; 4]; [2]; [2; 4]; [2; 3]; [2; 3; 4]; [1]; [1; 4]; [1; 3]; [1; 3; 4]; [1; 2]; [1; 2; 4]; [1; 2; 3]; [1; 2; 3; 4]]

2ème approche :
Définition de la fonction :
On construit la fonction d'accumulation map_f :
let rec map_f f i = function
  [] -> i
| x::R -> f x (map_f f i R) ;;
puis, on définit la fonction parties comme une application de la fonction d'accumulation map_f :
let parties l =
  let f x p = map (function l->x::l) p@p in map_f f [[]] l ;;
 ou bien en une fonction unique :
let parties l =
  let rec map_f f i = function
    [] -> i
  | x::R -> f x (map_f f i R) in
  let f x p = map (function l->x::l) p@p in map_f f [[]] l ;;
 Exemple d'application de la fonction:
#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 de l'exercice 24

Première solution construite à partir de la fonction parties de l'exercice 2.3 :
#let lister_sous_liste n liste =
  let rec sous_listes = function []->[]
    | x::R -> if list_length x = n
       then x::(sous_listes R)
       else sous_listes R
  in sous_listes (parties liste) ;;
lister_sous_liste : int -> 'a list -> 'a list list = <fun>
 Exemples d'application de la fonction :
#lister_sous_liste 4 l;;
- : int list list = [[1; 2; 3; 4]]
#lister_sous_liste 3 l;;
- : int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 4]; [2; 3; 4]]
#lister_sous_liste 2 l;;
- : int list list = [[1; 2]; [1; 3]; [1; 4]; [2; 3]; [2; 4]; [3; 4]]
#lister_sous_liste 1 l;;
- : int list list = [[1]; [2]; [3]; [4]]
#lister_sous_liste 0 l;;
- : int list list = [[]]
cas d'erreurs :
#lister_sous_liste 5 l;;
- : int list list = []
#lister_sous_liste (-1) l;;
- : int list list = []
#liste_sous_liste 2 [1; 2; 3; 4] ;;
- : int list list = [[4; 3]; [3; 2]; [4; 2]; [2; 1]; [3; 1]; [4; 1]]

Cette première solution qui est une application immédiate de la fonction parties, est peu performante et devient vite inefficace puisqu'il faut construire une liste à 2n éléments pour en extraire une sous_liste éventuellement réduite à un nombre très petit d'éléments comparativement à 2n.

En fait, pour l'ensemble des listes de p éléments formées à partir d'une liste à n éléments, nous aurons n!/p!(n-p)! éléments. Au lieu de former la liste des parties et d'éliminer les listes qui ne conviennent pas, nous construirons uniquement les listes qui conviennent, en observant que : l'ensemble des sous listes de longueur n peut être obtenu en dissociant la liste initiale, en retirant un, quelconque, de ses élément x, et en le séparant de la liste résiduelle R.

On forme les sous listes de n éléments en ajoutant l'élément x au sous listes de (n-1) éléments formées depuis la liste résiduelle R, et on applique la même méthode à chacun des éléments de la liste initiale et à chaque liste résiduelle correspondante.
let rec sub_list n liste =
  match liste with
    [] -> []
  | x::R ->
      if n < 0 then failwith "sub_list"
      else if n = 0 then []
      else if n = 1 then map (fun x -> [x]) liste
      else (map(fun y -> x::y)(sub_list(n-1)R))@(sub_list n R) ;;


Solution de l'exercice 25

Définition de la fonction : (* on définit une fonction rotation *) #let rotation l = map (function x -> x::(except x l)) l ;; rotation : 'a list -> 'a list list = <fun> #let rec permuter liste = let perm = function []->[] | [x]->[[x]] | x::R -> (map (function l->x::l) (permuter R) ) in flat_map perm (rotation liste) ;; permuter : 'a list -> 'a list list = <fun> Exemple d'application de la fonction :
#permuter [1;2;3];;
- : int list list = [[1; 2; 3]; [1; 3; 2]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [3; 2; 1]]
(* les deux fonctionnelles prédéfinies map et flat_map *)
let rec map_r la_fonction la_liste = match la_liste with []->[]
  | x::R -> (la_fonction x)::(map_r la_fonction R);;
let rec flat_map_r la_fonction la_liste = match la_liste with []->[]
  | x::R -> (la_fonction x)@(flat_map_r la_fonction R);;

 Solution en une seule fonction

#let permuter liste =
  let rotation l = map (function x -> x::(except x l)) l in
  let rec pre_perm = function []->[] | [x] -> [[x]]
    | x::R -> (map (function l->x::l) (r_perm R) )
  and r_perm = function l -> flat_map pre_perm (rotation l)
  in r_perm liste ;;
permuter : 'a list -> 'a list list = <fun>

ou bien

#let rec permuter liste =
  let rotation l = map (function x -> x::(except x l)) l in
  let rec perm = function []->[] | [x] -> [[x]]
    | x::R -> (map (function l->x::l) (permuter R) )
  in flat_map perm (rotation liste) ;;
permuter : 'a list -> 'a list list = <fun>
#permuter ["a";"b";"c"];;
- : string list list = [["a"; "b"; "c"]; ["a"; "c"; "b"]; ["b"; "a"; "c"]; ["b"; "c"; "a"]; ["c"; "a"; "b"]; ["c"; "b"; "a"]]

Solution de l'exercice 26

exception Non_trouvé;; let assoc_r = function a -> function l -> let rec assoc_rec = function [] -> raise Non_trouvé | (x,y)::R -> if x=a then y else assoc_rec R in assoc_rec l;;

Solution de l'exercice 27

a) Exception Failure "int_of_string" : - Définition : exception prédéfinie - Déclenchement : Lors de l'appel à la fonction prédéfinie int_of_string, si la valeur retournée par (demande q) n'est pas une valeur du type int, l'exception Failure "int_of_string" est déclenchée par le système Caml. - Récupération : Affichage du message "Erreur de saisie : entrer un nombre entier.", puis appel récursif de la fonction entrer_entier. b) Exception erreur_bornes : - Définition par l'utilisateur : exception erreur_bornes ;; - Déclenchement : si (n < borne_inf) ou (n > borne_sup) - Récupération : Affichage du message "Erreur de saisie : bornes non respectées.", puis appel récursif de la fonction entrer_entier.

Solution de l'exercice 28

(* pile.mli *) value init_pile : unit -> unit and afficher : unit -> int list and empiler : int -> unit and depiler : unit -> unit ;;

Solution de l'exercice 29

On peut utiliser une définition locale de fonction récursive. #let entrer_entier_bis x (borne_inf, borne_sup)= let q = x^" (min="^(string_of_int borne_inf) ^", max="^(string_of_int borne_sup)^")" in let rec re_saisir () = 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." ; re_saisir () | erreur_bornes -> message "Erreur de saisie : bornes non respectées." ; re_saisir () in re_saisir ();; entrer_entier_bis : string -> int * int -> int = <fun>

Solution de l'exercice 30

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 ;; alpha : 'a -> 'a -> 'a list -> 'a list = <fun> 2. #let delta = alpha 5 8 ;; delta : int list -> int list = <fun> 3. #delta([ 1; 5; 8; 9; 5; 4; 1; 3; 5; 9; 4]) ;; - : int list = [1; 8; 8; 9; 8; 4; 1; 3; 8; 9; 4] 4. #let rec omega a = function [] -> 0 | x::R -> (a * x) + (omega (a+1) R) ;; omega : int -> int list -> int = <fun> 5. #let epsilon = alpha 9 1 [ 1; 5; 8; 9; 5; 8; 1; 1; 5; 9] in omega 0 (alpha 8 1(delta epsilon));; - : int = 45

Solution de l'exercice 31

Construire une fonction Caml équivalente à la fonction alpha de l'exercice 1, en utilisant la fonction prédéfinie map.
#let alpha' = function a -> function b -> function c ->
    map (function x -> if x = a then b else x) c ;;
alpha' : 'a -> 'a -> 'a list -> 'a list = <fun>

#alpha' 5 8 [ 1; 5; 8; 9; 5; 4; 1; 3; 5; 9; 4] ;;
- : int list = [1; 8; 8; 9; 8; 4; 1; 3; 8; 9; 4]

Solution de l'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.
#type kAtome =
     Null | Tout
   | Ent of int
   | Car of char
   | Lst of kAtome list ;;
Type kAtome defined.

#let rec profondeur = function [] -> 0
  | (Lst z)::R -> max (1+(profondeur z)) (profondeur R)
  | x::R -> (profondeur R) ;;
profondeur : kAtome list -> int = <fun>

#let KL =
   [Ent 5;                            (* niveau 0 *)
    Lst[                              (* niveau 1 *)
        Lst[Ent 1;                    (* niveau 2 *)
            Lst[Ent 0; Car `X`;       (* niveau 3 *)
                Lst[Null]];           (* niveau 4 *)
            Lst[ Car `X`]]]] ;;       (* niveau 3 *)
KL : kAtome list = [Ent 5; Lst [Lst [Ent 1; Lst [Ent 0; Car `X`; Lst [Null]]; Lst [Car `X`]]]]

#profondeur KL ;;
- : int = 4
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.
#let substituer = function a -> function b -> function c ->
      let  rec gamma = function
        [] -> []
      | (Lst z)::R ->
          if (Lst z) = a then b::(gamma R)
          else  (Lst (gamma z))::(gamma R)
      | x::R ->
          if x = a then b::(gamma R) else x::(gamma R)
      in gamma c ;;
substituer : kAtome -> kAtome -> kAtome list -> kAtome list = <fun>

#let KLL = substituer (Car `X`) (Lst [Ent 7; Tout]) KL ;;
KLL : kAtome list = [Ent 5; Lst [Lst [Ent 1; Lst [Ent 0; Lst [Ent 7; Tout]; Lst [Null]]; Lst [Lst [Ent 7; Tout]]]]]
#let KLLL = substituer (Lst [Ent 7; Tout]) Null KLL ;;
KLLL : kAtome list = [Ent 5; Lst [Lst [Ent 1; Lst [Ent 0; Null; Lst [Null]]; Lst [Null]]]]
#let K = substituer (Lst [Null]) Tout KLLL ;;
K : kAtome list = [Ent 5; Lst [Lst [Ent 1; Lst [Ent 0; Null; Tout]; Tout]]]
C ) Etablir le module d'interface permettant d'exporter le type kAtome et la fonction substituer.
(* kAtome.mli *)

type kAtome =
     Null | Tout
   | Ent of int
   | Car of char
   | Lst of kAtome list ;;

value substituer : kAtome -> kAtome -> kAtome list -> kAtome list ;;

Solution de l'exercice 33

A) Ecrire une liste de paires comme représentation du polynôme
A = 2*x^5-8*x^3+3*x^2-x-7.
Solution :
A = [(5,2);(3,-8);(2,3);(1,-1);(0,-7)].
B) Ecrire le polynôme B correspondant à la représentation suivante :
[(4,8);(0,9);(1,-5);(3,7)].
Solution :
B = 8*x^4+ 7*x^3+ (-5)*x^1+ 9*x^0
B = 8*x^4+ 7*x^3- 5*x + 9
C) Construire la fonction qui détermine le degré n d'un polynôme Pn(x) donné :
#let rec degré = function
    [] -> 0
  | (d,c)::R -> max d (degré R) ;;
degré : (int * 'a) list -> int = <fun>

#degré [(2,11);(0,9);(5,-1);(3,7)] ;;
- : int = 5
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).
#let deriver_mono = function
    (0,_) -> (0,0)
  | (d,c) -> (d-1,d*c) ;;
deriver_mono : int * int -> int * int = <fun>

#let deriver_poly = function P -> map deriver_mono P ;;
deriver_poly : (int * int) list -> (int * int) list = <fun>

#deriver_poly [(2,11);(0,9);(5,-1);(3,7)] ;;
- : (int * int) list = [1, 22; 0, 0; 4, -5; 2, 21]

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.

(* 1ère version *)
#let rec string_of_poly = function [] -> ""
  | (d,c)::R ->
      (if c < 0 then "-" else "+")^(string_of_int (abs c))^
           "*x^"^(string_of_int d)^(string_of_poly R) ;;
string_of_poly : (int * int) list -> string = <fun>

#let p = [(2,21);(4,9);(1,-1);(3,7);(0,2);(8,0)] ;;
p : (int * int) list = [2, 21; 4, 9; 1, -1; 3, 7; 0, 2; 8, 0]

(* 2ème version *)
let rec string_of_poly' = function [] -> ""
  | (_,0)::R -> string_of_poly' R
  | (0,c)::R ->
      (if c < 0 then "-" else "+")^(string_of_int (abs c))^(string_of_poly' R)
  | (1,1)::R ->
      "+x"^(string_of_poly' R)
  | (1,-1)::R ->
      "-x"^(string_of_poly' R)
  | (1,c)::R ->
      (if c < 0 then "-" else "+")^(string_of_int (abs c))^
           "*x"^(string_of_poly' R)
  | (d,1)::R ->
      "+x^"^(string_of_int d)^(string_of_poly' R)
  | (d,-1)::R ->
      "-x^"^(string_of_int d)^(string_of_poly' R)
  | (d,c)::R ->
      (if c < 0 then "-" else "+")^(string_of_int (abs c))^
           "*x^"^(string_of_int d)^(string_of_poly' R) ;;
string_of_poly' : (int * int) list -> string = <fun>

(* le tri *)
#let rec insertion (d,c) poly =
  match poly with [] -> [d,c]
  | (a,b)::R ->
      if d > a then (d,c)::poly
      else (a,b)::(insertion (d,c) R)

and tri_poly = function [] -> []
  | x::R -> insertion x (tri_poly R) ;;
insertion : int * 'a -> (int * 'a) list -> (int * 'a) list = <fun>
tri_poly : (int * 'a) list -> (int * 'a) list = <fun>

#let normaliser P = string_of_poly(tri_poly P) ;;
normaliser : (int * int) list -> string = <fun>
#let normaliser' P = string_of_poly'(tri_poly P) ;;
normaliser' : (int * int) list -> string = <fun>

#normaliser  p ;;
- : string = "+0*x^8+9*x^4+7*x^3+21*x^2-1*x^1+2*x^0"
#normaliser' p ;;
- : string = "+9*x^4+7*x^3+21*x^2-x+2"

#normaliser  (deriver_poly p) ;;
- : string = "+0*x^7+36*x^3+21*x^2+42*x^1+0*x^0-1*x^0"
#normaliser' (deriver_poly p) ;;
- : string = "+36*x^3+21*x^2+42*x-1"


Solution de l'exercice 34

1.#let a = ref (5 - 3 * 2) ;; a : int ref = ref -1 2.#let b = let x = 3 and y = 4, 2 in !a + (snd y) * x, !a*x + fst y ;; b : int * int = 5, 1 3.#let h = function x -> function y -> ( y * (x y) ) ;; h : (int -> int) -> int -> int = 4.#a := h (fun x -> x + x) 5 ;; - : unit = () 5.#a;; - : int ref = ref 50

Solution de l'exercice 35

#let global_numéro = ref 0 ;; global_numéro : int ref = ref 0 #let génère_numéro () = incr global_numéro; !global_numéro ;; génère_numéro : unit -> int = (* Exemple *) #génère_numéro ();; - : int = 1 #génère_numéro ();; - : int = 2 ................... ................... ................... #génère_numéro ();; - : int = 27

Solution de l'exercice 36

let table_articles = [|("Guitare", 3500, 45); ("Banjo", 2300, 18); ("Ukulele", 1800, 34); ("Toere", 2200, 29); ("Flûte à bec", 1100, 55) |] ;; a) #let entrée_en_stock code qte = let (d,p,q) = table_articles.(code) in (d,p,q+qte) ;; entrée_en_stock : int -> int -> string * int * int = #entrée_en_stock 2 7;; - : string * int * int = "Ukulele", 1800, 48 b) #exception erreur_sortie_stock of int ;; Exception erreur_sortie_stock defined. #let sortie_de_stock code qte = let (d,p,q) = table_articles.(code) in if qte > q then raise (erreur_sortie_stock (qte-q)) else (d,p,q-qte) ;; sortie_de_stock : int -> int -> string * int * int = #sortie_de_stock 1 63 ;; Uncaught exception: erreur_sortie_stock 45 #sortie_de_stock 1 15 ;; - : string * int * int = "Banjo", 2300, 3

Solution de l'exercice 37

#type mention = Chèque | Espèce | Carte_bancaire and mode_règlement = COMPTANT of mention | CREDIT and ligne_achat = {code:int;quantité:int} and facture = { nom_client : string; date_facture : int * int * int; livré : bool; règlement : mode_règlement; liste_achats : ligne_achat list } ;; Type mention defined. Type mode_règlement defined. Type ligne_achat defined. Type facture defined. #let exemple_client = { nom_client = "JEAN LEFRANC"; date_facture = (12, 5, 93); livré = true; règlement = COMPTANT Espèce; liste_achats = [ { code = 2 ; quantité = 1 } ; { code = 3 ; quantité = 2 } ; { code = 1 ; quantité = 2 } ] } ;; exemple_client : facture = {nom_client="JEAN LEFRANC"; date_facture=12, 5, 93; l ivré=true; règlement=COMPTANT Espèce; liste_achats=[{code=2; quantité=1}; {code= 3; quantité=2}; {code=1; quantité=2}]}