Discussion :

[Happpy]

Bonjour tout le monde, je travaille sur un testeur de formules logiques simples.
Il faut le faire de façon récursive.

Mon professeur nous a indiqué que si on a n variables propositionnelles, on fixe la première à 0 ou 1 et on réitère le processus avec les n-1 restantes.
On a :

{0, 1}^n = ({0} x {0, 1}^(n-1)) U ({1} x {0, 1}^(n-1)) qui j'admets

Mais je ne vois pas comment gérer cette expression au niveau récursif...
Quelques explications ne seraient pas de refus.

Merci d'avance.

[Happpy]

S'il vous plaît personne n'a une idée ?
J'ai travaillé sur le code suivant mais il n'est pas au point :

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
18
19
20
 
let rec completerListe liste taille =
    match liste with
        |liste when list_length liste >= taille -> liste
        |_ -> completerListe (0::liste) taille;;
 
let genererCombLog taille =
    let rec generer listeActuelle t combLog =
        match t with
            |t when t <= 0 -> combLog
            |_ ->
                    begin
                        let l0 = 0::listeActuelle in
                        let l1 = 1::listeActuelle in
                        generer l0 (t - 1) ((completerListe l0 t)::combLog);
                        generer l1 (t - 1) ((completerListe l1 t)::combLog);
                    end;
    in generer [] taille [];;
 
genererCombLog 3;;

...?

[gorgonite]

Bonjour tout le monde, je travaille sur un testeur de formules logiques simples.

Mon professeur nous a indiqué que si on a n variables propositionnelles, on fixe la première à 0 ou 1 et on réitère le processus avec les n-1 restantes.

question bête : qu'entend-il par tester ?

• évaluer avec une distribution de valeurs en entrée
• trouver si elle peut être satisfaite
• trouver une voire toutes les combinaisons la satisfaisant

[Happpy]

Re bonjour, je me suis mal exprimé effectivement.

En faite pour l'instant je veux avoir une fonction, ayant pour paramètre une "taille de liste" qui représente en fait le nombre de variables propositionnelles dans une formule logique.
Cette fonction sera récursive et renverra toutes les combinaisons possibles sous forme de liste (donc renverra une liste de listes...), contenant donc des 0 ou des 1.

