Discussion :

[christina03]

Bonjour,

j'ai le type formule suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
type formula=
|Var of string
|Neg of formula
|And of formula*formula
|Or of formula*formula;;

et j'essaye d'écrire une fonction qui prend une formule en argument, et renvoie sa forme normale comme résultat.

La forme normale d'une formule de la forme Neg (Neg x) est x
et de Neg (And (x,y)) est Or (Neg x, Neg y)
et de Neg (Or (x,y)) est And (Neg x, Neg y)

j'ai écrit la fonction suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
let forme_normale=function
|Var "x"->Var "x" (*pour ne plus réduire ce cas*)
|Neg (Neg x)->x
|Neg (And (x,y))->Or (Neg x, Neg y)
|Neg (Or (x,y))->And (Neg x, Neg y)
;;

ceci me renvoie un warning que le pattern matching n'est pas exhaustif
mais la fonction est acceptée
et un test me renvoit la formule suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
# forme_normale (Neg(And(Neg(Var "x"), Or(Var "y", Neg (Var "z")))));;
- : formula = Or (Neg (Neg (Var "x")), Neg (Or (Var "y", Neg (Var "z"))))

comment faire pour que Neg (Neg (Var "x")) se réduise à Var "x" ?
j'ai essayé de rendre la fonction récursive, et d'appeler la fonction à nouveau dans le cas où le résultat est une formule
comme :
Neg (Neg x)-> forme_normale x

mais cela n'a pas marché

est-ce que qqn peut m'aider à le faire

merci

[gorgonite]

tu as utilisé let rec pour définir ta fonction récursive ?

nb: il est important de faire un pattern-matching exhaustif
au pire, ajoutes un cas qui matche tout sans rien modifier et affichant un warning pour signaler cet abus

[prgasp77]

Salut,
ta fonction d'évaluation se doit d'être introspective :

Code caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
# let rec eval = function
  | Neg (Neg x)     -> eval x
  | And (x,y)       -> And (eval x, eval y)
  | Or  (x,y)       -> Or  (eval x, eval y)
  | Neg (And (x,y)) -> eval (Or ((eval (Neg x)), (eval (Neg y))))
  | Neg (Or  (x,y)) -> eval (And ((eval (Neg x)), (eval (Neg y))))
  | Neg x           -> Neg (eval x)
  | Var x           -> Var x
  ;;
val eval : formula -> formula = <fun>

# eval (Neg (And (Neg (Var "x"), Or (Var "y", Neg (Var "z"))))) ;;
- : formula = Or (Var "x", And (Neg (Var "y"), Var "z"))

Edit : y'a des eval de trop ... mais bon c'est pour l'exemple

[gasche]

"introspective", qu'est-ce que ça veut dire ?

prgasp77> Avoir des eval en trop n'est pas du tout bon pour l'exemple. Ça rend le code beaucoup plus compliqué et ça soulève des questions de terminaison. Il se trouve que ton code termine, mais ce n'est pas évident, et en tout cas ses performances seront complètement lamentables. Avec de petites variations, un code ressemblant pourra boucler à l'infini. Bref montrer ça n'est *pas* un service à rendre à un débutant (ou alors dans le style anti-example).

[gasche]

La façon la plus jolie à mon goût d'implémenter une forme normale négative (on ne parle pas d'une forme normale disjonctive ou quoi ici, on est d'accord?) est de considérer qu'on manipule des formules dans un "contexte", soit positif, soit négatif (quand on est sous une négation), et que le contexte négatif échange les quantificateurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
let forme_normale_neg formula =
  let rec positif = function
    | Var x -> Var x
    | Neg a -> negatif a
    | And (a, b) -> And (positif a, positif b)
    | Or (a, b) -> Or (positif a, positif b)
  and negatif = function
    | Var x -> Neg (Var x)
    | Neg a -> positif a
    | And (a, b) -> Or (negatif a, negatif b)
    | Or (a, b) -> And (negatif a, negatif b)
  in positif formula

On peut faire plus compact avec une représentation mieux factorisée des formules (réunir And et Or en un même cas pour les traiter de façon homogène).

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
16
17
type formula=
| Var of string
| Neg of formula
| BinOp of formula * op * formula
and op = And | Or
 
