Discussion :

[Fellowes]

Bonjour à tous!

Voilà, je débute en Caml et j´essaye de régler un petit problème.

Je dois créer un ensemble de sous ensemble d’une liste donnée!

J’ai une liste qui contient [1,2,3] par exemple et je dois réussir à avoir une liste qui donne [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] (pas de doublons dans les listes)

Je précise que je n’ai pas droit au fonction des librairies Caml, ni aux boucles sinon ça serait trop simple ^^ (j’utilise presque que de la récursivité du coup)

J’ai déjà fait une fonction union qui créer l’union de deux listes et qui gère les doublons si ça peut aider..

Merci pour tous vos futurs conseils, si vous avez des idées, pour le code, ou pour m’aider à démarrer parce que ça fait un bon moment que je bug dessus!

[TchoubiTchoub]

Bonjour,

Ce serait déjà bien de mettre ce que vous avez fait pour le moment et de mettre une fonction, même incomplète, pour voir où vous bloquez.

[Fellowes]

Pas de probleme


Voila toutes les fonctions que j'ai faites. Je sais que je peux faire plus simple pour certaines en utilisant les fonctions précédentes mais je voulais m'entraîner:

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
 
(* a *)
 
let rec appartient e l=match l with
  |[] -> false;
  |a::f -> if a=e then true else appartient e f ;;
 
 
(* b *)
 
(* construit liste sans doublons *)
let rec consEns l  = match l with
  |[]-> []
  |a::f -> if appartient a f then consEns f else a :: consEns f ;;
 
(* c *)
 
let union l1 l2 = consEns(l1@l2);;
 
(* d *)
 
let rec inter l1 l2=match l1 with
  |[]-> []
  |a::f -> if appartient a l2  then a :: inter f l2 else inter f l2;;
 
 
 
 
 
(* e *)
 
let rec inclus l1 l2= match l1 with
  |[] -> true;
  |a::f -> if appartient a l2 then inclus f l2 else false;;
 
 
 
(* f *)
 
(* fonction qui enleve un element de la liste si il y est *)
 
let rec remove_element e l = match l with
  |[]->[]
  |a::f -> if a=e then f else a::remove_element e f;;
 
 
(* les listes avec les mêmes éléments, sont égals, même si ces éléments ne sont pas 
dans le même ordre *)
let rec  egalite l1 l2 =  match l1,l2 with
  |_::_,[]->false
  |[],_::_->false
  |[],[]->true
  |a::f,b::g-> if appartient a l2 && a=b then egalite f g
               else if appartient a l2 && a!=b
               then  egalite f (remove_element a l2)
               else false;;
 
 
(* g *)
 
 
(* un element x tous les elements d'une liste *)
let rec sousProd e l= match l with
  |[]->[]
  |a::f-> (e,a)::sousProd e f;;
 
let rec prodCart l1 l2= match l1 with
  |[]->[]
  |a::f-> union (sousProd a l2) (prodCart f l2);;

Et donc j'ai commencé ma fonction mais je vais pas bien loin...

Code :

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

1
2
3
4
5
 
 
let  rec sousEnsemble1 l= match l with
          |[]-> []
          |a::f -> [a]::sousEnsemble1 f;;

J'ai une autre question: C'est quoi la difference entre let f= function et let f= match f with??
Merci bcp pour votre aide.

[TchoubiTchoub]

Bien, regardons ça étape par étape, alors (ça vous aidera pour plus tard) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(* a *)
 
let rec appartient e l=match l with
  |[] -> false;
  |a::f -> if a=e then true else appartient e f ;;
 
(* a alternatif *)
 
let rec appartient e = function
  | [] -> false;
  | a::f -> a = e || appartient e f ;;

Car "if b then true else e" c'est la même chose que b || e (et les opérateurs logiques étant paresseux en OCaml, si b est faux il évalue e sans garder en mémoire la valeur de b, récursivité terminale)

Code :

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

1
2
3
4
5
6
(* b *)
 
(* construit liste sans doublons *)
let rec consEns l  = match l with
  |[]-> []
  |a::f -> if appartient a f then consEns f else a :: consEns f ;;

(* b alternatif *)

(* construit liste sans doublons *)
let rec consEns = function
|[]-> []
|a::f -> if appartient a f then consEns f else a :: consEns f ;;[/CODE]

Je mets celle-ci uniquement pour répondre à votre dernière question. Il n'y a aucune différence entre "let f l = match l with" et "let f = function" si ce n'est que "l" n'est pas nommé dans le second cas et ne peut donc pas être utilisé tel quel.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(* e *)
 
let rec inclus l1 l2= match l1 with
  |[] -> true;
  |a::f -> if appartient a l2 then inclus f l2 else false;;
 
(* e alternatif *) 
 
(* e *)
 
let rec inclus l1 l2= match l1 with
  | [] -> true;
  | a::f -> appartient a l2 && inclus f l2;;

Pour la même raison que précédemment, "if b then e else false" est équivalent à "b && e".

De plus, j'ai un problème avec cette fonction parce qu'on ne supprime pas l'élément dans la liste 2 donc "inclus [1; 1; 1] [1]" renverra "true" (après si les listes n'ont pas de doublons, c'est correct ;-))

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
(* f *)
 
let rec remove_element e l = match l with
  | [] -> []
  | a::f -> if a=e then f else a::remove_element e f;;
 
(* f alternatif *)
 
let rec remove_element e l = match l with
  | [] -> []
  | a :: f when a = e -> f
  | a :: f -> a::remove_element e f;;
 
(* f récursif terminal *)
let remove_element e l =
  let rec aux acc = function
    | [] -> List.rev acc
    | a :: f when a = e -> aux acc f
    | a :: f -> aux (a :: acc) f 
  in aux [] l;;

C'est un exercice intéressant (et permettant d'avoir un code optimisé) que de rendre le plus de fonctions possibles récursives terminales.

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
(* les listes avec les mêmes éléments, sont égals, même si ces éléments ne sont pas 
   dans le même ordre *)
