0001179: Feature wish: sentinelle pour bloquer hash

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0001179

OCaml

OCaml general

public

2002-06-02 21:57

2012-01-20 14:40

Reporter

administrator

Assigned To

Priority

normal

Severity

feature

Reproducibility

always

Status

resolved

Resolution

won't fix

Platform

OS Version

Product Version

Target Version

Fixed in Version

Summary

0001179: Feature wish: sentinelle pour bloquer hash

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

Tags

No tags attached.

Attached Files

Relationships

Notes
(0006757) doligez (manager) 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