Path: utzoo!attcan!uunet!know!samsung!zaphod.mps.ohio-state.edu!sdd.hp.com!hplabs!otter.hpl.hp.com!otter!der
From: der@otter.hpl.hp.com (Dave Reynolds)
Newsgroups: comp.lang.functional
Subject: Re: Extensional functions in SML?
Message-ID: <33330002@otter.hpl.hp.com>
Date: 2 Oct 90 08:46:12 GMT
References: <26470@boulder.Colorado.EDU>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 39

> Apologies for my ignorance about ML, but I'm curious: can you define a
> generic hash function in ML?  (i.e. a function which can take a argument
> of *any* type (on which equality is defined), and map it (in some plausible
> way) onto a range of integers.)  If so, how?

No, there doesn't seem to be any satisfying way of doing this.  There is
certainly no built in hashing scheme as found in prolog, smalltalk etc.  Not
least amongst your problems is that there are no generic functions just
polymorphic functions, not even user overloading.

In pactice this is not so great a problem since you can't have inhomogeneous
collections either!  This means that for a given hash map you can only insert
elements of the same type and only need a monomorphic hash function.

In our local library we have a run time description (called a 'typeSpec') for
each type we are interested in, which contains (amongst other things) a hash
function.  When you create an instance of a hash map you bind into the map a
'typeSpec' for the domain of the map.  Then all the hash map functions are
polymorphic on the domain of the map and rely on the typeSpec supplied as
part of the map datastructure to provide little things like the hashing
function.  This works reasonably well for built in types and a few 'standard'
constructed types but it is an annoying overhead to have to define a
'typeSpec' for each user type you might want to use as a map domain.

All the hash mapping schemes we have experimented with in ML have suffered
from the following limitations:
  (1) Only homogeneous collections/maps.
  (2) Inefficient unless you use an exposed imperative implementation.
  (3) Lack of general hashing function.

Whilst (3) is annoying I've typically found it to be the least of my worries.

Dave

------------------------------------------------------------------
Dave Reynolds                   | Phone: (0272) 799910 x 24165
Hewlett-Packard Laboratories	| der@hplb.lb.hp.co.uk   - UKnet
Filton Road, Stoke Gifford      | der@hplb.hpl.hp.com    - Internet
Bristol BS12 6QZ, ENGLAND       | Dave Reynolds/HPC600/UX - HPDesk