Discussion :

[magodeoz]

Bonjour à tous,
J'ai quelques soucis en ocaml avec une fonction....
Tout d'abord je dois créer une fonction cardinal et on m'impose:
type 'e ensemble = NIL | Cons of 'e * 'e ensemble;;
let ensemblevide = NIL;;

puis une fonction cardinalmultiens et on m'impose:
type 'e multielt = 'e*int ;;
type 'e multiens = VIDE | Add of 'e multielt * 'e multiens ;;


Donc pour ça pas de problème:
cardinal:
Spécification : cardinal 'e ensemble->int
Sémantique : calcule le nombre d'éléments d'un ensemble

Code :

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

1
2
3
4
let rec cardinal (x : 'e ensemble) : int =
  match x with |Cons (a, ensemble2)->1+cardinal(ensemble2)
               |ensemblevide -> 0
;;

et pour cardinalmultiens:
Profil :cardinalmultiens :'e multiens -> int * int
Sémentique : calcule le nombre de multi-elements et le nombre d'occurences total

Code :

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

1
2
3
4
let rec cardinalmultiens(e : 'e multiens) : int*int =
  match e with |Add((_,x),suite) -> let (a,b) = cardinalmultiens(suite) in (a+1, x + b)
               |multivide -> (0,0)
;;

Le problème c'est qu'après on me demande de refaire cela en utilisant la notation usuelle de ocaml pour les listes.
Donc pour cardinal:

Code :

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

1
2
3
4
5
6
 let rec cardinal (x:'a list) :int=
  match x with
  |a::b->1+cardinal (b)
  |ensemblevide->0;;
 
 "

Pourriez-vous m'aider pour cardinalmultiens...?

D'avance je vous remercie,
Cordialement,
PRG

[prgasp77]

Bonjour,

La première étape est de définir l'équivalent du type multiens en utilisant des listes. Quel est-il ?

Une fois cela fait, si la résolution de ton problème n'est pas immédiate, dis nous ce qui te pose problème .

Dernier point, j'imagine que tu fais tout cela dans un but d'apprentissage, sois à l'école soit en autodidacte. C'est pourquoi je peux te proposer d'aller un peu plus loin. Sais-tu ce qu'est la récursivité terminale ? De plus, connais tu la notation let f = function 0 -> 1 | _ -> 0 ?

Cordialement,

[magodeoz]

Merci de ta réponse prgasp.
Ah d'accord

définir l'équivalent du type multiens en utilisant des listes.

C'était ça mon problème redéfinir le type multiens.
type multiens= []|int* 'a list non?
Je pensais pouvoir m'en sortir comme avec cardinal en faisant du genre:
let rec cardinalmultiens (l : 'a list):int*int


et que par exemple pour une liste [1;1;2;2;3;4] la fonction renvoit (2,1) (2,2) (1,3) (1,4)

Pour ce qui est de la notation

let f = function 0 -> 1 | _ -> 0

je ne l'ai pas vu comme ça mais si je comprends bien 0 renverra 1 et toutes autres valeurs 0.

[magodeoz]

Je crois que j'ai trouvé!

Code :

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

1
2
3
4
let rec cardinalmultiens (l: 'a list):int*int=
  match l with
  |(_,b)::suite -> let (x,y)=cardinalmultiens(suite) in (x+1,b+y)
  |[] -> (0,0);;

c'est bon ça non? ça me met:
val cardinalmultiens : ('a * int) list -> int * int = <fun>

Vous pourriez m'expliquer comment je teste avec un exemple par contre....?
Je tape cardinalmultiens [(2,1);(3,2);(4,3)];; comme exemple et ça ne fonctionne pas....

[prgasp77]

Étrange ... Chez moi :

Code :

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

1
2
3
4
5
6
7
# let rec cardinalmultiens (l: 'a list):int*int=
  match l with
  |(_,b)::suite -> let (x,y)=cardinalmultiens(suite) in (x+1,b+y)
  |[] -> (0,0);;      
val cardinalmultiens : ('a * int) list -> int * int = <fun>
# cardinalmultiens [(2,1);(3,2);(4,3)];;
- : int * int = (3, 6)

Ce qui est la réponse attendue.

Mais peut être peux-tu fournir un code un peu plus propre en définissant explicitement les type multielt et multiens. Et tu n'as pas répondu à ma question concernant la récursion terminale.
Quant à la notation liée au mot clé function, oui tu as effectivement raison (on y reviendra plus tard ).

[magodeoz]

En fait j'ai objectif caml sur mon windows et ce n'est pas très stable...Le programme bug assez souvent...et je n'ai pas vraiment envie de mettre du ubuntu sur mon pc...
Finalement l'exemple a marché ^^

Bon la récursivité terminale, si c'est sous la forme de let in disons que je l'ai survolé.... Plus de facilité à écrire par exemple:

Code :

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

1
2
3
let rec factorielle n = match n with
      0 -> 1
    | _ -> n * factorielle (n-1)

plutôt que

Code :

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

1
2
3
4
5
let factorielle n =
    let rec auxiliaire resultat = function
        0 -> resultat
      | n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n

peux-tu fournir un code un peu plus propre en définissant explicitement les type multielt et multiens

multielt, ça reste un 'a*int non? et multiens une liste de 'a*int ?

[SpiceGuid]

En fait j'ai objectif caml sur mon windows et ce n'est pas très stable...Le programme bug assez souvent...

OCamlWinPlus

[magodeoz]

merci du conseil. :-)
Petite question, à la fac on utilise emacs, est-il possible de l'avoir sur Windows (j'ai cherché partout...rien trouvé) ou n'existe-t-il que sous linux ou unix?

[prgasp77]

Bon la récursivité terminale, si c'est sous la forme de let in disons que je l'ai survolé.... Plus de facilité à écrire par exemple:

Code :

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

1
2
3
let rec factorielle n = match n with
      0 -> 1
    | _ -> n * factorielle (n-1)

plutôt que

Code :

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

1
2
3
4
5
let factorielle n =
    let rec auxiliaire resultat = function
        0 -> resultat
      | n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n

La récursivité terminale est bien plus qu'une convention d'écriture. C'est une forme de récursivité qui permet à un compilateur digne de ce nom d'effectuer une importante optimisation qui rendra la fonction toujours utilisable avec de grandes entrées (une liste de plusieurs milliers d'éléments par exemple).

Pour faire simple, une fonction récursive est tail-rec si elle retourne soit une constante soit la valeur de retour, telle quelle, d'un appel récursif à elle-même (ou plus générallement, à une fonction tail-rec).

Par exemple, pour ta fonction cardinal qui à une liste retourne sa longueur, plutôt que d'ajouter 1 au cardinal de la queue, si tu envoies ce 1 en tant qu'argument, qui s'accumulerait, alors tu aurais une fonction terminale récursive :

Code OCaml :

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

1
2
3
4
5
6
7
let cardinal =
   let rec aux acc = function
   | [] -> acc
   | _ :: tl -> aux (succ acc) tl
   in
   aux 0

On peut ici voir que la fonction aux retourne soit une constante (acc) soit un appel non modifié/traité à elle même. Afin de bien comprendre le fonctionnement de la fonction aux, amuse toi à tracer ses appels sur de petites listes (2 ou 3 éléments).

multielt, ça reste un 'a*int non? et multiens une liste de 'a*int ?

Pas tout à fait,

Code OCaml :

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

type 'a multielt = 'a * int

Et qu'en est-il pour 'a multiens ?

merci du conseil. :-)
Petite question, à la fac on utilise emacs, est-il possible de l'avoir sur Windows (j'ai cherché partout...rien trouvé) ou n'existe-t-il que sous linux ou unix?

Partout ... sauf sur google Voir ici (en bas de page).

[magodeoz]

Je crois que la récursion terminale c'est encore un peu trop compliqué pour moi ^^

type 'a multielt = 'a * int
type 'a multiens= []| 'a multiens of 'a multielt ?

Merci pour le lien :-) Je vais voir quelle version télécharger :-)

[magodeoz]

prgasp, pourrais-tu m'aider pour cette fonction.... Même problème que pour la précèdente, je m'en sors avec le "Add of mais pas sans...

occurencemultiens : 'e multiens -> int
Sémentique : renvoit le nombre d'occurence de l'élément dans le multiens

Code :

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

1
2
3
4
let rec occurencemultiens(e : 'e)(multie : 'e multiens) : int =
	match multie with |Add((a,x),suite) -> if (a=e)then x else occurencemultiens (e) (suite)
                          |multivide -> 0	
;;

J'ai tenté:

Code :

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

1
2
3
4
 let rec occurrence (a :’a)(l :’a list) :int=
match l with
|(b,x)::suite->if (b=a) then x else occurrence (a)(suite)
|[]->0;;

et ça me met: This expression has type 'a * 'b but is here used with type 'a

[prgasp77]

Bon alors déjà tu n'as pas encore bien saisi ce qu'était ton type multiens. Sémantiquement, qu'est-il ? Tu ne parviendra à rien avant de régler ça .

Ensuite à propos du calcul du nombre d’occurrence, même avec ton premier type (Add etc), tu n'y parviens pas. Mais je commence à avoir des doutes sur l'énoncé lui même. Tu devrais le copier/coller afin qu'on soit sûr.

[magodeoz]

Voila je vous ai envoyé le sujet en pièce jointe. D'après le professeur, Partie 1 et 2, il n'y a pas d'erreurs dans ce que j'ai fait .J'ai réussi jusqu'au début de la partie 3. J'ai fait estvidemultiens et cardinalmultiens en utilisant la notation usuelle de Ocaml pour les listes.

tu n'as pas encore bien saisi ce qu'était ton type multiens. Sémantiquement, qu'est-il ? Tu ne parviendra à rien avant de régler ça .

multiens c'est bien une liste de 'a multielt non...?

[magodeoz]

type multiens= 'a multielt list non?

[Ptival]

Code :

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

1
2
3
4
5
 
let rec occurencemultiens (e : 'e) (multie : 'e multiens) : int =
	match multie with
	| Add((a,x),suite) -> if a = e then x else occurencemultiens e suite
	| multivide -> 0

Attention, ce second motif ne fait pas ce que tu penses !
Quand, dans un motif, tu met un mot en minuscule, OCaml le prend comme un motif qui accepte n'importe quoi, et lui donne le nom que tu as écrit.
Pour filtrer le multi-ensemble vide, tu dois utiliser les constructeurs du type multiens : Add, et VIDE. Ainsi, cela donne :

Code :

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

1
2
3
4
5
 
let rec occurencemultiens (e : 'e) (multie : 'e multiens) : int =
	match multie with
	| Add((a,x),suite) -> if a = e then x else occurencemultiens e suite
	| VIDE -> 0

Sinon, cela me semble correct. Passons maintenant à la version listes :

Code :

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

1
2
3
4
5
 
let rec occurrence (a :’a) (l :’a list) : int =
match l with
|(b,x)::suite-> if b = a then x else occurrence a suite
|[] -> 0

Ton erreur est dans la signature donnée : tu déclares prendre une liste de "n'importe quoi", mais dans ton code, tu l'utilises comme une liste de paires d'un "n'importe quoi" et d'un int.

Ce que tu veux, c'est juste corriger ta signature :

Code :

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

1
2
3
4
5
 
let rec occurrence (a : 'a) (l : 'a multilelt list) : int =
match l with
|(b,x)::suite-> if b = a then x else occurrence a suite
|[] -> 0

Effectivement, si tu définis type 'a multiens= 'a multielt list, tu peux même écrire (l : 'a multiens).

[magodeoz]

Merci beaucoup de ta réponse Ptival!

En fait le multivide c'était un ensemble que j'avais défini:
let multivide = VIDE ;;

Et donc pour la version liste:

Code :

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

type 'a multielt = 'a * int ;;

Code :

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

type 'a multiens= 'a multielt list ;;

Code :

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

1
2
3
4
let rec occurrence (a : 'a) (l : 'a multiens) : int =
match l with
|(b,x)::suite-> if b = a then x else occurrence a suite
|[] -> 0 ;;

Bon je vais essayer la fonction suivante sans me planter cette fois...

Petite question pourquoi dans le type on doit mettre 'a avant multiens? Je croyais que juste après "type" on mettait simplement le nom du type voulu or

Code :

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

type multiens= 'a multielt list ;;

ne fonctionne pas.

[Ptival]

En fait le multivide c'était un ensemble que j'avais défini:
let multivide = VIDE ;;

Certes, mais cela n'implique pas que l'on peut remplacer toute occurence de VIDE par multivide, et c'est en particulier faux dans l'endroit où tu l'as fait.

Le motif :

Code :

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

| VIDE -> ...

ne filtre que le multi-ensemble vide.

Alors que le motif :

Code :

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

| multivide -> ...

filtre n'importe quel truc, et le nomme "multivide" dans le code à droite de la flèche.

En particulier, si tu avais écrit :

Code :

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

1
2
3
4
 
let foo = function
| multivide -> ...
| ADD(_, _) -> ...

Alors OCaml t'aurais indiqué que le deuxième motif n'est pas accessible. En effet, le premier motif accepte tout !

---

Petite question pourquoi dans le type on doit mettre 'a avant multiens? Je croyais que juste après "type" on mettait simplement le nom du type voulu or

Code :

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

type multiens= 'a multielt list ;;

ne fonctionne pas.

Ton type est paramétré par un 'a. En OCaml, les paramètres du type doivent apparaître à gauche de la déclaration de type :

Code :

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

type 'a list = nil |cons of 'a * 'a list

Après tout, tu es en train de définir ce qu'est une "liste de 'a", et pas une "liste". :-) (oui, pas très convaincant comme argument...)
Il y a d'autres fonctionnalités du système de types qui font qu'on veut écrire à gauche du "égal" les types qui sont des paramètres.

[magodeoz]

Merci pour ces infos, j'ai bien compris à présent :-)

J'ai réussi à mettre toutes les autres fonctions sous la forme liste....sauf une
La dernière....
J'ai:

Code :

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

1
2
3
4
5
6
let rec unionmultiens(multie1 : 'a multiens)(multie2 : 'a multiens) : 'a multiens =
  match (multie1,multie2) with |(((b,x):: suite),(c,y)::suite') -> ajoutemultiens(b,x)(ajoutemultiens(c,y)(unionmultiens suite suite'))
                               |([], ((c,y)::suite')) -> ajoutemultiens (c,y)(unionmultiens([])(suite'))
		               |(((b,x)::suite), []) -> ajoutemultiens (b,x)(unionmultiens(suite)([]))
		               |([],[]) -> []
;;

Code :

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

1
2
3
4
5
let rec intersectionmultiens(multie1 : 'a multiens)(multie2 : 'a multiens) : 'a multiens =
	match multie1 with |((b,x)::suite) -> let y = occurencemultiens (b) (multie2) in if (y>0) then ((b,min(x)(y)):: intersectionmultiens(suite)(multie2))
                                                                                                    else intersectionmultiens (suite)(multie2)
	                   |[] -> []
;;

Code :

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

1
2
3
4
let rec differencemultiens(multie1 : 'a multiens)(multie2 : 'a multiens) : 'a multiens =
	match multie2 with  |((b,x)::suite) -> supprimemultiens(b,x)(differencemultiens(multie1)(suite))
		                     |[] -> []
;;

Donc pas de problème avec ces 3 fonctions mais après pour celle-ci:

Code :

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

1
2
let differencesymetriquemultiens(multie1 : 'a multiens)(multie2 : 'a multiens) : 'a multiens = differencemultiens(unionmultiens(multie1)(multie2))(intersectionmultiens (multie1)(multie2))
;;

ça me marche pas.... Problème de parenthèsage comme message d'erreur mais je ne vois pas du tout pourquoi....

[Ptival]

Hmmm... je ne vois pas d'erreur de parenthésage que pourrait te signaler le compilateur dans ce cas.

Par contre, une remarque d'ordre plus générale, tu mets beaucoup de parenthèses superflues !

Si tu veux passer des arguments a, b, c à une fonction f, on n'écrit en général pas :

Code :

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

f(a)(b)(c)

comme tu as tendance à le faire, mais simplement :

Code :

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

f a b c

On ne se met à utiliser des parenthèses que pour regrouper une expression complexe afin qu'elle ne soit qu'un argument :

Code :

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

f a (b + 1) c

Code :

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

f a (g b) c

Ainsi quand tu écris :

Code :

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

differencemultiens(unionmultiens(multie1)(multie2))(intersectionmultiens (multie1)(multie2))

On n'écrit généralement seulement :

Code :

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

differencemultiens (unionmultiens multie1 multie2) (intersectionmultiens multie1 multie2)

Pour ce qui est de ton erreur, je ne la vois pas. Si tu me postes le message d'erreur exact, avec les indications de la localisation de l'erreur, alors je pourrais faire l'effort d'y réfléchir. Sinon, pas envie.

[magodeoz]

ça a finalement marché! :-)

J'en avais une de trop à la fin ^^Elle était confondue avec la fin de la fenêtre...Je sais pas si c'est clair mais l'idée c'est ça

Code :

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

differencemultiens (unionmultiens multie1 multie2) (intersectionmultiens multie1 multie2)

Ah oui en effet....Merci beaucoup. Plus lisible et ça m'empêchera les erreurs de parenthèses....
Pour la suite du travail,j'avoue avoir énormément de mal....Je dois refaire les fonctions cardinal;cardinalmultiens,inclus,inclusmultiens,union,unionmultiens, intersection et intersectionmultiens en utilisant fold....
Pour commencer, cardinal:
J'avais:
|Spécification : cardinal 'e ensemble->int
|Sémantique : calcule le nombre d'éléments d'un ensemble

Code :

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

1
2
3
4
let rec cardinal (x : 'e ensemble) : int =
  match x with |Cons (a, ensemble2)->1+cardinal(ensemble2)
               |ensemblevide -> 0
;;

Je peux laisser ensemble vide dans le match dans ce cas là ou comme pour la fonction précèdente je dois mettre VIDE?
(on ne m'avait pas demandé dans le début de la partie 3 de mettre sous forme de liste les fonctions partie 1....) Mais sinon ça fait:

Code :

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

1
2
3
4
5
let rec cardinal (l:'a list):int=
match l with 
|a::suite->1+cardinal(suite)
|[]->0 
;;

Donc je connais fold_left:

Code :

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

1
2
3
4
let rec fold_left (f: 'a -> 'b ->'a) (acc: 'a) (l: 'b list): 'a =
  match l with
    [] -> acc
  | x::xs -> fold_left f (f acc x) xs ;;

Mais alors après.... Je n'y comprends pas grand chose...Je ne vois pas du tout comment utiliser fold-left.

D'avance merci...,
Magodeoz