Discussion :

[alexpand]

Bonsoir à tous,

Je suis informaticien et j'ai 48 ans. Je suis dans la Production depuis 10 ans.
J'ai commencé à apprendre OCaml depuis 2 jours suite à un stage intensif (eLearning). J'ai plutôt de l'expérience sur des langages interprétés style Perl ou Shell et je dois vous avouer que ce type de langage me perturbe pas mal.
J'ai donc beaucoup de mal à comprendre ce langage fonctionnel (l'âge n'aidant pas...).

J'ai un exercice pour me permettre de maîtriser les listes récursives:

Nous définissons des multi-ensembles qui sont des ensembles avec répétitions. Par exemple, me =
{3,5,4,5,6,3,6} est un multi-ensemble d’entiers contenant deux exemplaires de 3, deux exemplaires de 5, un exemplaire de 4
et deux exemplaires de 6.
Introduisons le type ’e melt pour représenter plusieurs exemplaires d’une même valeur d’élément :

Code :

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

type ’e melt = ’e * int.

Un multi-ensemble est une collection d’éléments non ordonnés avec répétitions. Nous le représentons
par le type suivant :

Code :

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

type ’e mset = Nil | Cons of ’e melt * ’e mset.

Tous les exemplaires
d’une valeur d’élément sont regroupés dans un seul multi-élément. L’ensemble vide sera défini par let
empty = Nil.
Voici deux définitions possibles de me :

Code :

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

1
2
– let me = Cons((3,2), Cons((5,2), Cons((4,1), Cons((6,2), Nil)))),
– let me = Cons((6,2), Cons((3,2), Cons((5,2), Cons((4,1), Nil)))).

Je dois définir une fonction de ce type:

Code :

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

isempty : ’e mset -> bool

, où isempty s est vrai si s est un muti-ensemble vide.

Au départ, je pensais à cette fonction:

Code :

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

