Filtrage, unification

Exercice 52

Définir un type expression booléenne avec Vrai, Faux, conjonction, disjonction, négation. Voici un exemple d'expression:

let e1 = Or(And(True,False),(Not False));;
e1 : expression_booleenne = Or (And (True, False), Not False)

Solution 52

type expression_booleenne =
    True
  | False
  | Or  of expression_booleenne * expression_booleenne
  | And of expression_booleenne * expression_booleenne
  | Not of expression_booleenne;;
Type expression_booleenne defined.
let e1 = Or(And(True,False),(Not False));;
e1 : expression_booleenne = Or (And (True, False), Not False)

Exercice 53

Écrire la fonction comparer qui teste si deux expressions booléennes sont identiques.

Solution 53

C'est un banal double parcours des expressions, ici programmé avec un double filtrage.

let rec comparer = fun
   True           True           -> true
 | False          False          -> true
 | (Or(e11,e12))  (Or(e21,e22))  -> comparer e11 e21 & comparer e12 e22
 | (And(e11,e12)) (And(e21,e22)) -> comparer e11 e21 & comparer e12 e22
 | (Not(e1))      (Not(e2))      -> comparer e1 e2
 | _              _              -> false;;
comparer : expression_booleenne -> expression_booleenne -> bool = <fun>
comparer e1 e1;;
- : bool = true

Exercice 54

Écrire la fonction filtrer prenant un filtre et une expression et testant si l'expression satisfait ce filtre. Les filtres seront définis à l'aide d'un type décrivant les filtrages souhaités c'est-à-dire reconnaître Vrai, Faux, n'importe quoi (l'équivalent de _) ainsi que des négations, des conjonctions ou disjonctions booléennes. Par exemple:

filtrer F_nimporte_quoi e1;;
- : bool = true
filtrer (F_Or(F_nimporte_quoi, F_Not(F_nimporte_quoi))) e1;;
- : bool = true

Solution 54

