Original bug ID: 340
Reporter: administrator
Assigned to: @alainfrisch
Status: closed (set by @xavierleroy on 2012-03-24T14:01:47Z)
Resolution: fixed
Priority: normal
Severity: feature
Category: ~DO NOT USE (was: OCaml general)
Has duplicate: #4822
Related to: #2991 #3225 #3501 #8223 #4489
Parent of: #3562 #3730 #3875 #3876

Bug description

Bonjour,

serait-il possible d'implémenter dans Map les mêmes opérations que Set ?
(ça se fait à coup de copier-coller entre les deux modules)

En particulier, il manque:
is_empty
singleton
union, inter, diff, compare, equal, subset (qui prennent en argument
l'opération correspondante sur les données),
for_all
exists
filter
partition
cardinal
elements
min_elt
max_elt
choose

Le plus important pour moi, ce serait compare.

D'autre part, je pense que ce serait utile d'avoir des versions de Map et
Set qui travaillent sur des types ordonnés et hashés et donnent des types
ordonnés et hashés efficacement. Une implementation possible, ce serait
d'utiliser comme valeur de hash pour un ensemble le triplet (cardinal,
somme des valeurs de hash des éléments, produit des valeurs de hash des
éléments), que l'on garde en interne dans la representation de l'ensemble
(ça se met à jour facilement lors de l'ajout d'un élément). On peut
utiliser d'autres fonctions symétriques calculables incrementalement,
comme la somme des cubes,etc... Ça permet aussi de voir rapidemment si
deux ensembles sont différents.

Cordialement,

Alain Frisch