Re: [Caml-list] Labelling trees

[skaller <skaller@users.sourceforge.net>]

On Thu, 2007-06-07 at 16:26 +0200, Till Varoquaux wrote:

> Hashtbl don't require ordering they require hashing.

True, but the hash required would be unstable.

>  Anyways I'm
> pretty sure both the functions `Pervasives.compare` and `Hashtbl.hash`
> actually work on the representation of the data,

Yes, which is why you can't use them. The idea is:

	map1: address1 -> AST
	map2: address1 -> decoration

where address1 is the address of the AST term. map1 is just the
function:

	let id x = x

map2 can be an association list, searching by address.

Hashing or comparing using the value of a term as a key
is no good. It's too slow.

> > Double indirection works though: instead of terms, use an integer
> > which Maps to a term .. you can then also Map the integer to
> > your type. Of course .. this isn't statically safe.
> 
> Huh????

The Felix compiler maps like:

	int -> term
	int -> decoration

This isn't statically safe. There's no assurance of a 1-1 correspondence
between terms and decorations.

The encoding is safe .. the semantics aren't. I use Hashtbl for this
and I get 'Not_found' exception regularly. Correctness here depends
on control flow -- dynamically maintaining the correspondence.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net