Discussion :

[rhnk17]

Bonjour,


Je veux implémenter une fonction "compare" qui algorithmiquement a besoin de regarder des ensembles dont les éléments ont le type t pour pouvoir comparer deux éléments de type t. Pour être bien propre, j'aurai voulu tout coder avec des ensembles (module d'arrivée de Set.Make), mais pour cela, il faudrait pouvoir définir en même temps monn module S et la fonction compare, et je vois pas trop comment c'est possible. Pour l'instant, j'ai une solution qui n'est pas très satisfaisante: à partir de deux éléments de type type, je construis des listes dans ma fonction compare, et je définis ensuite le module Ensemble.

Est-ce qu'on peut faire mieux ?

[alex_pi]

Je veux implémenter une fonction "compare" qui algorithmiquement a besoin de regarder des ensembles dont les éléments ont le type t pour pouvoir comparer deux éléments de type t.

http://caml.inria.fr/pub/docs/manual...021.html#toc75

[rhnk17]

Citation:
Envoyé par rhnk17:
Je veux implémenter une fonction "compare" qui algorithmiquement a besoin de regarder des ensembles dont les éléments ont le type t pour pouvoir comparer deux éléments de type t.
http://caml.inria.fr/pub/docs/manual...021.html#toc75

merci !

[rhnk17]

en fait, ça marche pas car je suis obligé de construire des ensembles
dans le module A pour définir la fonction compare...

[gasche]

Tu peux essayer d'implémenter les ensembles par une table de hachage : au lieu d'un 'a Set.t, tu utilises une ('a, unit) Hashtbl.t : pour ajouter un élément dans l'ensemble tu le mets comme clé avec la valeur (), et tu peux utiliser Hashtbl.mem pour tester l'appartenance.

Ça permet d'utiliser une fonction de hachage (générique par défaut, mais tu peux en écrire une toi-même en utilisant l'interface fonctorielle) au lieu d'une fonction de comparaison, ce qui est pratique si tu ne peux pas encore utiliser compare.

[rhnk17]

bon, finalement, problème contourné dans mon cas:
J'avais des ensembles de termes (d'arbres), et pour comparer les termes je teste (entre autres si l'un est sous-arbre de l'autre, et je dois aussi fournir une fonction sub qui rend l'ensemble des sous-arbres. Pour démêler ça:
- j'ai en plus défini une fonction is_sub qui rend un booléen et qui est appelée par compare- je défini la fonction sub ensuite
- j'étends le module d'ensembles ensuite (trick vue sur sur ce forum et dans une doc ocaml
ça donne

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
module A : TYPEA
struct...
  is_ sub
  compare
  module S = Set.Make(...)
  sub
end
 
module TS = functor ( T : TYPEA) ->
struct
 
  include T.S
  (mes autres fonctions)
end

Ocaml se débrouille bien pour voir que les types de T.S et de TS sont les mêmes...

Merci aussi pour le coup des fonctions de hachage, j'essayerai une autre fois...