On Thu, May 30, 2002 at 05:01:32AM +1000, John Max Skaller wrote:
> 
> [The replace semantics you describe are unfortunate for me: my unification
> algorithm keeps a hashtable of variable -> term bindings into which
> I have to incrementally subtitute while iterating through the table.

Do you need to maintain *several* such substitutions (i.e. tables) with
the same domain (i.e. the same set of variables)? If not (that is, if
you only have one hash table), then it is customary to use a mutable
field, within each variable record, to store the associated term. It's
simpler and the overhead for access is very small.

One nice way of doing so is to use a generic union/find algorithm, such
as the one I am attaching to this message. Simply define

  type term =
    descriptor UnionFind.point

  and descriptor =
  | TInteger
  | TArrow of term * term
  | ...

and you're all set.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/