Bonjour,
Je suis débutant en Caml / Ocaml et je suis actuellement le cours suivant : https://www.lri.fr/~paulin/LGL/docs/polycaml-etuds.pdf
Je suis à l'exercice 50, je n'ai pas l'impression d'avoir eu de problème mais je souhaite avoir quelques avis dont la façon dont j'ai codé. J'essaie de m'approprier la vision du fonctionnel, si vous avez du temps pour me lire (c'est un peu long), et des conseils à me donner, c'est avec plaisir.
Sans attendre voici les questions et les réponses :
1. Décrire un type boolexpr pour représenter des expressions booléennes construites sur les constantes True et False, les opérateurs And, Or et Not, et les variables booléennes.
2. Écrire une fonction qui évalue une expression dans un environnement de valeurs booléennes, c’est-
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 type op_unaire = Not;; type op_binaire = And | Or;; type boolexpr = | Boolean of bool | Var of string | Op_unaire of op_unaire * boolexpr | Op_binaire of op_binaire * boolexpr * boolexpr;;
à-dire une liste de couples (nom de variable, booléen). Utiliser la fonction List.assoc.
3.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14 let rec evalue_bool env expr = match expr with | Boolean(bool1) -> bool1 | Var(chaine) -> (try (List.assoc chaine env) with Not_found -> raise (Variable_non_definie chaine)) | Op_unaire(op1, expr_bool) -> (match op1 with | Not -> not (evalue_bool env expr_bool)) | Op_binaire(op1, expr_bool1, expr_bool2) -> (match op1 with | Or -> (evalue_bool env expr_bool1) || (evalue_bool env expr_bool2) | And -> (evalue_bool env expr_bool1) && (evalue_bool env expr_bool2));;
Donner une fonction qui prend un boolexpr et qui retourne la liste de toutes ses variables. Une
variable qui se trouve plusieurs fois dans l’expression doit apparaître une seule fois dans la liste.
La plupart de mes problèmes ont été sur cette question, d'abord, la complexité est bien sûr pas optimiser (table hachage / arbre binaire de recherche serait mieux que l2) mais n'y a-t-il pas même possibilité de faire cela de manière plus élégante, sans même passé par l2 (sans avoir une complexité trop mauvaise).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 let rec retourne_liste_variable_int = function | Boolean(bool1) -> [] | Var(chaine) -> [chaine] | Op_unaire(_, expr_bool) -> (retourne_liste_variable expr_bool) | Op_binaire(_, expr_bool1, expr_bool2) -> (retourne_liste_variable expr_bool1)@(retourne_liste_variable expr_bool2);; let rec supp_doublon l1 l2 = match l1 with | [] -> l2 | h::t -> if (List.mem h l2) then (supp_doublon t l2) else (supp_doublon t (h::l2));; let retourne_liste_variable expr_bool = supp_doublon (retourne_liste_variable_int expr_bool) [];;
4. Écrire une fonction qui retourne, pour une liste de variables, la liste de tous les environnements
avec valeurs booléennes pour ces variables.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 let rec liste_env l = let ajoute_liste_var var l = (match l with | [] -> [[(var, true)]; [(var, false)]] | t::[] -> [(var, true)::t ; (var, false)::t] | h::t -> ((var, true)::h)::(((var, false)::h)::(ajoute_liste_var var t))) in match l with | [] -> [] | t::[] -> ajoute_liste_var t [] | h::t -> ajoute_liste_var h (liste_env t);;
5. Écrire une fonction pour_tous de type ’a list -> (’a -> bool) -> bool tel que
(pour_tous l f) retourne true si et seulement si f x retourne true pour tous les éléments
x de la liste l.
6. Écrire une fonction qui prend une expression du type boolexpr et qui retourne true si cette
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 let rec pour_tous l f = match l with | [] -> true | h::t -> if (f h) then (pour_tous t f) else false;;
expression est une tautologie, c’est-à-dire si l’évaluation de cette expression retourne true pour
tous les environnements.
7. (J'ai pas trouvé comment insérer du LaTeX, désolé).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 let est_totologie expr = let fonction_evaluation env = evalue_bool env expr in pour_tous (liste_env (retourne_liste_variable expr)) fonction_evaluation;;
En utilisant le fait que
not(and(x,y)) = or(not(x), not(y))
not(or(x,y)) = and(not(x), not(y))
not(not(x)) = x
écrire une fonction qui prend une expression du type boolexpr et retourne une expression du type boolexpr équivalente où il n’y a plus de Not sauf si appliqué directement à une variable.
Par exemple, la fonction appliqué à l’expression not(and(x, or(y, z))
doit retourner or(not(x), and(not(y), not(z))).
Là encore, je trouve mon code assez long, y avait-il possibilité de faire beaucoup plus simple (à part supposé que le seul opérateur unaire est le not ici) ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 let rec transf_boolexpr = function | Boolean(bool1) -> Boolean(bool1) | Var(x) -> Var(x) | Op_unaire(op1, expr1) -> (match op1 with | Not -> (match expr1 with | Op_unaire(Not, expr2) -> expr2 | Op_binaire(And, expr2, expr3) -> Op_binaire(Or, transf_boolexpr (Op_unaire(Not, expr2)), transf_boolexpr (Op_unaire(Not, expr3))) | Op_binaire(Or, expr2, expr3) -> Op_binaire(And, transf_boolexpr (Op_unaire(Not, expr2)), transf_boolexpr (Op_unaire(Not, expr3))) | _ -> Op_unaire(Not, expr1)) | _ -> Op_unaire(op1, transf_boolexpr expr1)) | Op_binaire(op1, expr1, expr2) -> Op_binaire(op1, transf_boolexpr expr1, transf_boolexpr expr2);;
Merci d'avance.
Partager