🚀 go-pugleaf

>>>>> In article <26470@boulder.Colorado.EDU>, dennis@boulder.Colorado.EDU (Dennis Heimbigner) writes:
Sorry for the long citation but it is needed for better understanding:

Dennis> I have only recently begun to look at SML and I am curious
Dennis> as to the best method for representing functions that are
Dennis> defined by specifying a set of pairs of values, where the set contents
Dennis> varies over time.  This is more-or-less analogous to prolog assert/retract
Dennis> or to functional data base model base functions.

Dennis> For example, I want to associate the set of pairs:
Dennis> 	(1,2)
Dennis> 	(17,9)
Dennis> 	(23,-1)
Dennis> with the function f, such that e.g, f(17) = 9, and so on.
Dennis> Then I want to be able to change this set by replacing some
Dennis> pairs and have the function f reflect these changes.

Dennis> The only way I can see to do this in SML is to
Dennis> associate a variable, f_var, with f such that f_var
Dennis> contains the set of pairs.  Modifying the set then
Dennis> consists of reconstructing the set and re-storing it into
Dennis> the variable.
This could be *one* way. But, since SML is a *functional* language, try
the following (the input follows the '-', SML output the '>'), the following
functions were written using "Standard ML of New Jersey, Version 0.56":

- exception unbound;   (* needed for undefined values *)
> exception unbound

- fun update f (x, y) = fn n => if (n = x) then y else f (n);
> val update = fn : (''a -> 'b) -> ''a * 'b -> ''a -> 'b
                       (* this function updates f with the new pair (x, y) *)

- fun raise_unbound x = raise unbound;
> val raise_unbound = fn : 'a -> 'b
                       (* The first update uses this function *)

- val f = update raise_unbound (1, 2);
> val f = fn : int -> int
                       (* the first pair *)

- val f = update f (17, 9);
> val f = fn : int -> int
                       (* the next one *)

- val f = update f (23, ~1);
> val f = fn : int -> int
                       (* and so on *)

 (* now the application of f *)
- f(17);
> val it = 9 : int

- f(23);
> val it = ~1 : int

- f(3);
> uncaught exception unbound

Hope this helps.
--
>>>>>>>>>> Robert Stabl <<<>>> stabl@unipas.fmi.uni-passau.de <<<<<<<<<<

> 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