Exercices
Exercice 1 (Quelques fonctions simples)
1-1.
#let f x = x*x+3*x-2;;
f : int -> int = <fun>
1-2.
#let rec power n p =
if p = 0 then 1 else
if p = 1 then n else
let aux = power n (p/2) in
if p mod 2 = 0 then aux * aux else aux * aux * n;;
power : int -> int -> int = <fun>
1-3.
Avec une liste en fonctionnel
#let rec f n =
if n < 100 || n >= 1000 then [] else
let c = n / 100
and d = (n/10) mod 10
and u = n mod 10 in
if c*c*c+d*d*d+u*u*u=n then n::(f (n+1)) else (f (n+1));;
f : int -> int list = <fun>
#f 0;;
- : int list = []
En imprimant en impératif
#let test_cubes () =
for c = 1 to 9 do
for d = 0 to 9 do
for u = 0 to 9 do
let n = c*100+d*10+u in
if c*c*c + d*d*d + u*u*u = n then (print_int n; print_string " ")
done;
done;
done; print_newline();;
test_cubes : unit -> unit = <fun>
#test_cubes();;
153 370 371 407
- : unit = ()
Exercice 2 (Représentation et manipulation de matrices)
2-1.
#let produit_scalaire v1 v2 =
let n1 = vect_length v1
and n2 = vect_length v2 in
if n1 <> n2
then failwith "produit_scalaire: vecteurs de longueurs différentes"
else
let p = ref 0 in
for i = 0 to n1-1 do
p := !p+v1.(i)*v2.(i);
done; !p;;
produit_scalaire : int vect -> int vect -> int = <fun>
2-2.
#let produit_matrices m1 m2 =
let l1 = vect_length m1
and c1 = vect_length m1.(0)
and l2 = vect_length m2
and c2 = vect_length m2.(0) in
if c1 <> l2
then failwith "produit_matrices: matrices de tailles incompatibles"
else
let c = make_matrix l1 c2 0 in
for i = 0 to l1-1 do
for j = 0 to c2-1 do
for k = 0 to c1-1 do
c.(i).(j) <- c.(i).(j)+m1.(i).(k)*m2.(k).(j);
done;
done;
done;
c;;
produit_matrices : int vect vect -> int vect vect -> int vect vect = <fun>
Exercice 3 (Les listes simples, filtrage et itérateurs)
3-1.
#let élément2 l = match l with
| _::x2::_ -> x2
| _ -> failwith "élément2: |liste| < 2";;
élément2 : 'a list -> 'a = <fun>
3-2.
#let rec somme l = match l with
| [] -> 0
| e::l' -> e+(somme l');;
somme : int list -> int = <fun>
ou avec l'itérateur sigma vu en cours
#let somme l = sigma (function x -> x) l;;
somme : int list -> int = <fun>
3-3.
#let rec print_int_list l = match l with
| [] -> ()
| e::l'-> print_int e; print_int_list l';;
print_int_list : int list -> unit = <fun>
ou avec l'itérateur do_list prédéfini
#let print_list l = do_list print_int l;;
print_list : int list -> unit = <fun>
3-4.
#let rec incr_list i l = match l with
| [] -> []
| e::l' -> (e+i)::(incr_list i l');;
incr_list : int -> int list -> int list = <fun>
3-5.
Avec l'itérateur map prédéfini
#let incr_list i l = map (function x -> x+i) l;;
incr_list : int -> int list -> int list = <fun>
3-6.
#let rec incr_list2 i l = match l with
| [] -> []
| (x, y)::l' -> (x+i, y)::(incr_list2 i l');;
incr_list2 : int -> (int * 'a) list -> (int * 'a) list = <fun>
Avec l'itérateur map
#let incr_list2 i l = map (function (x, y) -> (x+i,y)) l;;
incr_list2 : int -> (int * 'a) list -> (int * 'a) list = <fun>
3-7.
#let rec prem_comp l = match l with
| [] -> []
| (x, y)::l' -> x::(prem_comp l');;
prem_comp : ('a * 'b) list -> 'a list = <fun>
Avec l'itérateur map
#let prem_comp l = map (function (x, y) -> x) l;;
prem_comp : ('a * 'b) list -> 'a list = <fun>
3-8.
#let rec incr_prem_list i l = match l with
| [] -> []
| e::l' -> (match e with
| [] -> []
| x::l1 -> (x+i)::l1)::(incr_prem_list i l');;
incr_prem_list : int -> int list list -> int list list = <fun>
Avec l'itérateur map
#let incr_prem_list i l =
map (function e -> match e with
| [] -> []
| x::l1 -> (x+i)::l1) l;;
incr_prem_list : int -> int list list -> int list list = <fun>
ou plus simplement
#let rec incr_prem_list i l = match l with
| [] -> []
| []::l' -> (incr_prem_list i l')
| (x::l1)::l' -> ((x+i)::l1)::(incr_prem_list i l');;
incr_prem_list : int -> int list list -> int list list = <fun>
#let lli = [[1;2;3];[4;5]];;
lli : int list list = [[1; 2; 3]; [4; 5]]
#incr_prem_list 10 lli;;
- : int list list = [[11; 2; 3]; [14; 5]]
Sur une liste d'entiers ou une liste de liste de liste d'entiers, on
obtient une erreur de typage, comme le montrent les exemples
ci-dessous:
#let li = [1;2;3];;
li : int list = [1; 2; 3]
#incr_prem_list 10 li;;
Entrée interactive:
>incr_prem_list 10 li;;
> ^^
Cette expression est de type int list,
mais est utilisée avec le type int list list.
#let llli = [[[1;2];[3]];[[4];[5;6;7]]];;
llli : int list list list = [[[1; 2]; [3]]; [[4]; [5; 6; 7]]]
#incr_prem_list 10 llli;;
Entrée interactive:
>incr_prem_list 10 llli;;
> ^^^^
Cette expression est de type int list list list,
mais est utilisée avec le type int list list.
Exercice 4 (Exceptions)
#exception pas_grave of int;;
L'exception pas_grave est définie.
#exception grave of string;;
L'exception grave est définie.
#let pseudo_id x =
if (x < 0) then raise (pas_grave (-x))
else if (x = 0) then raise (grave "Argh !!!") else x ;;
pseudo_id : int -> int = <fun>
#pseudo_id(-4);;
Exception non rattrapée: pas_grave 4
#pseudo_id(0);;
Exception non rattrapée: grave "Argh !!!"
#pseudo_id(2);;
- : int = 2
#let f = let val = 10 in function x ->
try let val = 100 in pseudo_id(x) - val with
| pas_grave n -> if (n < 0) then raise(grave "impossible ?") else n + val
| grave "Argh !!!" -> raise(pas_grave(10))
| grave s -> raise(grave "possible ?");;
f : int -> int = <fun>
#f(-100);;
- : int = 110
#f(0);;
Exception non rattrapée: pas_grave 10
#f(100);;
- : int = 0
#f(grave "Ouf !!!");;
Entrée interactive:
>f(grave "Ouf !!!");;
> ^^^^^^^^^^^^^^^
Cette expression est de type exn,
mais est utilisée avec le type int.
#f(raise(grave "Ouf !!!"));;
Exception non rattrapée: grave "Ouf !!!"
Exercice 5 (Itérateurs classiques sur les listes)
5-1.
#let rec it_list f a l = match l with
| [] -> a
| x::l' -> it_list f (f a x) l';;
it_list : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
5-2.
#let rec list_it f l b = match l with
| [] -> b
| x::l' -> list_it f l' (f x b);;
list_it : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
Par exemple la fonction somme vue précédemment peut être
écrite
#let somme l = list_it (prefix +) l 0;;
somme : int list -> int = <fun>
Vous pouvez en chercher d'autres.
Exercice 6 (Itérateurs map et do_ sur les arbres binaires)
6-1.
#type 'a tree = Empty | Node of 'a * 'a tree * 'a tree;;
Le type tree est défini.
6-2.
#let rec print_tree_prefix a = match a with
| Empty -> ()
| Node (e, fg, fd) -> print_int e; print_tree_prefix fg; print_tree_prefix fd;;
print_tree_prefix : int tree -> unit = <fun>
6-3.
#let rec map_tree f a = match a with
| Empty -> Empty
| Node (e, fg, fd) -> Node (f e, map_tree f fg, map_tree f fd);;
map_tree : ('a -> 'b) -> 'a tree -> 'b tree = <fun>
#let rec do_tree_infix f a = match a with
| Empty -> ()
| Node (e, fg, fd) -> do_tree_infix f fg; f e; do_tree_infix f fd;;
do_tree_infix : ('a -> 'b) -> 'a tree -> unit = <fun>
#let print_tree_prefix a = do_tree_infix print_int a;;
print_tree_prefix : int tree -> unit = <fun>
6-4.
#let rec tree_list a = match a with
| Empty -> []
| Node (e, fg, fd) -> (tree_list fg)@(e::(tree_list fd));;
tree_list : 'a tree -> 'a list = <fun>
6-5.
#let rec insert_tree x a = match a with
| Empty -> Node (x, Empty, Empty)
| Node (e, fg, fd) ->
if x < e
then Node (e, insert_tree x fg, fd)
else Node (e, fg, insert_tree x fd);;
insert_tree : 'a -> 'a tree -> 'a tree = <fun>
6-6.
#let rec tree_sort l = match l with
| [] -> Empty
| e::l' -> insert_tree e (tree_sort l');;
tree_sort : 'a list -> 'a tree = <fun>
#let rec tree_sort_list l = tree_list (tree_sort l);;
tree_sort_list : 'a list -> 'a list = <fun>
6-7.
#let tree_sort l = (list_it insert_tree l Empty);;
tree_sort : 'a list -> 'a tree = <fun>
6-8.
Il nous faut permuter les arguments de la fonction insert_tree
#let rec insert_tree a x = match a with
| Empty -> Node (x, Empty, Empty)
| Node (e, fg, fd) ->
if x < e
then Node (e, insert_tree fg x, fd)
else Node (e, fg, insert_tree fd x);;
insert_tree : 'a tree -> 'a -> 'a tree = <fun>
#let tree_sort_list l = tree_list (it_list insert_tree Empty l);;
tree_sort_list : 'a list -> 'a list = <fun>
Exercice 7 (Utilisation des listes pour une version naïve du crible
d'Eratosthene, de la factorisation d'entiers et calcul du pgcd)
7-1.
#let rec ote_multiples n l = match l with
| [] -> []
| m::l -> if m mod n = 0
then ote_multiples n l
else m::(ote_multiples n l);;
ote_multiples : int -> int list -> int list = <fun>
avec l'itérateur filter
#let ote_multiples n l = filter (function m -> m mod n = 0) l;;
ote_multiples : int -> int list -> int list = <fun>
7-2.
#let rec teste_diviseurs n = function
| [] -> []
| m::l -> if n mod m = 0
then m::(teste_diviseurs n l)
else (teste_diviseurs n l);;
teste_diviseurs : int -> int list -> int list = <fun>
avec l'itérateur filter
#let ote_diviseurs n l = filter (function m -> n mod m = 0) l;;
ote_diviseurs : int -> int list -> int list = <fun>
7-3.
#let rec interval i j =
if i > j then failwith "interval" else
if i = j then [i] else i::(interval (i+1) j);;
interval : int -> int -> int list = <fun>
7-4.
#let rec Erec = function
| [] -> []
| n::l -> n::(Erec (ote_multiples n l));;
Erec : int list -> int list = <fun>
#let Eratosthene n =
Erec (interval 2 n);;
Eratosthene : int -> int list = <fun>
#let liste_diviseurs_premiers n =
let sqrtn = int_of_float (floor (sqrt (float_of_int n))) in
teste_diviseurs n (Eratosthene sqrtn);;
liste_diviseurs_premiers : int -> int list = <fun>
7-5.
#let rec power_m_in_n n m =
if n mod m <> 0 then 0 else 1+(power_m_in_n (n / m) m);;
power_m_in_n : int -> int -> int = <fun>
#let liste_diviseurs n =
map (function m -> (m, power_m_in_n n m)) (liste_diviseurs_premiers n);;
liste_diviseurs : int -> (int * int) list = <fun>
7-6.
#let rec power_min = function
| [], [] | [], _ | _, [] -> []
| (n1, p1)::l1, (n2, p2)::l2 ->
if n1 < n2 then power_min (l1, (n2, p2)::l2) else
if n1 > n2 then power_min ((n1, p1)::l1, l2) else
(n1, min p1 p2)::(power_min (l1, l2));;
power_min : ('a * 'b) list * ('a * 'b) list -> ('a * 'b) list = <fun>
7-7.
#let rec prod = function
| [] -> 1
| n::l -> n*(prod l);;
prod : int list -> int = <fun>
7-8.
power doit travailler sur des couples donc soit on la
réécrit avec un argument qui est un couple , soit on lui applique
l'itérateur uncurry que l'on écrit à l'exercice :
#let pgcd n1 n2 =
prod (map (uncurry power) (power_min (liste_diviseurs n1, liste_diviseurs n2)));;
pgcd : int -> int -> int = <fun>
Exercice 8 (Comment utiliser les itérateurs pour réaliser un crible
d'Ératosthène)
8-1.
#let pseudo_non_multiple n m = n= m || m mod n <> 0;;
pseudo_non_multiple : int -> int -> bool = <fun>
8-2.
#let rec pseudo_non_multiples_liste n =
if n <=1 then [] else (pseudo_non_multiple n)::(pseudo_non_multiples_liste (n-1));;
pseudo_non_multiples_liste : int -> (int -> bool) list = <fun>
8-3.
#let rec liste_n n =
if n = 2 then [2] else n::(liste_n (n-1));;
liste_n : int -> int list = <fun>
8-4.
#let sqrt_int n = int_of_float (floor (sqrt (float_of_int n)));;
sqrt_int : int -> int = <fun>
#let liste_premiers n =
list_it filter (pseudo_non_multiples_liste (sqrt_int n)) (liste_n n);;
liste_premiers : int -> int list = <fun>
Exercice 9 (Typage, ordre supérieur, fonctions anonymes)
9-1.
#let curry f x y = f (x, y);;
curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
#let uncurry f (x, y) = f x y;;
uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>
#let compose f g x = f (g x);;
compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
#uncurry compose;;
- : ('_a -> '_b) * ('_c -> '_a) -> '_c -> '_b = <fun>
#compose curry uncurry;;
- : ('_a -> '_b -> '_c) -> '_a -> '_b -> '_c = <fun>
#compose uncurry curry;;
- : ('_a * '_b -> '_c) -> '_a * '_b -> '_c = <fun>
Exercice 10 (La date du lendemain: découpage d'un problème)
#let bissextile a = (a mod 4 = 0) && ((a mod 100 <> 0) || (a mod 400 = 0));;
bissextile : int -> bool = <fun>
#let nb_jours m a =
if m = 4 || m = 6 || m = 9 || m = 11 then 30
else if m = 2 then (if bissextile a then 29 else 28) else 31;;
nb_jours : int -> int -> int = <fun>
#let date_valide (j, m, a)=
((a >= 1583 && m >= 1 && j >= 1)
|| (a = 1582 && ((m > 10 && j >=1) || (m=10 && j >= 15))))
&& m <= 12 && j <= (nb_jours m a);;
date_valide : int * int * int -> bool = <fun>
#let lendemain (jour, mois, an) =
if date_valide (jour, mois, an) then
if jour = nb_jours mois an
then if mois = 12 then (1, 1, an+1) else (1, mois+1, an)
else (jour+1, mois, an)
else failwith "lendemain : date non valide";;
lendemain : int * int * int -> int * int * int = <fun>
Quelques applications:
Fin février
#lendemain (28, 2, 1992);;
- : int * int * int = 29, 2, 1992
#lendemain (29, 2, 1996);;
- : int * int * int = 1, 3, 1996
#lendemain (28, 2, 1993);;
- : int * int * int = 1, 3, 1993
#lendemain (28, 2, 1900);;
- : int * int * int = 1, 3, 1900
#lendemain (28, 2, 2000);;
- : int * int * int = 29, 2, 2000
Fin d'une année
#lendemain (31, 12, 1990);;
- : int * int * int = 1, 1, 1991
Fin d'un mois ordinaire
#lendemain (31, 1, 1998);;
- : int * int * int = 1, 2, 1998
1583 est accepté
#lendemain (15, 2, 1583);;
- : int * int * int = 16, 2, 1583
1582 accepté après le 15 octobre, refusé avant
#lendemain (28, 2, 1582);;
Exception non rattrapée: Failure "lendemain : date non valide"
#lendemain (15, 10, 1582);;
- : int * int * int = 16, 10, 1582
#lendemain (15, 12, 1582);;
- : int * int * int = 16, 12, 1582
Mois trop long refusé
#lendemain (33, 11, 1995);;
Exception non rattrapée: Failure "lendemain : date non valide"
#lendemain (31, 11, 1990);;
Exception non rattrapée: Failure "lendemain : date non valide"
Exercice 11 (Les légumes: structures de données)
11-1. (Types)
#type quantité =
Pièce of int
| Kilo of float;;
Le type quantité est défini.
#type légume =
{ nom : string;
prix : float;
quantité : quantité;
seuil : quantité };;
Le type légume est défini.
#type rayon == légume list;;
Le type rayon est défini.
#type panier == (string * quantité) list;;
Le type panier est défini.
11-2. (Quantités)
#let vérifie_quantités q1 q2 =
match q1, q2 with
| Pièce _, Pièce _ -> true
| Kilo _, Kilo _ -> true
| _ -> false;;
vérifie_quantités : quantité -> quantité -> bool = <fun>
#let différence_entre_quantités q1 q2 =
match q1, q2 with
| Pièce p1, Pièce p2 -> Pièce (p1 - p2)
| Kilo l1, Kilo l2 -> Kilo (l1 -. l2)
| _ -> failwith "différence_entre_quantités: quantités de nature différentes";;
différence_entre_quantités : quantité -> quantité -> quantité = <fun>
#let inférieur_quantités q1 q2 =
match q1, q2 with
| Pièce p1, Pièce p2 -> p1 < p2
| Kilo l1, Kilo l2 -> l1 < l2
| _ -> failwith "inférieur_quantités: quantités de nature différentes";;
inférieur_quantités : quantité -> quantité -> bool = <fun>
11-3. (Panier)
#type panier == (string * quantité) list;;
Le type panier est défini.
11-4. (Prix)
#let rec info_légume nom rayon =
match rayon with
| [] -> failwith "Ce n'est pas la saison !"
| leg'::rayon' -> if leg'.nom=nom then leg' else info_légume nom rayon';;
info_légume : string -> légume list -> légume = <fun>
#let prix_légume nom rayon = (info_légume nom rayon).prix;;
prix_légume : string -> légume list -> float = <fun>
#let rec prix_panier panier rayon =
match panier with
| [] -> 0.0
| (nom, Pièce i) :: panier ->
(float_of_int i) *. (prix_légume nom rayon) +. prix_panier panier rayon
| (nom, Kilo l) :: panier ->
l *. (prix_légume nom rayon) +. prix_panier panier rayon;;
prix_panier : (string * quantité) list -> légume list -> float = <fun>
11-5. (Mise à jour)
#let rec mise_à_jour_légume nom quantité rayon =
match rayon with
| [] -> failwith "Ce n'est pas la saison !"
| leg::rayon' ->
if leg.nom = nom then
{ quantité = différence_entre_quantités leg.quantité quantité;
nom = leg.nom; prix = leg.prix; seuil = leg.seuil } :: rayon'
else
leg::(mise_à_jour_légume nom quantité rayon);;
mise_à_jour_légume : string -> quantité -> légume list -> légume list = <fun>
#let rec mise_à_jour_panier panier rayon =
match panier with
| [] -> []
| (nom, quantité)::panier' ->
mise_à_jour_panier panier' (mise_à_jour_légume nom quantité rayon);;
mise_à_jour_panier : (string * quantité) list -> légume list -> 'a list =
<fun>
11-6. (Commande)
#let rec légumes_à_commander rayon =
match rayon with
| [] -> []
| {nom = n; quantité = q; seuil = s} :: rayon' ->
if inférieur_quantités q s
then (n, s)::(légumes_à_commander rayon')
else légumes_à_commander rayon';;
légumes_à_commander : légume list -> (string * quantité) list = <fun>
Exercice 12 (Définir soi-même les listes)
12-1.
Les listes d'entiers
#type intlist = | Vide | Cons of int * intlist;;
Le type intlist est défini.
et les listes polymorphes
#type 'a list = | Vide | Cons of 'a * 'a list;;
Le type list est défini.
12-2.
#let rec length l = match l with
| Vide -> 0
| Cons (e, l') -> 1+(length l);;
length : 'a list -> int = <fun>
#let head l = match l with
| Vide -> failwith "head: liste vide"
| Cons (e, _) -> e;;
head : 'a list -> 'a = <fun>
#let tail l = match l with
| Vide -> failwith "tail: liste vide"
| Cons (_, l') -> l';;
tail : 'a list -> 'a list = <fun>
#let rec nth n l = match l with
| Vide -> failwith "nth: liste vide"
| Cons (e, l') -> if n = 1 then e else nth (n-1) l';;
nth : int -> 'a list -> 'a = <fun>
#let rec append l1 l2 = match l1 with
| Vide -> l2
| Cons (e, l'1) -> Cons (e, append l'1 l2);;
append : 'a list -> 'a list -> 'a list = <fun>
#let rec reverse l = match l with
| Vide -> Vide
| Cons (e, l') -> append (reverse l) (Cons (e, Vide));;
reverse : 'a list -> 'a list = <fun>
#let rec member x l = match l with
| Vide -> false
| Cons (e, l') -> x=e || member x l';;
member : 'a -> 'a list -> bool = <fun>
#let rec for_all p l = match l with
| Vide -> true
| Cons (e, l') -> (p e) && (for_all p l');;
for_all : ('a -> bool) -> 'a list -> bool = <fun>
12-3.
Pour le type prédéfini
#let rec diviser_liste l = match l with
| [] -> ([], [])
| [x] -> ([x], [])
| x1::x2::l' -> let (l1, l2) = diviser_liste l' in (x1::l1, x2::l2);;
diviser_liste : 'a builtin__list -> 'a builtin__list * 'a builtin__list =
<fun>
#let rec fusion l1 l2 = match (l1, l2) with
| ([], []) -> []
| ([], _) -> l2
| (_, []) -> l1
| (x1::l'1, x2::l'2) ->
if x1 < x2
then x1::(fusion l'1 (x2::l'2))
else x2::(fusion (x1::l'1) l'2);;
fusion : 'a builtin__list -> 'a builtin__list -> 'a builtin__list = <fun>
#let rec tri_fusion l = match l with
| [] -> []
| [x] -> [x]
| _ -> let (l1, l2) = diviser_liste l in fusion (tri_fusion l1) (tri_fusion l2);;
tri_fusion : 'a builtin__list -> 'a builtin__list = <fun>
Exercice 13 (Arbres d'expression (évaluation, simplification))
13-1.
#type formule =
| Vrai
| Faux
| Variable of int
| Non of formule
| Et of formule * formule
| Ou of formule * formule
| Implique of formule * formule
| Equivalent of formule * formule;;
Le type formule est défini.
#Variable 1;;
- : formule = Variable 1
#Non (Variable 1);;
- : formule = Non (Variable 1)
#Et (Variable 1, Non (Variable 2));;
- : formule = Et (Variable 1, Non (Variable 2))
#Non (Implique (Variable 1, Variable 2));;
- : formule = Non (Implique (Variable 1, Variable 2))
#Equivalent (Non (Variable 1), Variable 2);;
- : formule = Equivalent (Non (Variable 1), Variable 2)
#Equivalent (Implique (Variable 1, Variable 2), Non (Ou (Non (Variable 1), Non (Variable 2))));;
- : formule =
Equivalent
(Implique (Variable 1, Variable 2),
Non (Ou (Non (Variable 1), Non (Variable 2))))
13-2.
#let rec string_of_formule f = match f with
| Vrai -> "V"
| Faux -> "F"
| Variable i -> "P"^(string_of_int i)
| Non f2 -> "!"^(string_of_formule f2)
| Et (f1, f2) -> "("^(string_of_formule f1)^"/\"^(string_of_formule f2)^")"
| Ou (f1, f2) -> "("^(string_of_formule f1)^""^(string_of_formule f2)^")"
| Implique (f1, f2) ->
"("^(string_of_formule f1)^"=>"^(string_of_formule f2)^")"
| Equivalent (f1, f2) ->
"("^(string_of_formule f1)^"<=>"^(string_of_formule f2)^")";;
string_of_formule : formule -> string = <fun>
#string_of_formule (Ou (Variable 1, Variable 2));;
- : string = "(P1\/P2)"
#string_of_formule (Non (Implique (Variable 1, Variable 2)));;
- : string = "!(P1=>P2)"
#string_of_formule (Implique (Non (Variable 1),Variable 2));;
- : string = "(!P1=>P2)"
13-3.
#let rec normalize f = match f with
| Non f -> Non (normalize f)
| Et (f1, f2) -> Et (normalize f1, normalize f2)
| Ou (f1, f2) -> Ou (normalize f1, normalize f2)
| Implique (f1, f2) -> Ou (Non (normalize f1), normalize f2)
| Equivalent (f1, f2) ->
let fn1 = normalize f1 and fn2 = normalize f2 in
Ou (Et (fn1, fn2), Et(Non fn1, Non fn2))
| _ -> f;;
normalize : formule -> formule = <fun>
#normalize (Non (Implique (Variable 1, Variable 2)));;
- : formule = Non (Ou (Non (Variable 1), Variable 2))
#normalize (Implique (Non (Variable 1),Variable 2));;
- : formule = Ou (Non (Non (Variable 1)), Variable 2)
13-4.
Avec la fonction prédéfinie union
#let rec liste_variables f = match f with
| Vrai | Faux -> []
| Variable i -> [i]
| Non f2 -> liste_variables f2
| Et (f1, f2) -> union (liste_variables f1) (liste_variables f2)
| Ou (f1, f2) -> union (liste_variables f1) (liste_variables f2)
| Implique (f1, f2) -> union (liste_variables f1) (liste_variables f2)
| Equivalent (f1, f2) -> union (liste_variables f1) (liste_variables f2);;
liste_variables : formule -> int builtin__list = <fun>
#liste_variables (Ou (Et (Variable 1, Variable 2), Non (Variable 1)));;
- : int builtin__list = [2; 1]
Avec la fonction mem et un accumulateur
#let rec liste_variables_aux accu f = match f with
| Vrai | Faux -> accu
| Variable i -> if mem i accu then accu else i::accu
| Non f2 -> liste_variables_aux accu f2
| Et (f1, f2) -> liste_variables_aux (liste_variables_aux accu f1) f2
| Ou (f1, f2) -> liste_variables_aux (liste_variables_aux accu f1) f2
| Implique (f1, f2) -> liste_variables_aux (liste_variables_aux accu f1) f2
| Equivalent (f1, f2) -> liste_variables_aux (liste_variables_aux accu f1) f2;;
liste_variables_aux : int builtin__list -> formule -> int builtin__list =
<fun>
#let liste_variables f = liste_variables_aux [] f;;
liste_variables : formule -> int builtin__list = <fun>
#liste_variables (Ou (Et (Variable 1, Variable 2), Non (Variable 1)));;
- : int builtin__list = [2; 1]
13-5.
#exception Variable_non_prévue;;
L'exception Variable_non_prévue est définie.
#let rec éval la f = match f with
| Vrai -> true
| Faux -> false
| Variable i ->
(try assoc i la with Not_found -> raise Variable_non_prévue)
| Non f2 -> not (éval la f2)
| Et (f1, f2) -> (éval la f1) && (éval la f2)
| Ou (f1, f2) -> (éval la f1) || (éval la f2)
| Implique (f1, f2) -> (not (éval la f1)) || (éval la f2)
| Equivalent (f1, f2) ->
((éval la f1) && (éval la f2)) ||
((not (éval la f1)) && (not (éval la f2)));;
éval : (int * bool) builtin__list -> formule -> bool = <fun>
#éval [(1, false); (2, true)]
(Ou (Et (Variable 1, Variable 2), Non (Variable 1)));;
- : bool = true
13-6.
#let rec éval fonction f = match f with
| Vrai -> true
| Faux -> false
| Variable i -> fonction i
| Non f2 -> not (éval fonction f2)
| Et (f1, f2) -> (éval fonction f1) && (éval fonction f2)
| Ou (f1, f2) -> (éval fonction f1) || (éval fonction f2)
| Implique (f1, f2) -> (not (éval fonction f1)) || (éval fonction f2)
| Equivalent (f1, f2) ->
((éval fonction f1) && (éval fonction f2)) ||
((not (éval fonction f1)) && (not (éval fonction f2)));;
éval : (int -> bool) -> formule -> bool = <fun>
#éval (function 1 -> false | 2 -> true | _ -> failwith "cas non prévu")
(Ou (Et (Variable 1, Variable 2), Non (Variable 1)));;
- : bool = true
13-7.
#let rec substituer f i v = match f with
| Vrai | Faux -> f
| Variable j -> if i = j then v else f
| Non f2 -> Non (substituer f2 i v)
| Et (f1, f2) -> Et (substituer f1 i v, substituer f2 i v)
| Ou (f1, f2) -> Ou (substituer f1 i v, substituer f2 i v)
| Implique (f1, f2) -> Implique (substituer f1 i v, substituer f2 i v)
| Equivalent (f1, f2) -> Equivalent (substituer f1 i v, substituer f2 i v);;
substituer : formule -> int -> formule -> formule = <fun>
#substituer (Ou (Et (Variable 1, Variable 2), Non (Variable 1))) 1 Vrai;;
- : formule = Ou (Et (Vrai, Variable 2), Non Vrai)
#substituer (Ou (Et (Variable 1, Variable 2), Non (Variable 1)))
2 (Non (Variable 3));;
- : formule = Ou (Et (Variable 1, Non (Variable 3)), Non (Variable 1))
13-8.
#let rec substitue_fun fonction f = match f with
| Vrai | Faux -> f
| Variable i -> fonction i
| Non f2 -> Non (substitue_fun fonction f2)
| Et (f1, f2) -> Et (substitue_fun fonction f1, substitue_fun fonction f2)
| Ou (f1, f2) -> Ou (substitue_fun fonction f1, substitue_fun fonction f2)
| Implique (f1, f2) ->
Implique (substitue_fun fonction f1, substitue_fun fonction f2)
| Equivalent (f1, f2) ->
Equivalent (substitue_fun fonction f1, substitue_fun fonction f2);;
substitue_fun : (int -> formule) -> formule -> formule = <fun>
#substitue_fun (function i -> Variable (i+1))
(Ou (Et (Variable 1, Variable 2), Non (Variable 1)));;
- : formule = Ou (Et (Variable 2, Variable 3), Non (Variable 2))
13-9.
#exception Formule_avec_variables;;
L'exception Formule_avec_variables est définie.
#let rec éval_sans_var f = match f with
| Vrai -> true
| Faux -> false
| Variable i -> raise Formule_avec_variables
| Non f2 -> not (éval_sans_var f2)
| Et (f1, f2) -> (éval_sans_var f1) && (éval_sans_var f2)
| Ou (f1, f2) -> (éval_sans_var f1) || (éval_sans_var f2)
| Implique (f1, f2) -> (not (éval_sans_var f1)) || (éval_sans_var f2)
| Equivalent (f1, f2) ->
((éval_sans_var f1) && (éval_sans_var f2)) ||
((not (éval_sans_var f1)) && (not (éval_sans_var f2)));;
éval_sans_var : formule -> bool = <fun>
#éval_sans_var (Ou (Et (Vrai, Faux), Non Vrai));;
- : bool = false
#let rec sub f la = match la with
| [] -> f
| (i, v)::la' -> substituer (sub f la') i v;;
sub : formule -> (int * formule) builtin__list -> formule = <fun>
#let éval la f = éval_sans_var (sub f la);;
éval : (int * formule) builtin__list -> formule -> bool = <fun>
#éval [(1, Faux); (2, Vrai)]
(Ou (Et (Variable 1, Variable 2), Non (Variable 1)));;
- : bool = true
13-10.
#let rec énumération_cas_liste = function
[] -> []
| [i] -> [[(i, Vrai)]; [(i, Faux)]]
| i::l -> let lla = énumération_cas_liste l in
(map (function la -> (i,Vrai)::la) lla)@
(map (function la -> (i,Faux)::la) lla);;
énumération_cas_liste :
'a builtin__list -> ('a * formule) builtin__list builtin__list = <fun>
#
let énumération_cas f = énumération_cas_liste (liste_variables f);;
énumération_cas : formule -> (int * formule) builtin__list builtin__list =
<fun>
13-11.
#let rec tautologie_aux f = function
[] -> true
| la::l -> (éval la f)&&(tautologie_aux f l);;
tautologie_aux :
formule -> (int * formule) builtin__list builtin__list -> bool = <fun>
#
let tautologie f = tautologie_aux f (énumération_cas f);;
tautologie : formule -> bool = <fun>
13-12. (Algorithme de Shannon)
#let rec est_tautologie f l =
try éval_sans_var f with
| Formule_avec_variables ->
(match l with
| [] -> failwith "est_tautologie: la liste ne contient pas toutes les variables de la formule"
| x::l' -> est_tautologie (substituer f x Vrai) l'
&& est_tautologie (substituer f x Faux) l');;
est_tautologie : formule -> int builtin__list -> bool = <fun>
#est_tautologie (Ou (Et (Variable 1, Variable 2), Non (Variable 1))) [1;2];;
- : bool = false
#est_tautologie (Ou (Ou (Variable 1, Variable 2), Non (Variable 1))) [1;2];;
- : bool = true
This document was translated from LATEX by
HEVEA.