In [12]:
let print = Printf.printf;;
Sys.command "ocaml -version";;
Out[12]:
Out[12]:
In [2]:
let successeur (n : int) : int =
n + 1
;;
Out[2]:
In [3]:
successeur(3);;
successeur(2 * 2);;
successeur(2.5);;
Out[3]:
Out[3]:
In [4]:
let produit3 (x : int) (y : int) (z : int) : int =
x * y * z
;;
let produit3_2 =
fun (x : int) (y : int) (z : int) : int ->
x * y * z
;;
let produit3_3 =
fun (x : int) ->
fun (y : int) ->
fun (z : int) : int ->
x * y * z
;;
let produit3_4 (tuple : (int * int * int)) : int =
let x, y, z = tuple in
x * y * z
;;
Out[4]:
Out[4]:
Out[4]:
Out[4]:
In [5]:
produit3 1 2 3;;
produit3_2 1 2 3;;
(produit3_3 1)(2);; (* fun (z : int) -> int : 1 * 2 * z *)
((produit3_3 1)(2))(3);;
produit3_4 (1, 2, 3);;
Out[5]:
Out[5]:
Out[5]:
Out[5]:
Out[5]:
In [8]:
let print = Printf.printf;;
let exercice6 (n : int) : unit =
for i = 1 to n do
print "%i\n" i;
done;
for i = n downto 1 do
print "%i\n" i;
done;
flush_all ();
;;
Out[8]:
Out[8]:
In [10]:
exercice6(4)
Out[10]:
In [13]:
let rec factoriel = function
| 0 -> 1
| n -> n * factoriel ( n - 1 );;
let rec factoriel = fun n ->
match n with
| 0 -> 1
| n -> n * factoriel ( n - 1 );;
let rec factoriel (n:int) : int =
match n with
| 0 -> 1
| n -> n * factoriel ( n - 1 );;
let rec factoriel (n:int) : int =
if n = 0
then 1
else n * factoriel ( n - 1 );;
Out[13]:
Out[13]:
Out[13]:
Out[13]:
In [16]:
factoriel 4;;
factoriel 0;;
for i = 1 to 8 do
print "%i! = %i\n" i (factoriel i)
done;;
flush_all ();;
Out[16]:
Out[16]:
Out[16]:
Out[16]:
In [17]:
(* Remarque: si a>b alors pgcd a b = pgcd (a-b) b *)
let rec pgcd (a : int) (b : int) : int =
if a = b
then a
else
if (a > b)
then pgcd (a-b) b
else pgcd a (b-a)
;;
Out[17]:
In [18]:
pgcd 16 1024;;
pgcd 25 130;;
Out[18]:
Out[18]:
Utilisons le générateur de nombres aléatoires pour faire quelques tests :
In [19]:
Random.self_init();;
Out[19]:
In [20]:
for _ = 1 to 10 do
let x = 1 + Random.int 100
and y = 1 + Random.int 100 in
let d = pgcd x y in
print " %i ^ %i = %i\n" x y d;
done;;
flush_all ();;
Out[20]:
Out[20]:
In [21]:
(* fonction naive *)
let rec fibonacci (n : int) : int =
match n with
| 0 -> 1
| 1 -> 1
| n -> fibonacci (n-1) + fibonacci (n-2)
;;
Out[21]:
Avec ce morceau de code on peut facilement mesurer le temps d'exécution :
In [22]:
let time (f : unit -> 'a) : 'a =
let t = Sys.time() in
let res = f () in
Printf.printf " Temps en secondes: %fs\n" (Sys.time() -. t);
flush_all ();
res
;;
Out[22]:
In [23]:
fibonacci 5;;
fibonacci 17;;
Out[23]:
Out[23]:
In [24]:
time (fun () -> fibonacci 40);;
Out[24]:
In [26]:
let fibonacci_lin (n : int) : int =
(* invariant:
m >= 1
u = fibo(n-m+1)
v = fibo(n-m)
aux m u v = fibo(n) *)
let rec aux (m : int) (u : int) (v : int) : int =
assert (m>0);
if m = 1 then u
else aux (m-1) (u+v) u
in aux n 1 1
;;
Out[26]:
In [27]:
for i = 1 to 10 do
assert ((fibonacci i) = (fibonacci_lin i))
done;;
Out[27]:
In [28]:
time (fun () -> fibonacci_lin 35);;
Out[28]:
In [29]:
time (fun () -> fibonacci_lin 40);;
Out[29]:
Voilà la différence.
In [30]:
let rec itere (f : 'a -> 'a) (n : int) : 'a -> 'a =
match n with
| 0 -> (fun x -> x);
| n -> (fun x -> f (itere (f) (n - 1) x))
;;
Out[30]:
In [31]:
(itere (fun x -> x + 1) 10)(1);;
Out[31]:
In [33]:
let print = Printf.printf;;
let rec hanoi (n : int) (a : string) (b : string) (c : string) : unit =
if n > 1 then
hanoi (n-1) a c b;
print "%s -> %s\n" a c;
if n > 1 then
hanoi (n-1) b a c;
flush_all ();
;;
Out[33]:
Out[33]:
In [34]:
hanoi 1 "T1" "T2" "T3";;
Out[34]:
In [35]:
hanoi 2 "T1" "T2" "T3";;
Out[35]:
In [36]:
hanoi 5 "T1" "T2" "T3";; (* 2^5 - 1 = 31 coups *)
Out[36]:
Avec un compteur de coups joués (ce sera toujours $2^n - 1$) :
In [38]:
let rec hanoi2 (n : int) (a : string) (b : string) (c : string) : int =
if n > 1 then begin
let coup = ref 0 in
coup := !coup + (hanoi2 (n-1) a c b);
print "%s -> %s\n" a c;
coup := !coup + (hanoi2 (n-1) b a c);
flush_all ();
!coup + 1
end else begin
print "%s -> %s\n" a c;
flush_all ();
1;
end;
;;
Out[38]:
In [39]:
hanoi2 2 "T1" "T2" "T3";;
Out[39]:
In [40]:
let rec concatenation (l1 : 'a list) (l2 : 'a list) : 'a list =
match l1 with
| [] -> l2
| t :: q -> t :: (concatenation q l2)
;;
Out[40]:
In [41]:
concatenation [1; 2; 3] [4; 5];;
Out[41]:
In [42]:
List.append [1; 2; 3] [4; 5];;
Out[42]:
In [43]:
let rec applique (f : 'a -> 'b) (liste : 'a list) : 'b list =
match liste with
| [] -> []
| t :: q -> (f t) :: (applique f q)
;;
Out[43]:
In [44]:
applique (fun x -> x + 1) [1; 2; 3];;
Out[44]:
In [45]:
let plus_un_liste = applique ((+) 1);;
plus_un_liste [1; 2; 3];; (* syntaxe sympa *)
Out[45]:
Out[45]:
Avantage à la notation concise applique f l autorise à avoir (applique f)(l) au lieu de faire fun l -> applique l f si les deux arguments étaient dans l'autre sens.
In [46]:
let liste_carree = applique (fun x -> x*x);;
Out[46]:
In [47]:
liste_carree [1; 2; 3];;
Out[47]:
In [1]:
let rec miroir_quad : 'a list -> 'a list = function
| [] -> []
| a :: q -> (miroir_quad q) @ [a]
;;
let miroir_lin (liste : 'a list) : 'a list =
(* sous fonction utilisant un deuxieme argument d'accumulation du resultat *)
let rec miroir (l : 'a list) (accu : 'a list) : 'a list =
match l with
| [] -> accu
| a :: q -> miroir q (a::accu)
in
miroir liste []
;;
Out[1]:
Out[1]:
In [49]:
miroir_quad [1; 2; 3];;
miroir_lin [1; 2; 3];;
Out[49]:
Out[49]:
In [50]:
time (fun () -> miroir_quad [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20]);;
time (fun () -> miroir_lin [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20]);;
(* Pas de différence observable ici *)
Out[50]:
Out[50]:
In [51]:
let longue_liste (n : int) : int list =
Array.to_list (Array.init n (fun i -> i))
;;
Out[51]:
Avec de grandes listes, on voit la différence.
In [52]:
let _ = time (fun () -> miroir_quad (longue_liste 10000));;
let _ = time (fun () -> miroir_lin (longue_liste 10000));;
Out[52]:
Out[52]:
In [53]:
let rec insertionDansListeTriee (liste : 'a list) (x : 'a) : 'a list =
match liste with
| [] -> [x]
| t :: q when t < x -> t :: (insertionDansListeTriee q x)
| _ -> x :: liste (* x est plus petit que le plus petit de la liste *)
;;
Out[53]:
In [54]:
insertionDansListeTriee [1; 2; 5; 6] 4;;
Out[54]:
In [55]:
let triInsertion (liste : 'a list) : 'a list =
let rec tri (l : 'a list) (accu : 'a list) : 'a list =
match l with
| [] -> accu
| t :: q -> tri q (insertionDansListeTriee accu t)
in
tri liste []
;;
Out[55]:
In [56]:
triInsertion [5; 2; 6; 1; 4];;
Out[56]:
In [57]:
type 'a ordre = 'a -> 'a -> 'a;;
Out[57]:
In [58]:
let ordre_croissant : int ordre =
fun (x : int) (y : int) ->
match y with
| yv when yv = x -> 0
| yv when yv < x -> +1
| yv when yv > x -> -1
| _ -> failwith "Erreur comparaison impossible (ordre_decroissant)"
;;
let ordre_decroissant : int ordre =
fun (x : int) (y : int) ->
match y with
| yv when yv = x -> 0
| yv when yv < x -> -1
| yv when yv > x -> +1
| _ -> failwith "Erreur comparaison impossible (ordre_decroissant)"
;;
Out[58]:
Out[58]:
In [59]:
let rec insertionDansListeTrieeOrdre (ordre : 'a ordre) (liste : 'a list) (x : 'a) : 'a list =
match liste with
| [] -> [x]
| t :: q when (ordre t x < 0) -> t :: (insertionDansListeTrieeOrdre ordre q x)
| _ -> x :: liste (* x est plus petit que le plus petit de la liste *)
;;
Out[59]:
In [60]:
insertionDansListeTrieeOrdre ordre_decroissant [6; 5; 2; 1; 2] 4;;
Out[60]:
In [61]:
let triInsertionOrdre (ordre : 'a ordre) (liste : 'a list) : 'a list =
let rec tri (l : 'a list) (accu : 'a list) : 'a list =
match l with
| [] -> accu
| t :: q -> tri q (insertionDansListeTrieeOrdre ordre accu t)
in
tri liste []
;;
Out[61]:
In [62]:
triInsertionOrdre ordre_decroissant [5; 2; 6; 1; 4];;
Out[62]:
In [63]:
triInsertionOrdre ordre_croissant [5; 2; 6; 1; 4];;
Out[63]:
In [64]:
let rec puiss (x : int) : int -> int = function
| 0 -> 1
| n -> x * (puiss x (n-1))
;;
Out[64]:
Complexité : linéaire ($\mathcal{O}(x)$)...
In [67]:
let x = 3 in
for n = 0 to 10 do
print " %i ** %i = %i\n" x n (puiss x n);
done;;
flush_all ();;
Out[67]:
Out[67]:
In [68]:
let rec puissRapide (x : int) : int -> int = function
| 0 -> 1
| n when (n mod 2) = 0 -> puissRapide (x * x) (n / 2)
| n -> (puissRapide (x * x) ((n-1)/2)) * x
(* Important de mettre * x à droite pour être récursive terminale. *)
;;
Out[68]:
Complexité : logarithmique ($\mathcal{O}(\log_2 x)$).
In [69]:
let x = 3 in
for n = 0 to 10 do
print " %i ** %i = %i\n" x n (puissRapide x n);
done;;
flush_all ();;
Out[69]:
Out[69]:
In [1]:
(* le type monoide *)
type 'a monoide = { mult : 'a -> 'a -> 'a; neutre : 'a };;
Out[1]:
Avec des champs d'enregistrement, c'est concis :
In [17]:
(* Ca rale ici ! *)
let floatmonoide = {
mult = fun a b -> a *. b;
(* ce ; est quoi ? fin de fun ou fin de mult ? *)
neutre = 1.0
}
In [18]:
let floatmonoide = {
mult = (fun a b -> a *. b);
neutre = 1.0
}
Out[18]:
In [19]:
let floatMonoide : 'float monoide = {
mult = ( *. ); (* fun x y -> x *. y *)
neutre = 1.
};;
Out[19]:
Par contre, impossible d'avoir un neutre de taille quelconque donc on doit écrire un monoied pour les matrices qui soit dépendent d'une taille $n$.
In [3]:
let mult_matrice (x : int array array) (y : int array array) : int array array =
let n = Array.length x in
let z = Array.make_matrix n n 0 in
for i = 0 to n-1 do
for j = 0 to n-1 do
for k = 0 to n-1 do
z.(i).(j) <- z.(i).(j) + x.(i).(k) * y.(k).(j)
done
done
done;
z
;;
Out[3]:
In [4]:
mult_matrice [| [|1; 1|]; [|1; 1|]|] [|[|1; 2|]; [|3; 4|]|];;
Out[4]:
Manuellement ce n'est pas trop dur :
In [5]:
let matrixMonoide n = {
mult = mult_matrice;
neutre = Array.init n (fun i -> Array.init n (fun j -> if i = j then 1 else 0));
};;
Out[5]:
In [6]:
let rec exp_rapide (m : 'a monoide) (x : 'a) (n : int) : 'a =
match n with
| 0 -> m.neutre
| n -> m.mult (exp_rapide m x (n-1)) x
;;
Out[6]:
Avec l'approche récursive :
In [10]:
let rec exp_rapide (m : 'a monoide) (x : 'a) (n : int) : 'a =
match n with
| 0 -> m.neutre
| n when (n mod 2) = 0 -> exp_rapide m (m.mult x x) (n / 2)
| n -> m.mult (exp_rapide m (m.mult x x) ((n-1)/2)) x
;;
Out[10]:
In [11]:
let exp_rapide_float = exp_rapide floatMonoide;;
Out[11]:
In [12]:
exp_rapide_float 2.0 8;;
Out[12]:
In [13]:
exp_rapide_float 0.2 8;;
Out[13]:
Et pour les matrices, un petit piège à cause des tailles :
In [79]:
let exp_rapide_mat x n = exp_rapide (matrixMonoide (Array.length x)) x n;;
Out[79]:
In [80]:
exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 0;;
exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 1;;
exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 2;;
exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 3;;
exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 4;;
Out[80]:
Out[80]:
Out[80]:
Out[80]:
Out[80]:
In [81]:
(* nilpotente ! *)
exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 0;;
exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 1;;
exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 2;;
exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 3;;
exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 4;;
Out[81]:
Out[81]:
Out[81]:
Out[81]:
Out[81]:
In [82]:
let monoideFonction = {
mult = (fun f g x -> f (g x) );
neutre = (fun x -> x)
};;
let itereMonoide f n = exp_rapide monoideFonction f n;;
Out[82]:
Out[82]:
In [83]:
itereMonoide (fun x -> x + 1) 10 0;;
itereMonoide ((+) 1) 10 0;;
Out[83]:
Out[83]:
In [2]:
type variable = string;;
type formule =
| V of variable
| Non of formule
| Conj of formule * formule
| Disj of formule * formule
;;
Out[2]:
Out[2]:
In [3]:
let f = (
Conj(
Non(V("p")),
Disj(
Conj(V("q"), Non(V("p"))),
Disj(V("r"), V("q"))
)
)
) ;;
Out[3]:
In [4]:
let rec taille : formule -> int = function
| V(_) -> 1
| Non(f) -> 1 + (taille f)
| Conj(f,g) -> 1 + (taille f) + (taille g)
| Disj(f,g) -> 1 + (taille f) + (taille g)
;;
Out[4]:
In [87]:
taille f;;
Out[87]:
In [5]:
let rec formule_to_string : formule -> string = function
| V(p) -> p
| Non(f) -> "non "^(formule_to_string f)
| Conj(f,g) -> "("^(formule_to_string f)^" ^ "^(formule_to_string g)^")"
| Disj(f,g) -> "("^(formule_to_string f)^" v "^(formule_to_string g)^")"
;;
Out[5]:
In [6]:
let print = Printf.printf;;
let affiche (f : formule) : unit =
print "%s\n" (formule_to_string f);
flush_all ();
;;
Out[6]:
Out[6]:
In [7]:
affiche f;;
Out[7]:
Et voilà. Pas si difficile non ?
In [8]:
type valuation = variable -> bool;;
let rec eval (v : valuation) : formule -> bool = function
| V(x) -> v(x)
| Non(f) -> not (eval v f)
| Conj(f,g) -> (eval v f) && (eval v g)
| Disj(f,g) -> (eval v f) || (eval v g)
;;
let valuFalse : valuation = function
| "p" -> true
| "q" -> false
| "r" -> false
| _ -> false
;;
let valuTrue : valuation = function
| "p" -> false
| "q" -> false
| "r" -> true
| _ -> false
;;
Out[8]:
Out[8]:
Out[8]:
Out[8]:
In [93]:
eval valuTrue f;;
Out[93]:
In [94]:
eval valuFalse f;;
Out[94]:
In [9]:
let rec inserUneFois (x : 'a) : ('a list -> 'a list) = function
| [] -> [x]
| t :: q when (x = t) -> t :: q
| t :: q -> t :: (inserUneFois x q)
;;
Out[9]:
In [10]:
let recupererVariable (f : formule) : variable list =
let rec recup (l : variable list) : formule -> variable list = function
| V(x) -> inserUneFois x l
| Non(f) -> recup l f
| Conj(f,g) -> recup (recup l f) g
| Disj(f,g) -> recup (recup l f) g
in
recup [] f
;;
Out[10]:
In [11]:
recupererVariable f;;
Out[11]:
In [12]:
let rec nouvelleValu (v : valuation) : 'a list -> valuation = function
| [] -> v
| t :: q ->
if (v t) then
let nv x = if (x = t) then false else v x in
nouvelleValu nv q
else function x ->
if (x = t) then true else v x
;;
Out[12]:
In [13]:
let rec isTrue (v : valuation) : variable list -> bool = function
| [] -> true
| t :: q -> if v t then isTrue v q else false
;;
Out[13]:
In [14]:
let rec valuToString (v : valuation) : variable list -> string = function
| [] -> ""
| t :: q -> (if v t then "1" else "0") ^ " " ^ (valuToString v q)
;;
Out[14]:
In [17]:
let print = Printf.printf;;
let rec printVariableList : variable list -> unit = function
| [ ] -> print "| "
| t :: q ->
print "%s " t;
flush_all ();
printVariableList q
;;
Out[17]:
Out[17]:
In [18]:
let tableVerite (f : formule) : unit =
let variables = recupererVariable f in
let valu = ref (function _ -> false) in
(* on construit dynamiquement la nouvelle valuation... moche mais ça marche *)
printVariableList variables;
affiche f;
while not (isTrue (!valu) variables) do
print_string ( (valuToString (!valu) variables)^"| "^(if eval (!valu) f then "1" else "0")^"\n");
valu := nouvelleValu (!valu) variables
done
;;
Out[18]:
In [19]:
tableVerite f;;
Out[19]:
On peut vérifier, par exemple sur Wolfram|Alpha que l'on obtient bien le bon résultat...
Voilà pour aujourd'hui !
Cette solution est aussi disponible en Python : TP1__Python.ipynb.
Là où Caml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles...