RE: [Axiom-developer] Set Any and SXHASH

[Bill Page]

On April 5, 2007 9:37 AM Waldek Hebisch wrote:
> ... 
> I would say that sorting elements of Set is a design bug.
> Namely, without any support form domain specific code it is
> hard to define linear order.  AFAICS in Axiom only domains
> which have OrderedSet are eqipped with linear order.
>

If Set is implemented by sorting the linear order cannot be
domain specific since there certainly are domains from which
we might wish to form finite sets for which no "natural" order
can be defined, e.g. the domain Any. But I think it is always
possible to define some lexical ordering over the members of
all domains For example, the Axiom interpreter contains the
Lisp function LEXGREATERP in

  src/interp/ggreater.lisp.pamphlet

For the implementation of Set using sorting all that is required
is that the ordering be constant within an Axiom session.

See: http://wiki.axiom-developer.org/SandBoxSetAny

> > So my question for Axiom Developers and Lisp aficionados is
> > what is your opinion of the use of SXHASH? How well does SXHASH
> > behave in GCL? What might be a reasonable alternative for
> > defining a total ordering on the elements of a Set given the
> > possibility of the type 'Set Any'?
> >
> 
> Hashing allows reasonably efficient implementation of set
> operations.
>  

Yes, but that would require a complete re-design of Set -
perhaps not a bad idea. Probably the current implementation
could be considered a little lame, but I was just looking for
a simple way to correct the existing bug. Axiom has other
domains that already use hashing such as EqTable so it might
be as easy as just choosing a different representation of the
Set domain.

Regards,
Bill Page.