let rec  egalite l1 l2 =  match l1,l2 with
  |_::_,[]->false
  |[],_::_->false
  |[],[]->true
  |a::f,b::g-> if appartient a l2 && a=b then egalite f g
    else if appartient a l2 && a!=b
    then  egalite f (remove_element a l2)
    else false;;
 
let rec egalite l1 l2 = match l1, l2 with
  | [], [] -> true
  | a :: f, b :: g when a = b -> egalite f g
  | a :: f, b :: g when appartient a g && appartient b f -> 
    egalite (remove_element b f) (remove_element a g)
  | _ -> false

Si vous relisez votre fonction dans un mois vous ne comprendrez plus ce que vous avez écrit.

Maintenant, comment créer l'ensemble des sous-parties d'une liste ?

L'idée est simple. Soit la liste [a; b; c] :
Au début on a "a". Les deux sous-parties correspondantes sont [a] et [].
Ensuite on a "b". Les deux nouvelles sous-parties sont [a; b] et [b]. Tiens, c'est curieux, c'est pile "b" ajouté à chaque liste précédente.
Enfin, on a "c". Les quatre nouvelles sous-parties sont [a; b; c], [b; c], [a; c] et [c]. Tiens, curieux encore, c'est pile "c" ajouté à chaque liste précédente.

Le code correspondant est donc le suivant :

Code :

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

1
2
3
4
5
6
7
8
 
let sousEnsemble l = 
  let rec aux acc = function
    | [] -> acc
    | a :: f -> 
      let acc = List.rev_append acc (List.rev_map (List.cons a) acc) in
      aux acc f
  in aux [[]] l

Attention a bien commencer avec une liste contenant la liste vide (qui correspond à la seule sous-partie d'un ensemble vide). (j'utilise les List.rev_* parce qu'ils sont récursifs terminaux, voici une version sans les rev_* :

Code :

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

1
2
3
4
5
6
7
let sousEnsemble l = 
  let rec aux acc = function
    | [] -> acc
    | a :: f -> 
      let acc = List.map (List.cons a) acc @ acc in
      aux acc f
  in aux [[]] l

[Fellowes]

Wahou!!!! Je m'inquiétais de recevoir un code que je devrais déchiffrer mais vous êtes un sacré pédagogue! Vous êtes prof?

Pour la récursivité terminal, c'est limpide! Je vais m'entraîner et l'utiliser un maximum, merci!

Alors pour l'ensemble des sous-listes, il me manquait la réflexion pour y arriver, c'est vraiment bien vu...
Pour le code en lui même, je n'ai pas le droit d'utiliser les fonctions List.map, List.rev etc...
Mais au moins j'ai la base de réflexion!

[TchoubiTchoub]

Hahaha ! Presque (chargé de TD) mais j'ai aimé enseigner depuis tout petit (mes frères et soeurs peuvent en témoigner).

C'est vrai que vous n'avez pas le droit d'utiliser les fonctions spécifiques du module List mais vu ce que vous avez réussi à faire je pense que vous y arriverez sans problème.

Soit dit en passant, pour vos premières fonctions, une étape importante dans ce genre de programme est de se rendre compte où on va passer le plus de temps et ce qui simplifierait cette perte de temps. Ici, par exemple, tout serait plus simple et plus rapide si l'invariant que vous maintenez pendant toute l'exécution est que chaque liste que vous manipulez est triée (notamment pour la recherche de doublon ou d'inclusion, par exemple).

Bon courage et n'hésitez pas à poser d'autres questions.

[Fellowes]

Je ne sais pas pourquoi mais je n'y arrive pas , j'essaye des choses mais je n'ai aucune idée de ce que je fais...


j'ai fait ça pour l'instant:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
 
let rec ajouterElem e l=match l with
	|[] -> [[e]]
	|a::f -> (e::a)::ajouterElem e f;;
 
 
let rec ensSousEns l=match l with
  |[]-> 
  |a::f ->   ;;

[TchoubiTchoub]

Regardez plutôt ce que font les fonctions que j'utilise dans la doc de OCaml : https://caml.inria.fr/pub/docs/manua...bref/List.html et essayez de les réimplémenter.

[Fellowes]

Ok, ça marche très bine du coup

Merci pour vos précieux conseil!