[MLton] Re: [MLton-commit] r6352

[Vesa Karvonen]

On Jan 24, 2008 10:33 PM, Matthew Fluet <fluet at mlton.org> wrote:
> Added a primitive (structural) polymorphic hash.
> On objects with identity (array,ref,etc.), it returns a constant.
> (This matches the behavior of MoscowML's Polyhash.hash function.)

Interesting!  This touches something that I've been thinking about
recently.  I think that SML's arrays and refs (anything with identity)
should include a hash value.  Without it (or something else that
allows efficient discrimination), there just isn't any way to create
an efficient mapping with objects with identity as the domain.  I've
been thinking about redefining all array types in my extended basis
library to include a generated hash value with the array.  With arrays
it would probably be possible to do it without having to change any
client programs (as long as all parts of the program are compiled
against the extended basis).  Assuming that a program doesn't call the
hash function on arrays, a compiler like MLton could probably drop the
hash field from the wrapped array objects, so there would likely be no
performance penalty for programs don't use the feature (and the
penalty would likely be fairly small anyway).  Unfortunately, refs
can't be redefined in a library, so a language/basis library solution
would be better.

> We could do better on objects with identity (e.g., gensym a hash value
> at birth points and flow to the hashing function), but this suffices
> for my immediate purposes.
[...]

I'd love to have that feature in SML (generated hash value for objects
with identity).  I find it both theoretically and practically
important.  MLton should show the way here! :-)

Note that what I'm talking about would only be for arrays and refs
(i.e. objects with identity).  Values without identity can already be
hashed (even if it requires some work) within the existing language.

-Vesa Karvonen