let isempty(a:'e mset) = if a = empty then true else false;;

Or, après réflexion, il me semble que la fonction doit retourner les résultats suivants:

Code :

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

1
2
3
4
5
let me1 = Cons((Nil,4),Nil)
isempty(me1) -> true
let me2 = Cons((Nil,4),Cons((3,2),Nil))
isempty(me2) -> false
isempty(empty) -> true

Donc, si x est un multi-élément (soit un couple (a,b) pour dire qu'il y a "b" fois le chiffre "a") et y est un multi-ensemble, pour que la fonction isempty retourne true, il faut que:
- x soit l'ensemble vide "empty" et
- isempty(y) retourne true

Avez-vous la même compréhension que moi ? Comment faire pour écrire cette sémantique en OCaml? Merci pour votre aide
De plus, je ne comprends pas pourquoi il est défini l'ensemble vide par let empty = Nil?

[TchoubiTchoub]

Bonjour,

Je réécris votre code ici avec le type inféré par l'interpréteur OCaml

Code :

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

1
2
3
4
5
6
type 'e melt = 'e * int;;
type 'e melt = 'e * int
type 'e mset = Nil | Cons of 'e melt * 'e mset;;
type 'e mset = Nil | Cons of 'e melt * 'e mset
let me = Cons((3,2), Cons((5,2), Cons((4,1), Cons((6,2), Nil))));;
val me : int mset = Cons ((3, 2), Cons ((5, 2), Cons ((4, 1), Cons ((6, 2), Nil))))

Jusque-là, tout va bien, me = {3,3,5,5,4,6,6}

En revanche, attention :

Code :

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

1
2
let me1 = Cons((Nil,4),Nil);;
val me1 : 'a mset mset = Cons ((Nil, 4), Nil)

Ne décrit pas l'ensemble {} mais {{}, {}, {}, {}} qui n'est pas l'ensemble vide.

Quand bien même, si vous vouliez définir isempty comme "isempty ms renvoie true si ms ne contient rien ou uniquement des ensembles vides il faudrait faire la chose suivante :

Code :

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

1
2
3
4
5
6
let rec isempty ms =
  match ms with
  | Nil -> true
  | Cons ((Nil, _), ms) -> isempty ms
  | Cons (_, _) -> false;;
val isempty : 'a mset mset -> bool = <fun>

Mais on voit bien que le type inféré spécifie bien que isempty ne prend que des multi-ensembles de multi-ensembles.

Je pense donc que la solution attendue est bien "si ms = {} alors ms est vide sinon ms n'est pas vide" qu'on préférera voir écrit (plutôt qu'avec un if ... then ... else) :

Code :

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

1
2
3
4
let isempty = function
  | Nil -> true
  | _ -> false;;
val isempty : 'a mset -> bool = <fun>

De plus, on met let empty = Nil pour la raison suivante :

Si on écrit le code suivant :

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
module type MSS = sig
 
  type 'e t
 
  val empty : 'e t
  val isempty : 'e t -> bool
 
end;;
 
module MS : MSS = struct
 
  type 'e melt = 'e * int
  type 'e t = Nil | Cons of 'e melt * 'e t
 
  let empty = Nil
 
  let isempty = function
    | Nil -> true
    | _ -> false
 
end;;
 
let ms = MS.empty;;

On a, par la signature MSS, caché la structure interne de notre multi-ensemble (ce qui nous permet de faire des modifications ultérieures dans notre module sans avoir à changer tout notre code.

Il m'est donc interdit d'écrire :

Code :

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

1
2
3
4
5
let ms = Nil;;
Characters 9-12:
  let ms = Nil;;
           ^^^
Error: Unbound constructor Nil

Car Nil n'est pas visible.

J'espère avoir pu vous aider ;-)

[alexpand]

Bonjour TchoubiTchoub,

Merci beaucoup pour votre aide.
Je n'ai pas encore tout compris : je suis au travail et donc je ne suis pas totalement concentré.

Mais encore merci pour ces explications très bien détaillées!

[TchoubiTchoub]

Avec plaisir.

Je me rends compte que j'ai codé avec des raccourcis de programmation :

Code :

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

let isempty = function

est équivalent à

Code :

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

let isempty ms = match ms with

N'hésitez pas à poser d'autres questions, j'y répondrai avec plaisir ;-)

[SpiceGuid]

Merci TchoubiTchoub.

Code :

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

val isempty : 'a mset mset -> bool = <fun>

Mais on voit bien que le type inféré spécifie bien que isempty ne prend que des multi-ensembles de multi-ensembles.

L'ennui avec les débutants c'est qu'il faut tout leur expliquer.
Ici en particulier, un débutant ne peut pas deviner que 'a mset mset c'est la même chose que ('a mset) mset. Certains débutants pensent (à tort) que c'est la même chose que 'a (mset mset)(qui n'est même pas un type valide).
À retenir :

• Le caractère espace (en tant qu'opérateur) est associatif à gauche.
• Le symbole flèche -> en tant qu'opérateur est associatif à droite.

J'ai plutôt de l'expérience sur des langages interprétés style Perl ou Shell et je dois vous avouer que ce type de langage me perturbe pas mal.
J'ai donc beaucoup de mal à comprendre ce langage fonctionnel (l'âge n'aidant pas...).

Ne faisons pas de jeunisme. L'âge n'y est pour pas grand chose.
Le fait est qu'OCaml est un langage pointilleux qui ne valorise pas beaucoup l'expérience acquise sur l'écrasante majorité des autres langages de programmation.

[alexpand]

Merci pour ces précisions. Je commence à comprendre ce langage qui, il est vrai, nécessite une rigueur

J'ai réussi à créer une fonction qui permet de retourner le nombre d'exemplaires d'un multi-ensemble

Code :

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

1
2
3
4
let nb_ex (me : 'e mset) : int =
  match me with
    | Nil -> 0
    | Cons ((x,y),z) -> y + nb_ex(z)

Qu'en pensez-vous ? Merci

Par contre, j'essaie de créer une autre fonction nb_occur comme suit:

’e -> ’e mset -> int, donne le nombre d’occurences d’un élément dans un muti-ensemble.

Tout d'abord, n'y a-t-il pas une erreur sur le profil de la fonction ? Le type 'e doit correspondre au type 'e melt, non ? Pourquoi ne pas le spécifier comme suit:

’e melt -> ’e mset -> int

Merci

[TchoubiTchoub]

Merci pour ces précisions. Je commence à comprendre ce langage qui, il est vrai, nécessite une rigueur

J'ai réussi à créer une fonction qui permet de retourner le nombre d'exemplaires d'un multi-ensemble

Code :

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

1
2
3
4
let nb_ex (me : 'e mset) : int =
  match me with
    | Nil -> 0
    | Cons ((x,y),z) -> y + nb_ex(z)

Qu'en pensez-vous ? Merci

Ah, on en arrive au premier point très important d'OCaml : la récursivité terminale (donc le fait qu'après un appel récursif il n'y ait rien à faire) (soit dit en passant, pensez à tester votre code avec l'interpréteur OCaml car je peux vous assurer que le vôtre ne compile pas du fait de l'absence de let rec)

Code :

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

1
2
3
4
let rec nb_ex me =
  match me with
    | Nil -> 0
    | Cons ((x,y),z) -> y + nb_ex z

Voilà un code qui compile. Ne mettez jamais les types en dur, OCaml les infère seul (sauf si c'est pour vous aider mais ce n'est pas une bonne habitude à prendre)

De plus, nul besoin de mettre des parenthèses pour les arguments ;-)

Revenons-en à la récursivité terminale :

Code :

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

Cons ((x,y),z) -> y + nb_ex z

Si on regarde cette ligne de code, on voit qu'après l'appel récursif nb_ex z on fait y + le résultat renvoyé par cet appel donc on va empiler des appels de fonctions.

Une façon propre de calculer cela est d'utiliser un accumulateur :

Code :

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

1
2
3
4
5
let nb_ex me =
  let rec nr acc = function
    | Nil -> acc
    | Cons ((x,y),z) -> nr (acc + y) z
  in nr 0 me

Ici, on crée une fonction interne qui ajoute à un accumulateur le nombre d'élément et qui renvoie celui-ci à la fin de l'appel. Comme on peut le voir, l'appel

Code :

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

nr (acc + y) z

est terminal car on n'a rien à faire après cet appel récursif. Le compilateur OCaml sait détecter la récursivité terminale et ne pas empiler les appels (vous ne devriez JAMAIS avoir de Stack Overflow en OCaml ;-))
En revanche, il faut mettre cette fois-ci des parenthèses autour de acc + y car les opérateurs sont infixes (on évalue tout ce qui est à gauche puis tout ce qui est à droite puis on applique l'opération).

Par contre, j'essaie de créer une autre fonction nb_occur comme suit:

’e -> ’e mset -> int, donne le nombre d’occurences d’un élément dans un muti-ensemble.

Tout d'abord, n'y a-t-il pas une erreur sur le profil de la fonction ? Le type 'e doit correspondre au type 'e melt, non ? Pourquoi ne pas le spécifier comme suit:

’e melt -> ’e mset -> int

Merci

Car 'e mset est un mset de 'e, pas de 'e melt. Si on mettait 'e melt, on aurait que

Code :

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

nb_occur (4,2) {(4,3)} = 0

or on veut écrire

Code :

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

nb_occur 4 {(4,3)}

et trouver 3 (les éléments présents dans l'ensemble sont bien du type 'e, le type 'e melt représente l'élément associé à un nombre.)

[alexpand]

Re-bonjour,

Après une dure journée de travail (Production oblige), me revoilà

Concernant l'erreur de compilation remontée, j'avais testé mon code OCaml dans l'interface web http://ocsigen.org/js_of_ocaml/files...vel/index.html et je n'ai pas eu d'erreur...

En fait, je n'ai pu faire l'installation sur mon poste car le téléchargement du livrable http://gallium.inria.fr/~protzenk/ca...ller4-opam.exe tombe en erreur à cause du blocage de mon antivirus (impossible de le désactiver temporairement car configurer comme telle sur mon poste de travail).

Sinon, pour revenir à la programmation, merci TchoubiTchoub pour les explications : je viens de comprendre la notion de polymorphisme sur les typages. Je n'avais pas bien saisi l'apostrophe lors de la déclaration des types melt et mset. En fait, OCaml permet de générer des listes d’objets de même type sans que ce type soit précisé :

Si j'ai bien compris, OCaml infère automatiquement lorsque la valeur est renseignée au moment de la déclaration :

Elément de type entier :

Code :

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

1
2
let a = Cons((4,3),Nil);;
val a : int mset = Cons ((4, 3), Nil)

Elément de type booléen :

Code :

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

1
2
let a = Cons((true,3),Nil);;
val a : bool mset = Cons ((true, 3), Nil)

Concernant la fonction nb_ex: je n'ai pas très bien saisi le code avec l'accumulateur mais j'ai bien compris cette notion d'empilement d'appels de fonctions

Je vais maintenant m'atteler à la fonction nb_occur

EDIT: et voici la fonction

Code :

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

1
2
3
4
let rec nb_occ e me = match me with
  | Nil -> 0
  | Cons((x,y),z) when x=e -> y
  | Cons((_,_),z) -> nb_occ e z

Et les tests:

Code :

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

1
2
3
4
5
6
7
8
9
10
let me = Cons((4,2),Cons((5,1),Cons((3,2),Nil)));;
val me : int mset = Cons ((4, 2), Cons ((5, 1), Cons ((3, 2), Nil)))
nb_occ 4 Nil;;
- : int = 0
nb_occ 4 me;;
- : int = 2
nb_occ 5 me;;
- : int = 1
nb_occ 3 me;;
- : int = 2

EDIT2: une autre fonction pour vérifier si un élément est dans un sous-ensemble:

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 member e me = if me = Nil then false else if nb_occ e me = 0 then false else true;;
val member : 'a -> 'a mset -> bool = <fun>
let me = Cons((4,2),Cons((5,1),Cons((3,2),Nil)));;
val me : int mset = Cons ((4, 2), Cons ((5, 1), Cons ((3, 2), Nil)))
member 4 me;;
- : bool = true
member 3 me;;
- : bool = true
member 2 me;;
- : bool = false
member 1 me;;
- : bool = false
member 0 me;;
- : bool = false
member 0 Nil;;
- : bool = false

NB: Par contre, je n'ai pas réussi à utiliser le pattern-matching: ok pour le sous-ensemble vide (Nil -> false) mais savez-vous comment faire ? Merci

EDIT3: et une dernière pour la route subset : ’e mset -> ’e mset -> bool, où (subset s1 s2) est vrai si et seulement si s1 inclus dans s2.

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
let rec subset me1 me2 = match me1 with | Nil -> true | Cons((x,_),y) -> member x me2 && nb_occ x me1 <= nb_occ x me2 && subset y me2;;
val subset : 'a mset -> 'a mset -> bool = <fun>
let me1 = Cons((4,2),Nil);;
val me1 : int mset = Cons ((4, 2), Nil)
let me2 = Cons((4,2),Cons((5,3),Cons((6,1),Nil)));;
val me2 : int mset = Cons ((4, 2), Cons ((5, 3), Cons ((6, 1), Nil)))
subset me1 me2;;
- : bool = true
let me1 = Cons((4,1),Nil);;
val me1 : int mset = Cons ((4, 1), Nil)
subset me1 me2;;
- : bool = true
let me1 = Cons((4,3),Nil);;
val me1 : int mset = Cons ((4, 3), Nil)
subset me1 me2;;
- : bool = false
subset Nil me2;;
- : bool = true

Vos avis m'intéressent

Bonne soirée

EDIT4: Bonjour à tous : avant de commencer ma journée, rien qu'une petite fonction en OCaml

add : ’e melt -> ’e mset -> ’e mset, ajoute un certain nombre d’occurences d’un élément dans le muti-ensemble

Je vous avoue que je viens de passer 1h sur cette fonction et je n'arrive toujours pas à la faire fonctionner.
Je pensais que l'ajout serait simple mais en fait, il faut vérifier si l'élément (e,n) est présent dans le multi-ensemble s et si oui, ajouter le nombre d'occurences n au nombre d'occurences de e dans s.

Voici le message d'erreur que j'obtiens:

Code :

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

1
2
3
4
5
let add (e,n) s = if member (e,n) s then Cons((e,nb_occ e s + nb_occ e Cons(e,Nil)),s) else Cons((e,n),s);;
File "", line 1, characters 58-59:
Error: This expression has type ('a * 'b) mset
       but an expression was expected of type 'a mset
       The type variable 'a occurs inside 'a * 'b

Par contre, le problème de cette fonction, c'est qu'elle ajoute un élément en plus. Du coup, pour un multi-ensemble s Cons((4,1),Cons((6,3),Nil)), la fonction add (4,2) s avec l'algorithme ci-dessus risque de retourner Cons((4,3),Cons((4,1),Cons((6,3),Nil)))

Merci pour votre aide

[TchoubiTchoub]

Re-bonjour,

Bonjour :-)

Après une dure journée de travail (Production oblige), me revoilà

Concernant l'erreur de compilation remontée, j'avais testé mon code OCaml dans l'interface web http://ocsigen.org/js_of_ocaml/files...vel/index.html et je n'ai pas eu d'erreur...

Etrange car je teste sur ce même site et j'ai bien l'erreur que j'attends : "Unbound value nb_ex"

Sinon, pour revenir à la programmation, merci TchoubiTchoub pour les explications : je viens de comprendre la notion de polymorphisme sur les typages. Je n'avais pas bien saisi l'apostrophe lors de la déclaration des types melt et mset. En fait, OCaml permet de générer des listes d’objets de même type sans que ce type soit précisé :

Si j'ai bien compris, OCaml infère automatiquement lorsque la valeur est renseignée au moment de la déclaration :

Elément de type entier :

Code :

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

1
2
let a = Cons((4,3),Nil);;
val a : int mset = Cons ((4, 3), Nil)

Elément de type booléen :

Code :

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

1
2
let a = Cons((true,3),Nil);;
val a : bool mset = Cons ((true, 3), Nil)

Oui ! Vous avez tout compris !

Vous pouvez donc donner le type de la fonction

Code :

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

f x y = (x, y)

Concernant la fonction nb_ex: je n'ai pas très bien saisi le code avec l'accumulateur mais j'ai bien compris cette notion d'empilement d'appels de fonctions

Regardons avec une pile d'appel :

Sur votre version de nb_ex :

Code :

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

1
2
3
4
5
6
nb_ex (Cons (('a', 3), (Cons (('b', 4), Nil)))) =
  3 + nb_ex (Cons (('b', 4), Nil))
    3 + 4 + nb_ex Nil
      3 + 4 + 0
    3 + 4
  7

Avec l'accumulateur, on a la chose suivante

Code :

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

1
2
3
4
5
nb_ex (Cons (('a', 3), (Cons (('b', 4), Nil)))) =
  nr 0 (Cons (('a', 3), (Cons (('b', 4), Nil))))
  nr (3+0=3) (Cons (('b', 4), Nil))
  nr (3+4=7) Nil
  = 7

Voici un début de réponse, je regarde la suite après et je modifierai donc directement ce message

Code :

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

1
2
3
4
let rec nb_occ e me = match me with
  | Nil -> 0
  | Cons((x,y),z) when x=e -> y
  | Cons((_,_),z) -> nb_occ e z

Ahhh, ça me rappelle mes TDs d'OCaml où l'étudiant est tout content et on vient lui casser son truc en lui rappelant qu'il a oublié un petit détail. Le détail, le voici :

Code :

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

1
2
nb_occ 4 (Cons ((4,1), (Cons ((4,2), Nil))));;
- : int = 1

Vous avez oublié de prendre en compte le fait qu'on puisse mettre deux Cons avec le même x (et même le même y).

Dans ce cas-là, vous avez plusieurs solutions

• Vous changez votre fonction nb_occ pour qu'elle gère ce cas (en récursif terminal, bien sûr)
• Vous faites en sorte qu'il soit impossible de créer une valeur de type 'e mset sans passer par une fonction

Je vous laisse faire la première solution. La deuxième est très amusante mais introduit plein de notions inconnues, je vous la mets donc ici commentée :

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
module MS : sig
 
  type 'e melt = 'e * int
  (* le mot clé private (à mettre dans une signature) 
     spécifie qu'on ne peut pas créer de valeur de ce type hors
     du module. Si on le fait on obtient l'erreur suivante :
     Cons (('b', 4), Nil)
     Error: Cannot create values of the private type char MS.t 
  *)
  type 'e t = private Nil | Cons of 'e melt * 'e t
 
  val empty : 'e t
  val add : 'e melt -> 'e t -> 'e t
 
end = struct
 
  type 'e melt = 'e * int
  type 'e t = Nil | Cons of 'e melt * 'e t
 
  let empty = Nil
 
  (* Cette fonction n'est pas récursive terminale, je vous invite
     donc à essayer d'en faire une version récursive terminale.
     Elle permet d'unir deux mset.
  *)
  let rec union t1 t2 =
    match t1, t2 with
      (* Petit raccourci, si un des deux ensembles est vide je renvoie l'autre
         donc, ici, si un ensemble est Nil, on nomme l'autre t (ce qui n'est
         pas une valeur donc on signale seulement qu'on veut nommer ainsi
         l'élément matché et on le renvoie. C'est un cas typique du pattern
         matching : match e1 with A | B | C -> e2.
      *)
      | Nil, t | t, Nil -> t
      | Cons (e, t1'), _ -> Cons (e, union t1' t2)
 
  let add (x, nb) t = 
    let rec ar acc t =
      match t with
        | Nil -> Cons ((x, nb), acc)
        (* Si l'élément en tête de t est égal à x, alors on augmente le
           nombre de x et on termine, c'est la sémantique de
           match e1 with A when P -> e2 qui dit qu'on ne prend cette branche
           que lorsque la propriété P est vérifiée
        *)
        | Cons ((x', nb'), t') when x = x' ->
          Cons ((x', nb' + nb), union t' acc)
        (* Cette version de add est récursive terminale (elle est même 
           bien plus facile comme-ça !)
        *)
        | Cons (e, t') -> ar (Cons (e, acc)) t'
    in ar Nil t
end

Pour créer un nouvel ensemble on écrit donc :

Code :

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

MS.add (4, 1) (MS.add (4, 2) MS.empty)

EDIT2: une autre fonction pour vérifier si un élément est dans un sous-ensemble:

Code :

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

let member e me = if me = Nil then false else if nb_occ e me = 0 then false else true;;

Ce n'est pas très beau mais avec le code que je vous ai mis au-dessus vous devriez y arriver plus facilement, non ?

EDIT3: et une dernière pour la route subset : ’e mset -> ’e mset -> bool, où (subset s1 s2) est vrai si et seulement si s1 inclus dans s2.

Code :

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

1
2
let rec subset me1 me2 = match me1 with | Nil -> true | Cons((x,_),y) -> member x me2 && nb_occ x me1 <= nb_occ x me2 && subset y me2;;
val subset : 'a mset -> 'a mset -> bool = <fun>

Idem, il y a mieux à faire.

add : ’e melt -> ’e mset -> ’e mset, ajoute un certain nombre d’occurences d’un élément dans le muti-ensemble

Je viens de me rendre compte que je vous ai mis la solution dans ma réponse mais c'est bonus, cadeau du matin !

Code :

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

1
2
3
4
5
let add (e,n) s = if member (e,n) s then Cons((e,nb_occ e s + nb_occ e Cons(e,Nil)),s) else Cons((e,n),s);;
File "", line 1, characters 58-59:
Error: This expression has type ('a * 'b) mset
       but an expression was expected of type 'a mset
       The type variable 'a occurs inside 'a * 'b

Ah mais c'est normal ! Si vous regardez bien vous appelez member (e, n) s or member est de type 'e -> 'e mset -> bool

De plus,

Code :

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

let member e me = if me = Nil then false else if nb_occ e me = 0 then false else true

BERK !

Code :

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

let member e me = me <> Nil && nb_occ e me <> 0

Mieux !

Code :

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

let member e me = nb_occ e me <> 0

Encore mieux car nb_occ gère déjà le cas Nil !

[alexpand]

Bonjour TchoubiTchoub,

Je n'ai pas encore eu le temps de tout lire mais il est vrai qu'il me reste encore beaucoup à apprendre...
Je lirai vos commentaires cet après-midi entre deux incidents

Merci encore pour ce retour rapide et détaillé!

[alexpand]

Bonsoir TchoubiTchoub,

Je reprends seulement maintenant la programmation OCaml (et oui, difficile de trouver du temps libre entre le travail et la famille ).
Après avoir lu vos retours, en fait, je me suis rendu compte que nous n'avions pas (encore) abordé la récursivité terminale. Du coup, cette histoire d'accumulateur n'est pour l'instant inconnue pour l'ensemble des participants à la formation.

Par conséquent, je vais rester sur la récursivité normale. Par contre, j'ai bien compris le fonctionnement (merci pour ton exemple qui est très clair!) et je pense que cette partie sera abordée dans les prochaines semaines

Revenons à nos fonctions! Après avoir vu avec notre formateur, il s'avère que nous considérons qu'il n'y a pas de doublon du même élément dans un multi-ensemble. Ainsi, on ne peut pas avoir un multi-ensemble avec les éléments suivants Cons ((1,2), (3, 2), (1, 1), Nil). Le multi-ensemble correspond est Cons ((1,3), (3, 2), Nil)

Du coup, cela simplifie nos fonctions!!

Code :

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

1
2
3
4
let rec nb_occ e me = match me with 
  | Nil -> 0
  | Cons ((x, n), y) when x=e -> n
  | Cons ((_, _), x) -> nb_occ e x

Je me suis lancé sur les autres fonctions demandées:

subset : ’e mset -> ’e mset -> bool, où (subset s1 s2) est vrai si et seulement si s1 inclus dans s2.

Code :

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

1
2
3
let rec subset me1 me2 = match me1 with
  | Nil -> true
  | Cons ((x, _),y) -> member x me2 && nb_occ x me1 <= nb_occ x me2 && subset y me2

add : ’e melt -> ’e mset -> ’e mset, ajoute un certain nombre d’occurences d’un élément dans le muti-ensemble.

Code :

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

1
2
3
4
let rec add (x,n) me = match me with
  | Nil -> Cons ((x,n), me)
  | Cons ((x',n'), me') when x=x' -> Cons ((x,n+n'), me')
  | Cons (e, me') -> Cons (e, add (x,n) me')

remove : ’e melt -> ’e mset -> ’e mset, où (remove (e, n) s) supprime n occurrences de e dans s.

Code :

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

1
2
3
4
5
let rec remove (x, n) s = match s with
  | Nil -> Nil
  | Cons ((x', n'), s') when x=x' && n>=n' -> s'
  | Cons ((x', n'), s') when x=x' -> Cons ((x, n'-n), s')
  | Cons (e, s') -> Cons (e, remove (x, n) s')

equal : ’e mset -> ’e mset -> bool, où equal s1 s2 = vrai si et seulement si s1 et s2 contiennent les mêmes éléments et en même nombre.

Code :

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

let equal s1 s2 = subset s1 s2 && subset s2 s1

sum : ’e mset -> ’e mset -> ’e mset (ta fonction union m'a bien aidé )

Code :

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

1
2
3
let rec sum s1 s2 = match (s1,s2) with
  | (Nil,s) -> s
  | Cons ((x,n), s), _ -> sum s (add (x,n) s2)

Pour sum, je n'ai pas mis le pattern-matching (s, Nil) car la fonction add le gère.

intersection : ’e mset -> ’e mset -> ’e mset

Pour cette fonction, je cale un peu. Dans l'idée, c'est pour chaque élément du multi-ensemble s1, je vérifie s'il appartient au multi-ensemble s2 -> si c'est le cas, je crée un nouveau multi-ensemble avec l'élément qui matche et j'applique la récursivité sur le reste du mulit-ensemble s1.

Code :

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

1
2
3
4
let rec intersection s1 s2 = match (s1, s2) with
  | (Nil, s) | (s, Nil) -> Nil
  | Cons ((x,n), s), _ where subset (Cons ((x,n), Nil)) s2 -> Cons ((x,n), intersection s s2)
  | Cons (_,s),_ -> intersection s s2

J'ai l'impression que l'expression subset ne passe pas...
Il est tard, donc je verrai ça demain.

Bonne soirée (ou Bonjour car il est quand même 4h passé!!)

EDIT1: arf, je n'arrivais pas à dormir à cause de cette erreur. En fait, je viens de voir pourquoi: il y avait une erreur sémantique: j'ai utilisé where au lieu de when

Code :

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

1
2
3
4
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons (e, s),y when subset (Cons (e, Nil)) y -> Cons (e, intersection s s2)
  | Cons (_, s), _ -> intersection s s2

EDIT2: Bonjour (et oui, la nuit a été courte )
Il m'est maintenant demandé de réaliser une fonction d'ordre supérieur sur certaines fonctions déjà créées:

Spécifier et réaliser une fonction d’ordre supérieur fold_mset qui applique récursivement une
fonction f à deux arguments sur un élément d’initialisation a et un multi-ensemble s, en parcourant
les éléments de s du premier au dernier. Autrement dit, fold_mset f a s retourne
f . . . ( f ( f a s0 ) s1 ) . . . sn􀀀1, où s0, s1, . . . désignent les différents éléments de s.
– En utilisant la fonction d’ordre supérieur fold_mset, réécrivez les fonctions suivantes de la partie
précédente :
1. nb_ex ;
2. subset ;
3. sum ;
4. intersection.

Nous avons abordé les fonctions d'ordre supérieur mais je vous avoue que je n'ai pas vraiment compris comment l'utiliser dans ce cas précis.

Je vois ce profil de fonction mais après, je ne comprends pas comment l'utiliser sur la fonction nb_ex:

Code :

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

1
2
let fold_mset f a s = f (f a s)
val fold_mset : ('a -> 'b -> 'a) -> 'a -> 'b -> 'b -> 'a = <fun>

Merci pour votre aide

[TchoubiTchoub]

Après avoir lu vos retours, en fait, je me suis rendu compte que nous n'avions pas (encore) abordé la récursivité terminale.

Ce n'est pas très compliqué et c'est une bonne habitude à prendre, vivement que cela arrive dans votre formation

Revenons à nos fonctions! Après avoir vu avec notre formateur, il s'avère que nous considérons qu'il n'y a pas de doublon du même élément dans un multi-ensemble. Ainsi, on ne peut pas avoir un multi-ensemble avec les éléments suivants Cons ((1,2), (3, 2), (1, 1), Nil). Le multi-ensemble correspond est Cons ((1,3), (3, 2), Nil)

Du coup, cela simplifie nos fonctions!!

Oui, on peut considérer cela comme un invariant du système mais dans votre construction rien ne l'assure. Je n'étais pas peu fier de mon super module

Code :

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

1
2
3
4
let rec nb_occ e me = match me with 
  | Nil -> 0
  | Cons ((x, n), y) when x=e -> n
  | Cons ((_, _), x) -> nb_occ e x

Ouaip, là c'est tout de suite plus évident !

subset : ’e mset -> ’e mset -> bool, où (subset s1 s2) est vrai si et seulement si s1 inclus dans s2.

Code :

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

1
2
3
let rec subset me1 me2 = match me1 with
  | Nil -> true
  | Cons ((x, _),y) -> member x me2 && nb_occ x me1 <= nb_occ x me2 && subset y me2

Là encore, je ne comprends pas pourquoi vous écrivez member x me2 puis nb_occ x me1 <= nb_occ x me2 car vous êtes bien d'accord que member x me2 est inutile, non ?

EDIT1: arf, je n'arrivais pas à dormir à cause de cette erreur. En fait, je viens de voir pourquoi: il y avait une erreur sémantique: j'ai utilisé where au lieu de when

J'aurais dit lexicale ou syntaxique

Pour l'intersection, je ne suis pas sûr que votre subset soit la bonne solution. J'aurais plutôt dit que si j'ai 4 'a' dans l'un et 2 'a' dans l'autre, alors j'ai 2 'a' dans le résultat (alors que votre subset ne fonctionne que si le premier est subset de l'autre, non ?)

EDIT2: Bonjour (et oui, la nuit a été courte )

Bonjour

Il m'est maintenant demandé de réaliser une fonction d'ordre supérieur sur certaines fonctions déjà créées:
Nous avons abordé les fonctions d'ordre supérieur mais je vous avoue que je n'ai pas vraiment compris comment l'utiliser dans ce cas précis.

Je vois ce profil de fonction mais après, je ne comprends pas comment l'utiliser sur la fonction nb_ex:

Code :

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

1
2
let fold_mset f a s = f (f a s)
val fold_mset : ('a -> 'b -> 'a) -> 'a -> 'b -> 'b -> 'a = <fun>

Merci pour votre aide

Ah, enfin un nouveau défi !

Déjà, êtes-vous sûr de la signature de fold_mset ? J'aurais plutôt dit que

Code :

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

1
2
3
4
let rec fold_mset f a s = 
  match s with
    | Nil -> a
    | Cons (e, s') -> fold_mset f (f a e) s'

(Ce qui correspond à la version récursive terminale du fold, étrange vu que vous n'avez pas encore vu ce concept, enfin bon...)

Donc son type est :

Code :

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

val fold_mset : ('a -> 'b -> 'a) -> 'a -> 'b mset -> 'a

Le principe de fold_mset est donc de prendre une fonction qui peut être appliquée à un élément du mset (donc à un 'e melt) et de l'appliquer automatiquement tout au long du mset.

Par exemple, avec nb_ex, on pourrait définir :

Code :

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

1
2
let incr_counter acc (_, i) = acc + i
val incr_counter : int -> 'a * int -> int = <fun>

(ce n'est pas moi qui ai mis l'accumulateur, hein, c'est vous )

Et fold_mset est la fonction telle que je l'ai définie au-dessus.

Donc

Code :

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

let nb_ex ms = fold_mset incr_counter 0 ms

Bonne journée de travail et à bientôt

[alexpand]

Ce n'est pas très compliqué et c'est une bonne habitude à prendre, vivement que cela arrive dans votre formation

Bonsoir,

En effet, je pense que nous l'avons vu en cours : en fait, je m'étais plus concentré sur cette notion d'accumulateur mais notre formateur ne l'a pas signifié de la même façon

Oui, on peut considérer cela comme un invariant du système mais dans votre construction rien ne l'assure. Je n'étais pas peu fier de mon super module

Oui, vous pouvez

Ouaip, là c'est tout de suite plus évident !

Ah, une fonction enfin bien codée! Merci

Là encore, je ne comprends pas pourquoi vous écrivez member x me2 puis nb_occ x me1 <= nb_occ x me2 car vous êtes bien d'accord que member x me2 est inutile, non ?

Je confirme: je me suis fait des noeuds au cerveau...

Pour l'intersection, je ne suis pas sûr que votre subset soit la bonne solution. J'aurais plutôt dit que si j'ai 4 'a' dans l'un et 2 'a' dans l'autre, alors j'ai 2 'a' dans le résultat (alors que votre subset ne fonctionne que si le premier est subset de l'autre, non ?)

Je ne vois pas en fait ce que vous voulez dire.

Ah, enfin un nouveau défi !

Déjà, êtes-vous sûr de la signature de fold_mset ? J'aurais plutôt dit que

Code :

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

1
2
3
4
let rec fold_mset f a s = 
  match s with
    | Nil -> a
    | Cons (e, s') -> fold_mset f (f a e) s'

(Ce qui correspond à la version récursive terminale du fold, étrange vu que vous n'avez pas encore vu ce concept, enfin bon...)

J'avais mis le profil de la fonction sans réelle conviction: je pense que la vôtre est plus appropriée

Donc son type est :

Code :

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

val fold_mset : ('a -> 'b -> 'a) -> 'a -> 'b mset -> 'a

Le principe de fold_mset est donc de prendre une fonction qui peut être appliquée à un élément du mset (donc à un 'e melt) et de l'appliquer automatiquement tout au long du mset.

Par exemple, avec nb_ex, on pourrait définir :

Code :

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

1
2
let incr_counter acc (_, i) = acc + i
val incr_counter : int -> 'a * int -> int = <fun>

(ce n'est pas moi qui ai mis l'accumulateur, hein, c'est vous )

Et fold_mset est la fonction telle que je l'ai définie au-dessus.

Donc

Code :

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

let nb_ex ms = fold_mset incr_counter 0 ms

Bonne journée de travail et à bientôt

Je vais regarder cette histoire d'accumulateur ce week-end. Pour l'instant, je vais me reposer car la nuit dernière a été très courte.

Merci encore pour votre aide car sans vous, je n'aurai pas réussi à assimiler ces notions de langage qui sont très particulières

Bonne soirée et à bientôt

EDIT1: bon, quand on y prend goût, on ne s'arrête plus

Cette fois-ci, la fonction difference :
difference : ’e mset -> ’e mset -> ’e mset, où difference s1 s2 = s1 \ s2 (on retire tous les éléments de s2 qui sont dans s1).

l

Code :

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

1
2
3
4
let rec difference s1 s2 = match s1, s2 with
  | s, Nil -> s
  | Nil, s -> Nil
  | x, Cons (e, y) -> difference (remove e x) y

Aucune erreur lors de la compilation. Par contre, en testant, j'ai l'erreur suivante:

Code :

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

1
2
3
4
5
6
7
8
let rec difference s1 s2 = match s1, s2 with | s, Nil -> s | Nil, s -> Nil | _, Cons (e, x) -> difference (remove e s1) x;;
val difference : 'a mset -> 'a mset -> 'a mset = <fun>
s1;;
- : int mset = Cons ((4, 2), Cons ((5, 1), Nil))
s2;;
- : int mset = Cons ((1, 1), Cons ((2, 4), Nil))
difference s1 s2;;
Exception: Match_failure ("", 1, 22).

[TchoubiTchoub]

Je ne vois pas en fait ce que vous voulez dire.

Vous avez écrit

Code :

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

1
2
3
4
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons (e, s),y when subset (Cons (e, Nil)) y -> Cons (e, intersection s s2)
  | Cons (_, s), _ -> intersection s s2

Or ce n'est pas vraiment l'intersection. Votre deuxième cas peut être lu comme :

si j'ai s1 du type Cons (e, s1') et s2 d'un type quelconque et l'élément Cons(e, Nil) est un sous-ensemble de s2 alors mon intersection est l'élément e ajouté à l'intersection de s1' et s2.

Or ce n'est pas tout à fait ça. C'est plutôt

si j'ai s1 du type Cons((e, i1), s1') et je peux trouver l'élément (e, i2) dans s2, alors l'intersection est l'élément e dont le nombre d'occurrences est le minimum entre son nombre d'occurrences dans s1 et dans s2

(donc, par exemple, dans votre cas Cons (('a', 2), Nil) Cons(('a', 1), Nil) aurait renvoyé Nil alors que dans mon cas il renvoie Cons(('a', 1), Nil).

EDIT1: bon, quand on y prend goût, on ne s'arrête plus

Ah ça !

Cette fois-ci, la fonction difference :
difference : ’e mset -> ’e mset -> ’e mset, où difference s1 s2 = s1 \ s2 (on retire tous les éléments de s2 qui sont dans s1).

Code :

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

1
2
3
4
let rec difference s1 s2 = match s1, s2 with
  | s, Nil -> s
  | Nil, _ -> Nil
  | x, Cons (e, y) -> difference (remove e x) y

Aucune erreur lors de la compilation. Par contre, en testant, j'ai l'erreur suivante:

Code :

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

1
2
3
4
5
6
7
8
let rec difference s1 s2 = match s1, s2 with | s, Nil -> s | Nil, s -> Nil | _, Cons (e, x) -> difference (remove e s1) x;;
val difference : 'a mset -> 'a mset -> 'a mset = <fun>
s1;;
- : int mset = Cons ((4, 2), Cons ((5, 1), Nil))
s2;;
- : int mset = Cons ((1, 1), Cons ((2, 4), Nil))
difference s1 s2;;
Exception: Match_failure ("", 1, 22).

Etrange, je n'ai eu aucun bug.

[alexpand]

Bonjou TchoubiTchoub

J'espère que vous avez passé un bon week-end ?
Pour ma part, oui. J'ai dû laisser un peu de côté la programmation pour passer du temps en famille.

Mais me voilà de retour Je vais par contre avoir un examen demain sur la première partie de la formation
Donc, je vais tenter de finaliser les fonctions présentes (qui sont en bonus dans les exercices) pour bien comprendre tous les aspects vu en cours.

C'est reparti! Merci d'abord pour votre retour.

Vous avez écrit

Code :

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

1
2
3
4
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons (e, s),y when subset (Cons (e, Nil)) y -> Cons (e, intersection s s2)
  | Cons (_, s), _ -> intersection s s2

Or ce n'est pas vraiment l'intersection. Votre deuxième cas peut être lu comme :

si j'ai s1 du type Cons (e, s1') et s2 d'un type quelconque et l'élément Cons(e, Nil) est un sous-ensemble de s2 alors mon intersection est l'élément e ajouté à l'intersection de s1' et s2.

Or ce n'est pas tout à fait ça. C'est plutôt

si j'ai s1 du type Cons((e, i1), s1') et je peux trouver l'élément (e, i2) dans s2, alors l'intersection est l'élément e dont le nombre d'occurrences est le minimum entre son nombre d'occurrences dans s1 et dans s2

(donc, par exemple, dans votre cas Cons (('a', 2), Nil) Cons(('a', 1), Nil) aurait renvoyé Nil alors que dans mon cas il renvoie Cons(('a', 1), Nil).

Ok, j'ai compris. Merci!

Code :

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

1
2
3
4
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons ((e, n1'), s1'), _ when nb_occurrences e s2 <> 0 -> Cons ((e, min n1' (nb_occurrences e s2)), intersection s1' s2)
  | Cons (_, s), _ -> intersection s s2

Par contre, est-il possible de simplifier car j'ai l'impression qu'elle est un peu "lourde" ?

Etrange, je n'ai eu aucun bug.

En effet, je viens de tester la fonction et elle marche! Et dire que j'ai perdu 4h...

Je continue

[TchoubiTchoub]

Bonjour TchoubiTchoub

J'espère que vous avez passé un bon week-end ?

Pas beaucoup de repos mais bon weekend

Pour ma part, oui. J'ai dû laisser un peu de côté la programmation pour passer du temps en famille.

Idem

Mais me voilà de retour Je vais par contre avoir un examen demain sur la première partie de la formation

Diz iz laïfe ! Beute laïfe iz izi !

Code :

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

1
2
3
4
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons ((e, n1'), s1'), _ when nb_occurrences e s2 <> 0 -> Cons ((e, min n1' (nb_occurrences e s2)), intersection s1' s2)
  | Cons (_, s), _ -> intersection s s2

Par contre, est-il possible de simplifier car j'ai l'impression qu'elle est un peu "lourde" ?

Code :

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

1
2
3
4
5
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons ((e, n1), s1'), _ -> let m = min n1 (nb_occurences e s2) in
    let i = intersection s1' s2 in
    if m = 0 then i else Cons ((e, m), i)

Ou, encore mieux, (car on voit que s2 n'est jamais changé)

On réécrit nb_occurences e de telle sorte qu'elle nous renvoie le nombre d'occurrences de e ainsi que le mset auquel on a enlevé e.

Code :

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

1
2
3
4
5
6
let get_and_remove e me = 
  let rec gr acc = function
    | Nil -> 0, acc
    | Cons((x,y),z) when x = e -> y, union acc z
    | Cons(e, z) -> gr (Cons (e, acc)) z
  in gr Nil me

Et le nouveau code de l'intersection donne :

Code :

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

1
2
3
4
5
6
7
let rec intersection s1 s2 = match s1, s2 with
  | Nil, s | s, Nil -> Nil
  | Cons ((e, n1), s1'), _ -> 
    let n2, s2' = get_and_remove e s2 in
    let m = min n1 n2 in
    let i = intersection s1' s2' in
    if m = 0 then i else Cons ((e, m), i)

Mais là on touche à un problème d'algorithmique très intéressant. Savoir choisir sa structure de donnée. Si vous voulez créez un ensemble pour lequel vous faites (en proportions), 100 ajouts, 1 suppression et 1 intersection, votre liste convient très bien car l'ajout d'un élément est O(1).

En revanche, si vous voulez faire beaucoup d'intersections, une liste triée irait mieux. La question est donc, quand la trier ? On pourrait la trier à l'ajout (donc avec l'interdiction de créer un mset nous même mais en passant par une fonction add.) C'est tout l'avantage de la programmation modulaire. Par exemple, dans le module que je vous avais mis, je peux remplacer add comme ceci :

Code :

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

1
2
3
4
5
6
let add_trie (x, nb) t =
    let rec insert = function
      | Cons ((x', _) as e, t') when x' < x -> Cons (e, insert t')
      | Cons ((x', nb') , t') when x = x' -> Cons ((x, nb+nb'), t')
      | t -> Cons ((x, nb), t)
    in insert t

(on a trois cas,

• Soit x est supérieur à l'élément courant donc on devra l'insérer dans la suite
• Soit x est égal à l'élément courant donc on augmente le nombre de x présents
• Soit x est le plus petit élément donc on l'ajoute en tête du mset traité

(C'est un simple tri par insertion )

Exemple :

Code :

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

1
2
let a = add_triee (2, 1) (add_triee (4, 1) (add_triee (3, 2) Nil));;
val a : int t = Cons ((2, 1), Cons ((3, 2), Cons ((4, 1), Nil)))

Nous allons avoir besoin d'une fonction reverse qui retourne un mset (e.g.

Code :

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

1
2
3
4
# let a = Cons ((4,1), (Cons ((2,1), Nil)));;
val a : int t = Cons ((4, 1), Cons ((2, 1), Nil))
# let ra = reverse a;;
val ra : int t = Cons ((2, 1), Cons ((4, 1), Nil))

)

Le code de cette fonction est laissé en exercice mais il est super simple !

La fonction intersection devient donc :

Code :

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

1
2
3
4
5
6
7
8
9
10
let rec intersection_triee s1 s2 = 
  let rec ir acc s1 s2 = match s1, s2 with
    | Nil, s | s, Nil -> acc
    | Cons ((e1, _), _), Cons ((e2, _), s2') when e1 > e2 ->
      ir acc s1 s2'
    | Cons ((e1, _), s1'), Cons ((e2, _), _) when e1 < e2 ->
      ir acc s1' s2
    | Cons ((e1, n1), s1'), Cons ((_, n2), s2') ->
      ir (Cons ((e1, min n1 n2), acc)) s1' s2'
  in reverse (ir Nil s1 s2)

Le fait d'avoir un ensemble toujours trié permet de faire l'intersection en temps linéaire (à chaque itération on supprime au minimum un élément de notre recherche donc on a une complexité en O(n1 + n2) (n1 et n2 étant les cardinaux des deux ensembles) alors que pour l'intersection précédente, pour chaque élément de s1 on explorait potentiellement tout s2 donc une complexité en O(n1 * n2) (complexité linéaire face à quadratique, pas photo sauf si vos ensembles ont un seul élément )

On remarquera aussi que je n'utilise pas add_triee car l'accumulateur contient au fur et à mesure une liste triée en sens inverse donc il me suffit, à la fin, de retourner (dans le sens retourner, par return des anglais) le résultat final et de renvoyer (dans le sens return des anglais ) ce résultat.

En effet, je viens de tester la fonction et elle marche! Et dire que j'ai perdu 4h...

Hahaha ! Etrange, quand-même. Vous aviez testé votre code avec l'interpréteur en mode Tuareg sous emacs ? (je pose la question car parfois Tuareg part dans les platanes et il vaut mieux redémarrer l'éditeur )

Bon courage pour votre examen

[alexpand]

Merci TchoubiTchoub

En effet, très intéressant !! J'avoue avoir du mal avec les in

Je suis maintenant en train de faire une fonction décrite comme suit (elle est un peu plus compliquée que les autres, enfin pour moi!):

getrandom : ’e mset -> ’e, qui rend un élément pris au hasard dans le multi-ensemble (en
tenant compte des répétitions : un élément présent 3 fois aura une probabilité d’être choisi 3 fois
supérieure à celle d’un élément présent 1 seule fois). On pourra utiliser la fonction Random.int
k qui donne un entier compris entre 0 et k-1.
On pourra définir une fonction get : int -> ’e mset -> ’e, où (get n s) donne le neme
élément de s. La fonction get a pour précondition que le multi-ensemble n’a pas plus de n
éléments, mais ne fait aucune hypothèse sur quelque ordre que ce soit du multi-ensemble, il
s’agit juste du parcours d’une représentation possible du multi-ensemble.

Je n'ai pas saisi la fonction get. Prenons un exemple:

me = {3,4,6,3,6,6} peut-être défini en:
- let me = Cons((3,2), Cons((4,1), Cons((6,3), Nil)))
ou
- let me = Cons((6,3), Cons((3,2), Cons((4,1), Nil)))
ou
- let me = Cons((4,1), Cons((6,3), Cons((3,2), Nil))).

Dans la liste {3,4,6,3,6,6}, le3 ème élément est 6. Par contre, avec mes définitions de multi-ensembles ci-dessus, j'ai:
- {3,3,4,6,6,6} -> g 3 me = 4
- {6,6,6,3,3,4} -> g 3 me = 6
- {4,6,6,6,3,3} -> g 3 me = 6

Quelque chose m'échappe...

NB: Les contraintes sont de n'utiliser que les fonctions précédemment définies.

[TchoubiTchoub]

Merci TchoubiTchoub

En effet, très intéressant !! J'avoue avoir du mal avec les in

Comment ça ?

Je n'ai pas saisi la fonction get. Prenons un exemple:

me = {3,4,6,3,6,6} peut-être défini en:
- let me = Cons((3,2), Cons((4,1), Cons((6,3), Nil)))
ou
- let me = Cons((6,3), Cons((3,2), Cons((4,1), Nil)))
ou
- let me = Cons((4,1), Cons((6,3), Cons((3,2), Nil))).

Dans la liste {3,4,6,3,6,6}, le3 ème élément est 6. Par contre, avec mes définitions de multi-ensembles ci-dessus, j'ai:
- {3,3,4,6,6,6} -> g 3 me = 4
- {6,6,6,3,3,4} -> g 3 me = 6
- {4,6,6,6,3,3} -> g 3 me = 6

Quelque chose m'échappe...

C'est normal, non ? Vous comprenez "le troisième élément" comme "le troisième élément différent" donc vous vous attendez à obtenir 6, 4 et 3 respectivement. Or le troisième élément c'est "le troisième élément"

Ce qui correspond à
- {3,3,4,6,6,6} -> g 3 me = 4
- {6,6,6,3,3,4} -> g 3 me = 6
- {4,6,6,6,3,3} -> g 3 me = 6

[alexpand]

Comment ça ?

Promis, je reviens vers vous pour plus d'explications mais pour l'instant, je suis concentré sur la fonction get

C'est normal, non ? Vous comprenez "le troisième élément" comme "le troisième élément différent" donc vous vous attendez à obtenir 6, 4 et 3 respectivement. Or le troisième élément c'est "le troisième élément"

Ce qui correspond à
- {3,3,4,6,6,6} -> g 3 me = 4
- {6,6,6,3,3,4} -> g 3 me = 6
- {4,6,6,6,3,3} -> g 3 me = 6

Non, j'ai donné dans mes exemples que je prenais bien le 3ème élément pas forcément différent.

[alexpand]

Hahaha ! Etrange, quand-même. Vous aviez testé votre code avec l'interpréteur en mode Tuareg sous emacs ? (je pose la question car parfois Tuareg part dans les platanes et il vaut mieux redémarrer l'éditeur )

Bon courage pour votre examen

J'ai utilisé la version online sur le site http://tinyurl.com/ocamltop
Par contre, impossible de faire des copier/coller donc j'ai cherché comment l'installer sur mon PC et maintenant, c'est bon !

Du coup, j'ai toutes mes fonctions dans un fichier et même si je sors d'Ocaml, je peux recharger facilement mes fonctions