let forme_normale_neg formula =
  let rec contexte signe = function
    | Var x -> if signe then Var x else Neg (Var x)
    | Neg a -> contexte (not signe) a
    | BinOp (a, op, b) ->
      let op' =
        if signe then op else match op with
          | And -> Or
          | Or -> And in
      BinOp (contexte signe a, op', contexte signe b)
  in contexte true formula

PS: je suis conscient que fournir du code qui marche ne répond pas à la question initiale de christina03. Mon soucis c'est qu'il est difficile d'y répondre sans en savoir plus. Ça pourrait être un simple oubli de "rec", une incompréhension de la sémantique du filtrage (en pensant que quand on ne précise rien il "se propage tout seul"), ou carrément une erreur de compréhension plus large où le filtrage est considéré comme un système de réécriture modifiant aussi les termes en profondeur. Difficile d'en dire plus (et donc de répondre façon adaptée) sans avoir plus d'informations.

[prgasp77]

"introspective", qu'est-ce que ça veut dire ?

C'est un terme de psychologie que j'ai trouvée adapté ici, peut être à tord . Il s'agit de s'auto-analyser, de s'évaluer en soi-même ... tout ça ...

Avoir des eval en trop n'est pas du tout bon pour l'exemple [...]

Je ne sais pas qui de nous deux fait le plus grand mal, moi qui donne un code bancal ou toi qui fournit la réponse telle quelle à l'exercice. Pour me défendre, je dirais que mon morceau de code n'était donné qu'à titre d'exemple, pour montrer « l'introspection » nécessaire (puisque vous voila maintenant familier avec ce mot).

La façon la plus jolie à mon goût d'implémenter une forme normale négative (on ne parle pas d'une forme normale disjonctive ou quoi ici, on est d'accord?) est de considérer qu'on manipule des formules dans un "contexte", soit positif, soit négatif (quand on est sous une négation), et que le contexte négatif échange les quantificateurs.

Je confirme, c'est une belle solution que tu fournis là.

[ceciestunpseudo]

[...]
Je ne sais pas qui de nous deux fait le plus grand mal, moi qui donne un code bancal ou toi qui fournit la réponse telle quelle à l'exercice.[...]

Je dirais le code bancal. Dans le cas d'un bon code, le pire est qu'il ne serve à rien mais n'entraîne pas de mauvaises habitudes (excepté la procrastination). Dans le cas d'une mauvaise manière de faire par contre, le pire est qu'il soit pris pour une bonne approche. Et là, c'est dramatique.

[prgasp77]

Dans le cas d'une mauvaise manière de faire par contre, le pire est qu'il soit pris pour une bonne approche. Et là, c'est dramatique.

Je trouve que tu exagères ... ce que j'ai fourni n'ai aucunement une mauvaise manière, j'ai juste par manque d'intérêt omis d'optimiser le code une fois le résultat attendu obtenu. De plus, je l'ai précisé.

[ceciestunpseudo]

Je trouve que tu exagères ... ce que j'ai fourni n'ai aucunement une mauvaise manière, j'ai juste par manque d'intérêt omis d'optimiser le code une fois le résultat attendu obtenu. De plus, je l'ai précisé.

Je t'accorde que cela peut se discuter. Mais pour les mêmes raisons que Gasche, je pense que ce que tu fournis est un mauvais exemple.

[SpiceGuid]

Une chose qui fait aussi du mal (au forum) c'est quand le titre n'a rien à voir avec le problème rencontré.
Dans le titre n'utilisez pas de terme technique que vous ne comprenez pas à 100%.
Dites juste Réécriture d'une formule booléenne, parce que vous êtes certain(e) que c'est bien là le sujet. Les types paramétrés ça existe probablement mais vous ne savez pas si c'est bien là que réside votre incompréhension. Si vous n'en êtes sûr(e) qu'à 60% alors il y a environ 80% de chances que ça n'ait rien à voir.

En résumé :

• si vous êtes débutant utilisez du vocabulaire simple (de débutant)
• si vous êtes expert, au contraire, utilisez le terme technique que vous savez être approprié à votre question