Correction des exercices
Un article de Mangue.org, l'encyclopéde libre.
Cette page rassemble les corrections des exercices proposés en fin de cours. Beaucoup de lecteurs ont demandé à y avoir accès...
| Sommaire |
Polymorphisme
Voir le cours correspondant
La fonction échange_valeurs prends en argument une paire (un n-uplet) et doit le renvoyer en permuttant ses valeurs. La solution que je vous propose utilise le filtrage :
# let échange_valeurs (a,b) = (b,a) ;;
échange_valeurs : 'a * 'b -> 'b * 'a = <fun>
# échange_valeurs (1,3) ;;
- : int * int = 3, 1
# échange_valeurs ( fst, ()) ;;
- : unit * ('_a * '_b -> '_a) = (), <fun>
# échange_valeurs (`t`,(false,0)) ;;
- : (bool * int) * char = (false, 0), `t`
La fonction échange_double_de_valeurs prends en argument un couple de couples de valeurs. Elles est chargée d'effectuer une double permutation des valeurs.
Je vous propose deux solutions différentes, la première utilisant la fonction échange_valeurs et la seconde utilisant un filtre :
# let échange_double_de_valeurs ((a,b),(c,d)) = ((d,c),(b,a)) ;;
(* version 1 *)
échange_double_de_valeurs : ('a * 'b) * ('c * 'd) -> ('d * 'c) * ('b * 'a) =
<fun>
# let échange_double_de_valeurs (couple1,couple2) =
( échange_valeurs(couple2), échange_valeurs(couple1)) ;;
(* version 2 *)
échange_double_de_valeurs : ('a * 'b) * ('c * 'd) -> ('d * 'c) * ('b * 'a) =
<fun>
# échange_double_de_valeurs ( (1,2), (3,4)) ;;
- : (int * int) * (int * int) = (4, 3), (2, 1)
# échange_double_de_valeurs ( (false,0), (true,1)) ;;
- : (int * bool) * (int * bool) = (1, true), (0, false)
# échange_double_de_valeurs ( (nth_char,()), (`r`,échange_valeurs)) ;;
- : (('_a * '_b -> '_b * '_a) * char) * (unit * (string -> int -> char)) =
(<fun>, `r`), ((), <fun>)
Nous devions ensuite implémenter une fonction assurant la composition de fonctions. Elle prenait en argument les deux fonctions justement ainsi que la valeur sur laquelle effectuer le calcul. Voici une solution très simple :
# let compose f g x = f (g (x)) ;;
compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
# compose float_of_int int_of_char `A` ;;
(* float_of_int ( int_of_char ( `A`)) *)
- : float = 65.0
# compose (fun x -> x + 1) ( fun x -> x * x) (6) ;;
- : int = 37
#let Pi = 4.0 *. atan(1.0) in
compose sin cos (Pi /. 2.0) ;;
(* sin ( cos ( Pi / 2)) *)
- : float = 6.12303176911e-017
Listes
Voir le cours correspondant
La fonction rev inverse l'ordre des valeurs d'une liste. Sa solution est encore une fois récursive. Le cas terminal est lorsque la liste est vide puisqu'il n'y a plus rien à inverser ;-)
Dans son cas général on isole le premier élément et le place en dernière position de la liste comme ceci :
# let rec rev = fun
| [] -> []
| (e :: r) -> rev(r) @ [e] ;;
rev : 'a list -> 'a list = <fun>
# rev [1;2;3;4] ;;
- : int list = [4; 3; 2; 1]
# rev [fst;snd] ;;
- : ('_a * '_a -> '_a) list = [<fun>; <fun>]
La fonction map admet en argument une fonction et une liste de valeurs. Elle applique à chaque valeur de cette liste la fonction passée en arguments et nous renvoie la liste avec les résultats.
# let map f liste =
let rec aux = fun
| [] -> []
| (x :: reste) -> f(x) :: aux(reste)
in
aux liste ;;
map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map float_of_int [1;2;3;4] ;;
- : float list = [1.0; 2.0; 3.0; 4.0]
# map (fun x -> if (x<0) then -x else x) [-5;0;3;-4;3;2;2;1;-8;-6;-2;7] ;;
- : int list = [5; 0; 3; 4; 3; 2; 2; 1; 8; 6; 2; 7]
# let int_of_float_list = map int_of_float ;;
int_of_float_list : float list -> int list = <fun>
# int_of_float_list [1e5;1e-6;1e2;1e3;0.0; 4.0 *. atan(1.0)] ;;
- : int list = [100000; 0; 100; 1000; 0; 3]
La fonction exists prends en argument les éléments de la liste les une après les autres et leur applique une fonction qui renvoie un résultat booléen. Le résultat global est composé de l'union de toutes les valeurs booléennes obtenues (avec un || entre chacune quoi!)
# let exists f liste =
let rec aux = fun
| [] -> false
| (e :: reste) -> f(e) || aux(reste)
in
aux liste ;;
exists : ('a -> bool) -> 'a list -> bool = <fun>
# not ( exists (fun x -> x = 0) [0;1;2;3;4;5]) ;;
(* vérifie qu'il n'y ait pas de 0 dans la liste *)
- : bool = false
# exists (fun x -> x *. x +. 4.0 *. x -. 5.0 =. 0.0) [-. 1.0; 0.0; 1.0] ;;
(* vérifie qu'il y ait une solution au trinôme dans la liste *)
- : bool = true
Structures de données
Voir le cours correspondant
Voici les fonctions pour le type complex, elles ne sont pas expliquées car assez faciles à comprendre à mon avis, mais si vous avez des problèmes foncez sur le forum !
# let module_cplx {Re=a;Im=b} = sqrt( a ** 2.0 +. b ** 2.0) ;;
module_cplx : complex -> float = <fun>
# let argument_cplx {Re=a;Im=b} = atan(b /. a) ;;
argument_cplx : complex -> float = <fun>
# let conjugué_cplx {Re=a;Im=b} = {Re = a;Im = -.b} ;;
conjugué_cplx : complex -> complex = <fun>
# let somme_cplx {Re=a1;Im=b1} {Re=a2;Im=b2} = {Re=a1+.a2;Im=b1+.b2} ;;
somme_cplx : complex -> complex -> complex = <fun>
# let différence_cplx {Re=a1;Im=b1} {Re=a2;Im=b2} = {Re=a1-.a2;Im=b1-.b2} ;;
différence_cplx : complex -> complex -> complex = <fun>
# let produit_cplx {Re=a1;Im=b1} {Re=a2;Im=b2} =
{Re=a1 *. a2 -. b1 *. b2; Im = a1 *. b2 +. a2 *. b1} ;;
produit_cplx : complex -> complex -> complex = <fun>
# let quotient_cplx = fun
| _ {Re=0.0;Im=0.0} -> invalid_arg "quotient_cplx: divison par 0 impossible"
| {Re=a1;Im=b1} {Re=a2;Im=b2} ->
let diviseur = a2 ** 2.0 +. b2 ** 2.0 in
{Re= (a1 *. a2 +. b1 *. b2) /. diviseur; Im = ( b1 *. a2 -. a1 *. b2) /. diviseur} ;;
quotient_cplx : complex -> complex -> complex = <fun>
La fonction créditer prends deux arguments, le premier est le compte sur lequel va oirter l'opération et le second est la somme à créditer (ou débiter). Voici une correction possible :
# let créditer compte_banque somme = compte_banque.solde <- compte_banque.solde +. somme ;; créditer : compte -> float -> unit = <fun>
Voilà les fonctions permettant d'effectuer des opérations simples sur les nombres rationels... D'autres solutions sont possibles évidemment, si vous avez un doute demandez tout simplement. Mais si vos essai en Caml fournissent les résultats attendus alors il y a toutes les chances que vos fonctions soient correctes :-)
# let somme_rationnel = fun
| (Entier a) (Entier b) -> Entier (a+b)
| (Fraction {Numérateur=a1;Dénominateur=b1}) (Fraction {Numérateur=a2;Dénominateur=b2}) ->
Fraction {Numérateur=a1*b2+a2*b1;Dénominateur=b1*b2}
| (Décimal a) (Décimal b) -> Décimal (a+.b)
(* pour les autres cas on essai de conserver le maximum de précision => Fraction ! *)
| nombre_rationnel (Fraction {Numérateur=a2;Dénominateur=b2}) ->
let {Numérateur=a1;Dénominateur=b1} = fact_of_rationnel (nombre_rationnel)
in Fraction {Numérateur=a1*b2+a2*b1;Dénominateur=b1*b2}
| (Fraction {Numérateur=a1;Dénominateur=b1}) nombre_rationnel ->
let {Numérateur=a2;Dénominateur=b2} = fact_of_rationnel (nombre_rationnel)
in Fraction {Numérateur=a1*b2+a2*b1;Dénominateur=b1*b2}
| (Décimal d) (Entier e) -> Décimal (d +. float_of_int(e))
| (Entier e) (Décimal d) -> Décimal (d +. float_of_int(e)) ;;
somme_rationnel : rationnel -> rationnel -> rationnel = <fun>
# let opposé_rationnel = fun
| (Entier x) -> Entier (-x)
| (Fraction {Numérateur = a;Dénominateur = b}) -> Fraction {Numérateur = -a;Dénominateur = b}
| (Décimal x) -> Décimal (-. x) ;;
opposé_rationnel : rationnel -> rationnel = <fun>
# let soustraction_rationnel rationnel1 rationnel2 = somme_rationnel rationnel1 (opposé_rationnel rationnel2) ;;
soustraction_rationnel : rationnel -> rationnel -> rationnel = <fun>
| Astuce |
Ecrivez vous même les autres fonctions multiplication_rationnel, quotient_rationnel.Comme toujours si vous avez des problèmes réagissez sur le forum... |
Récurrence structurelle
Voir le cours correspondant
Pour transformer une int liste_simple en chaîne de caractère nbous allons écrire une fonction, forcément récursive, qui renverra une chaîne vide dans le cas d'une liste vide. Dans les autres cas nous renverrons le premier élément de la liste simple sous forme de chaîne de caractère (donc fonction string_of_int) concaténé au traitement par la fonction du reste de la liste simple comme ceci :
# let rec string_of_liste_simple = fun | NULL -> "" | (Data(e,NULL)) -> string_of_int(e) | (Data(e,suite)) -> string_of_int(e) ^ ";" ^ string_of_liste_simple (suite) ;; string_of_liste_simple : int liste_simple -> string = <fun> # string_of_liste_simple liste2 ;; - : string = "0;1;2"
string_of_Tree est une fonction relativement facile à implémenter... Le cas simple correspond à une feuille, il suffit de la transformer en chaîne de carctère avec string_of_int, quant au reste et bien une chaîne de cartère est définie pour chaque opérateur, on aurait pu écrire uen fonction locale pour assurer la correspondance des opérateurs avec leurs représentation sous forme de chaîne mais je ne l'ai pas fait. Et la récursivité traite le reste de façon naturelle... La fonction est donc écrite :
# let rec string_of_Tree = fun
| (Leaf x) when (x<0) -> "(" ^ string_of_int(x) ^ ")"
| (Leaf x) -> string_of_int(x)
| (Knot(x,y,OpMult)) -> "(" ^ string_of_Tree(x) ^ "*" ^ string_of_Tree(y) ^ ")"
| (Knot(x,y,OpDivi)) -> "(" ^ string_of_Tree(x) ^ "/" ^ string_of_Tree(y) ^ ")"
| (Knot(x,y,OpSum)) -> "(" ^ string_of_Tree(x) ^ "+" ^ string_of_Tree(y) ^ ")"
| (Knot(x,y,OpSub)) -> "(" ^ string_of_Tree(x) ^ "-" ^ string_of_Tree(y) ^ ")"
| (Knot(x,y,OpMod)) -> "(" ^ string_of_Tree(x) ^ "mod" ^ string_of_Tree(y) ^ ")" ;;
string_of_Tree : int Tree -> string = <fun>
# string_of_Tree (ArbreBinaire) ;;
- : string = "((2*(0-(-1)))+(1+4))"
| Astuce |
Nous aurions pu écrire une structure if plutôt que d'utiliser un when, mais il faut varier les plaisirs comme disent certains ;-p
|
Références et vecteurs
Voir le cours correspondant
echange est une fonction permettant d'intervertir les valeurs de deux références. Sa définition n'est pas très complexe, nous avons simplement besoin d'une sorte de mémoire tampon pour stocker la valeur avant échange. Voici une correction possible :
# let echange ref_a ref_b = let tmp = !ref_a in ref_a := !ref_b; ref_b := tmp;; echange : 'a ref -> 'a ref -> unit = <fun> # let a,b = ref 0, ref 1 ;; a : int ref = ref 0 b : int ref = ref 1 # echange a b ;; - : unit = () # !a ;; - : int = 1 # !b ;; - : int = 0
La fonction somme permettant d'additionner tous les éléments d'un vecteur est récursive. Elle prends en unique argument le vecteur et nous renvoie le résultat en unique valeur. Il convient donc de définir localement une fonction effectuant le traitement récursif. Voici une correction possible :
# let somme vecteur = let rec aux = fun | 0 -> vecteur.(0) | n -> vecteur.(n) + aux (n-1) in aux (vect_length(vecteur)-1) ;; somme : int vect -> int = <fun> # somme (vecteur) ;; - : int = 6 # somme [| 0; 1; -1; 2; 3 |] ;; - : int = 5