Il y a deux innnovations ici: l'introduction d'une spécification de la forme des expressions booléennes admises (le filtre, qui n'est pas une expression mais la description d'une classe d'expressions), et le filtre attrape-tout qui permet de spécifier des classes d'expressions non réduites à un seul terme.

type filtreBooleen =
   F_True
 | F_False
 | F_Or  of filtreBooleen * filtreBooleen
 | F_And of filtreBooleen * filtreBooleen
 | F_Not of filtreBooleen
 | F_nimporte_quoi;;
Type filtreBooleen defined.
let rec filtrer = fun
   F_nimporte_quoi _            -> true
 | F_True          True         -> true
 | F_False         False        -> true
 | (F_Or(f1,f2))   (Or(e1,e2))  -> filtrer f1 e1 & filtrer f2 e2
 | (F_And(f1,f2))  (And(e1,e2)) -> filtrer f1 e1 & filtrer f2 e2
 | (F_Not(f))      (Not(e))     -> filtrer f e
 | _ _                          -> false;;
filtrer : filtreBooleen -> expression_booleenne -> bool = <fun>

Exercice 55

Écrire la fonction apparaitre qui teste si une sous-expression de expression satisfait le filtre.

Solution 55

let rec apparaitre filtre expression =
  (filtrer filtre expression) or
  match expression with
     True       -> false
   | False      -> false
   | Or(e1,e2)  -> apparaitre filtre e1 or apparaitre filtre e2
   | And(e1,e2) -> apparaitre filtre e1 or apparaitre filtre e2
   | Not(e)     -> apparaitre filtre e;;
apparaitre : filtreBooleen -> expression_booleenne -> bool = <fun>
apparaitre (F_Not(F_nimporte_quoi)) e1;;
- : bool = true

Exercice 56

Écrire la fonction compter_apparitions qui retourne le nombre de sous-expressions dans expression satisfaisant le filtre.

Solution 56

C'est une simple variation de la précédente.

let compter_apparitions filtre expression =
  let rec parcourir expression =
    (if filtrer filtre expression then 1 else 0) +
    match expression with
       True       -> 0
     | False      -> 0
     | Or(e1,e2)  -> parcourir e1 + parcourir e2
     | And(e1,e2) -> parcourir e1 + parcourir e2
     | Not(e)     -> parcourir e
  in parcourir expression;;
compter_apparitions : filtreBooleen -> expression_booleenne -> int = <fun>
compter_apparitions (F_Not(F_nimporte_quoi)) (And(e1,Not(e1)));;
- : int = 3

Exercice 57

Redéfinir un nouveau type de filtre incorporant en plus la notion de variable de filtrage.

Solution 57

type filtreBooleen =
   F_True
 | F_False
 | F_Parametre of string
 | F_Or  of filtreBooleen * filtreBooleen
 | F_And of filtreBooleen * filtreBooleen
 | F_Not of filtreBooleen
 | F_nimporte_quoi;;
Type filtreBooleen defined.

Exercice 58

Écrire une nouvelle fonction filtrer prenant un filtre et une expression booléenne et retournant un couple (booléen, environnement). Le booléen indique si le filtrage a réussi tandis que l'environnement associe des variables de filtres aux valeurs qu'elles ont prises. Lorsqu'une variable de filtrage a déjà une valeur, elle n'admet que des expressions égales à cette valeur. Par exemple,

filtrer (F_Or(F_Parametre "x", F_Parametre "y")) e1 [];;
- : bool * (string * expression_booleenne) list =
 true, ["y", Not False; "x", And (True, False)]
filtrer (F_Or(F_Parametre "x", F_Parametre "x")) e1 [];;
- : bool * (string * expression_booleenne) list = false, []

Solution 58

L'innovation ici est de propager correctement l'environnement de filtrage lors du filtrage des sous-termes. Pour ne pas manipuler un filtrage à trois termes on introduit un filtrage explicite sur des paires.

let rec filtrer filtre expression environnement = 
 match (filtre, expression) with
   (F_nimporte_quoi, _) -> (true, environnement)
 | (F_True, True) -> (true, environnement)
 | (F_False, False) -> (true, environnement)
 | (F_Parametre (n), expression) -> 
    let (deja_vue, valeur) = 
         let rec chercher = function
             [] -> (false, expression)
           | (nom, valeur) :: env -> if nom = n then (true,valeur)
                                     else chercher env in
         chercher environnement in
     if deja_vue then if comparer valeur expression
                      then (true, environnement)
                      else (false, [])
     else (true, (n, expression) :: environnement)
 | (F_And(f1,f2), And(e1,e2)) -> 
   let (booleen, nouvel_environnement) = (filtrer f1 e1 environnement) in
    if booleen then (filtrer f2 e2 nouvel_environnement)
    else (false, [])
 | (F_Or(f1,f2), Or(e1,e2)) -> 
   let (booleen, nouvel_environnement) = (filtrer f1 e1 environnement) in
    if booleen then filtrer f2 e2 nouvel_environnement
    else (false, [])
 | (F_Not(f), Not(e)) -> filtrer f e environnement
 | _                  -> (false, []);;
filtrer :
 filtreBooleen ->
 expression_booleenne ->
 (string * expression_booleenne) list ->
 bool * (string * expression_booleenne) list = <fun>

Exercice 59

On admet maintenant la présence de variables au sein des expressions booléennes, définir ce nouveau type et écrire une fonction substituer prenant un nom de variable, une valeur qui est une expression booléenne et une expression et qui retourne une nouvelle expression d'où toutes les occurrences de (Variable nom) ont été remplacées par valeur. Par exemple,

substituer "x" (And(Variable "y", Not False))
           (Or (Not (Variable "x"), And(Variable "x", Variable "y")));;
- : expression_booleenne =
 Or
  (Not (And (Variable "y", Not False)),
   And (And (Variable "y", Not False), Variable "y"))

Solution 59

type expression_booleenne =
    True
  | False
  | Variable of string 
  | Or  of expression_booleenne * expression_booleenne
  | And of expression_booleenne * expression_booleenne
  | Not of expression_booleenne;;
Type expression_booleenne defined.
let rec substituer nom valeur = function
   True as expression -> expression
 | False as expression -> expression
 | Variable autre_nom as expression ->
    if nom = autre_nom then valeur else expression
 | Or(e1,e2) -> Or((substituer nom valeur e1), (substituer nom valeur e2))
 | And(e1,e2) -> And((substituer nom valeur e1), (substituer nom valeur e2))
 | Not(e) -> Not (substituer nom valeur e);;
substituer :
 string ->
 expression_booleenne -> expression_booleenne -> expression_booleenne = <fun>

Exercice 60

Ecrire une fonction unifier testant si deux expressions, comprenant des variables, s'unifient. Par exemple,

unifier True True [];;
- : bool = true
unifier (Or (And (Variable "x", Variable "y"), True))
        (Or (And (False, True), Variable "z"))
        [];;
- : bool = true

Solution 60

let rec unifier expression1 expression2 environnement = 
 match (expression1, expression2) with
   (True, True) -> exploiter environnement
 | (False, False) -> exploiter environnement
 | (Or(e11,e12), Or(e21,e22)) -> 
     unifier e11 e21 ((e12,e22) :: environnement)
 | (And(e11,e12), And(e21,e22)) ->
     unifier e11 e21 ((e12,e22) :: environnement)
 | (Not(e1), Not(e2)) ->
     unifier e1 e2 environnement
 | (Variable n1, e2) ->
     exploiter (map (function (ea, eb) -> 
                      ((substituer n1 e2 ea), (substituer n1 e2 eb)))
                    environnement )
 | (e1, Variable n2) ->
     exploiter (map (function (ea, eb) -> 
                      ((substituer n2 e1 ea), (substituer n2 e1 eb)))
                    environnement )
 | _  -> false
and exploiter = function
   [] -> true
 | (ea,eb) :: environnement -> unifier ea eb environnement;;
unifier :
 expression_booleenne ->
 expression_booleenne ->
 (expression_booleenne * expression_booleenne) list -> bool = <fun>
exploiter : (expression_booleenne * expression_booleenne) list -> bool =
 <fun>