Je travaille sur cette fonction pour ensuite obtenir toutes les combinaisons qui satisfont une formule logique (faire en sorte qu'elle soit vraie).



Je veux juste faire ça pour l'instant.

J'ai réussi à le faire de façon impérative en faisant l'analogie avec l'unicité d'un nombre en écriture binaire. Mais là je veux le faire en récursif pour m'entraîner et ne pas rouiller pendant les vacances.

[gorgonite]

Code :

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

1
2
3
4
let l0 = 0::listeActuelle in
                        let l1 = 1::listeActuelle in
                        generer l0 (t - 1) ((completerListe l0 t)::combLog);
                        generer l1 (t - 1) ((completerListe l1 t)::combLog);

indice:
ta fonction renvoie en théorie une liste...
que fais-tu du résultat de la partie rouge ?

au passage vu la complexité de tes match/with, pourquoi ne pas faire des if then else ?

[prgasp77]

Je parie que generer est une fonction qui retourne un unit et qui a des effets de bord. Ça sent la variable globale .

[Happpy]

Re bonjour alors voila mon code modifié.

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
18
19
20
21
22
 
let rec completerListe liste taille =
    match liste with
        |liste when list_length liste >= taille -> liste
        |_ -> completerListe (0::liste) taille;;
 
let genererCombLog taille =
	let combLog = ref [] in
   let rec generer listeActuelle t =
   	if t <= 0 then !combLog
      else
      	begin
         	let l0 = 0::listeActuelle in
            let l1 = 1::listeActuelle in
            combLog := (completerListe l0 t)::(!combLog);
            combLog := (completerListe l1 t)::(!combLog);
            generer l0 (t - 1);
            generer l1 (t - 1);
         end;
    in generer [] taille;;
 
genererCombLog 4;;

C'est un peu mieux déjà au niveau des résultats.
Par contre pour des tests, (genererCombLog 2, 3,...) il y a des doublons et pire, des listes qui ne font pas la bonne taille...

[gorgonite]

au passage vu la complexité de tes match/with, pourquoi ne pas faire des if then else ?

au risque de me répéter

exemple

Code :

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

1
2
3
let rec completerListe liste taille =
  if List.length liste >= taille then liste else completerListe (0::liste) taille;;
val completerListe : int list -> int -> int list = <fun>

attention OCaml pas Caml Light

C'est un peu mieux déjà au niveau des résultats.

• l'exercice est de comprendre comment procéder en fonctionnel. c'est tentant de se raccrocher à ce que l'on sait, mais c'est dangereux pour la suite
• référence de liste en programmation fonctionnelle... à la rigueur quand tu ne seras plus débutant, tu auras le droit à des champs mutable
• je ne vois pas clair, ou alors les branches then et else ne renvoient pas le même type

[Happpy]

J'ai pensé à passer par la référence ce qui n'est pas correcte effectivement pour du fonctionnel.
Le problème est le double appel de la fonction generer par rapport au retour, etc... ça me gène...

[gorgonite]

J'ai pensé à passer par la référence ce qui n'est pas correcte effectivement pour du fonctionnel.
Le problème est le double appel de la fonction generer par rapport au retour, etc... ça me gène...

as-tu pensé à ceci ?

Code :

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

1
2
3
4
5
6
7
8
9
10
let ma_fonction_generatrice a = 
  let rec sous_fonction a liste =
     if ... then liste
     else 
         let a0 = ... and a1 = ... in
         let l0 = ... and l1 = ... in
         let tmp0 = sous_fonction a0 l0 and tmp1 = sous_fonction a1 l1 in
         tmp0 @ tmp1
  in
  sous_fonction a [] ;;

[Happpy]

Re bonjour, je m'excuse pour cette réponse très tardive mais bon, c'était compliqué, problèmes à côté de tout ça....

Voila mon code :

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 completerListe liste taille =
	if list_length liste >= taille then liste else completerListe (0::liste) taille;;
 
let genererCombLog taille =
	let rec generer listeActuelle t =
		if t <= 0 then listeActuelle
		else
			let newT = (t - 1) in
			let l0 = 0::listeActuelle and l1 = 1::listeActuelle in
			let lF0 = (completerListe (generer l0 newT) taille) and lF1 = (completerListe (generer l1 newT) taille) in
			lF0 @ lF1;
	in generer [] taille;;

Après test, j'ai de bons résultats, après je ne sais pas si c'est ce code que tu attendais, gorgonite d'après le modèle que tu m'as donné...
La seule chose est qu'on n'a pas une liste de listes mais juste une liste...

[gorgonite]

et si tu remplaçais ceci :

Code :

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

1
2
3
let l0 = 0::listeActuelle
[...]
generer [] taille

par cela :

Code :

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

1
2
3
let l0 = map (fun l -> 0::l) listeActuelle
[...]
generer [ [] ] taille

par ailleurs, completerListe n'est pas utile...


Pour infos, c'est bien cela que tu souhaites obtenir ?

Code :

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

1
2
3
4
5
6
7
8
9
val genererCombLog : int -> int list list = <fun>
# genererCombLog 0;;
- : int list list = [[]]
# genererCombLog 1;;
- : int list list = [[0]; [1]]
# genererCombLog 2;;
- : int list list = [[0; 0]; [1; 0]; [0; 1]; [1; 1]]
# genererCombLog 3;;
- : int list list = [[0; 0; 0]; [1; 0; 0]; [0; 1; 0]; [1; 1; 0]; [0; 0; 1]; [1; 0; 1]; [0; 1; 1]; [1; 1; 1]]

[Happpy]

Re bonjour, oui c'est exactement ça que je cherchais !

J'ai des questions, quel est la différence entre l'utilisation de map lors de l'ajout du 0 ou du 1 à la liste ? Après quelques tests j'ai cru comprendre qu'en utilisant map on avait vraiment le polymorphisme avec une a' list list alors que sans map on avait une int list list et ça renvoyait une erreur dans le generer [ [] ] taille...

Dans "generer [ [] ] taille", le [ [] ] sert juste à indiquer qu'on voudra une liste de listes en faite ?

Pourquoi compléter liste devient inutile ?

[gorgonite]

J'ai des questions, quel est la différence entre l'utilisation de map lors de l'ajout du 0 ou du 1 à la liste ?
Après quelques tests j'ai cru comprendre qu'en utilisant map on avait vraiment le polymorphisme avec une a' list list alors que sans map on avait une int list list et ça renvoyait une erreur dans le generer [ [] ] taille...

map renvoyer une nouvelle liste dont les éléments sont le résultat de l'application de la fonction passée en premier argument aux éléments de la liste passée en second argument

principe de la récursivité : on donne le résultat pour un cas de base et ensuite on suppose qu'on a le résultat pour un cas de taille n (ou pour p cas de taille <= n) et on construit le résultat pour les cas de taille n+1 à partir de ces résultats ( l(es) appel(s) récursif(s) )

Dans "generer [ [] ] taille", le [ [] ] sert juste à indiquer qu'on voudra une liste de listes en faite ?

Pourquoi compléter liste devient inutile ?

Non... 'a list list est un cas particulier de 'a list, ce n'était pas le but

[ [] ] te donne la graine qui servira à initier ta récursion...

[Happpy]

Ah d'accord, mais dans ce cas, pourquoi avoir utilisé map alors qu'en ajoutant simplement le 0 ou le 1 à la liste on gagnait en nombre de caractères tapés ?

[gorgonite]

Ah d'accord, mais dans ce cas, pourquoi avoir utilisé map alors qu'en ajoutant simplement le 0 ou le 1 à la liste on gagnait en nombre de caractères tapés ?

Code :

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

1
2
1::[ [] ] => error
map (fun l -> 1::l) [ [] ] => [ [1] ]

[Happpy]

Ah d'accord !
Merci beaucoup pour ces informations !

Bonne continuation et merci encore !

Sujet résolu !

[gorgonite]

Sujet résolu !

penses à mettre le code final pour les futurs lecteurs...

et

[Happpy]

Voila le code final :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
let genererCombLog taille =
	let rec generer listeActuelle t = 
		if t <= 0 then listeActuelle
		else
			let newT = (t - 1) in
			let l0 = map (fun l -> false::l) listeActuelle and l1 = map (fun l -> true::l) listeActuelle in
			let lF0 = generer l0 newT and lF1 = generer l1 newT in
			lF0 @ lF1;
	in generer [ [] ] taille;;

[gorgonite]

pas mal, j'avais prévu cela :

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
let genererCombLog taille =
   let rec generer listeActuelle t =
      if t <= 0 then listeActuelle
      else
         let newT = (t - 1) in
         let l0 = List.map (fun l -> 0::l) listeActuelle and 
         l1 = List.map (fun l -> 1::l) listeActuelle in
         (generer l0 newT) @ (generer l1 newT)
   in
   if taille <= 0 then [ ] else (generer [ [] ] taille)
;;
 
genererCombLog 0;;
genererCombLog 1;;
genererCombLog 2;;
genererCombLog 3;;