Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001179OCamlOCaml generalpublic2002-06-02 21:572013-08-31 12:46
Reporteradministrator 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityalways
StatusclosedResolutionwon't fix 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0001179: Feature wish: sentinelle pour bloquer hash
DescriptionBonjour,

la fonction générique Hashtbl.hash est bien pratique sur des structures
imbriquées (avec termes, listes, records, tableaux, ...). Le problème,
c'est que dès que l'une des informations aux "feuilles" n'est plus
hashable (par exemple parce que l'on manipule des structures récursives,
ou que l'on veut fournir sa propre fonction de hash pour un bloc Caml), on
ne peut plus du tout l'utiliser (donc bye bye par exemple la version non
fonctorielle de Hashtbl) et il faut dérouler des lignes de code:
c'est pénible et on perd en performance.

Ce serait bien de pouvoir implémenter un module M de signature:

type 'a t
val lift: int -> 'a -> 'a t
val value: 'a t -> 'a

tel que:
 Hashtbl.hash (M.lift n x) = n
 M.value (M.lift x) = x


Je vois deux methodes assez simples qui permettrait de faire ça:
1) introduire un nouveau tag de bloc Fixedhash_tag et faire que la
   fonction hash ne regarde que le premier objet de ces blocs
2) sans nouveau tag: allouer un bloc global "sentinelle" bidon, de taille
   1, et sortir de la boucle:
     while (i != 0) {
        i--;
        hash_aux(Field(obj, i));
      }
  (dans byterun/hash.c) dès que l'on tombe dessus


Le 2) est très peu intrusif, ne devrait pas être trop pénalisant dans le
cas général, et permettrait au programmeur d'écrire des choses comme:

type t = { ... ; sentinel : Sentinel.t ; ... }

pour séparer ce qui est hashable de ce qui ne l'est pas.


Bon, c'est de la cuisine, mais je trouve que ça serait vraiment très
pratique (et léger à implémenter).


-- Alain

TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0006757)
doligez (administrator)
2012-01-20 14:40

You can do it by wrapping your data inside an object: in that case, the hash function uses the object's ID and never looks inside the object itself.

- Issue History
Date Modified Username Field Change
2005-11-18 10:13 administrator New Issue
2012-01-20 14:40 doligez Note Added: 0006757
2012-01-20 14:40 doligez Status acknowledged => resolved
2012-01-20 14:40 doligez Resolution open => won't fix
2012-01-20 14:40 doligez Description Updated View Revisions
2013-08-31 12:46 xleroy Status resolved => closed


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker