Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature wish: sentinelle pour bloquer hash #3368

Closed
vicuna opened this issue Jun 2, 2002 · 1 comment
Closed

Feature wish: sentinelle pour bloquer hash #3368

vicuna opened this issue Jun 2, 2002 · 1 comment

Comments

@vicuna
Copy link

vicuna commented Jun 2, 2002

Original bug ID: 1179
Reporter: administrator
Status: closed (set by @xavierleroy on 2013-08-31T10:46:04Z)
Resolution: won't fix
Priority: normal
Severity: feature
Category: ~DO NOT USE (was: OCaml general)

Bug description

Bonjour,

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

@vicuna
Copy link
Author

vicuna commented Jan 20, 2012

Comment author: @damiendoligez

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant