[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Axiom-developer] Set Any and SXHASH

From: Bill Page
Subject: [Axiom-developer] Set Any and SXHASH
Date: Wed, 4 Apr 2007 17:24:02 -0400


'oklhazi' reported that "map confuses sets" and gives
the example

  A:=set [-2,-1,0]
  B:=set [0,1,4]
  C:=map(x +-> x^2,A)

where the map operation produces a "Set" C with the same
elements as B but which is not equal to B, thus violating
a major axiom of set theory.

The documentation for Set

says, (in part):

++ In our implementation, \Language{} maintains the entries
++ in sorted order.  Specifically, the parts function returns
++ the entries as a list in ascending order and the extract
++ operation returns the maximum entry.

but the example shows that this is not true even if the Set
is composed of elements from a domain which has OrderedSet.
In the #347 I proposed a simple patch to correct this
behaviour but it is easy to show that it still fails if the
element domain is not an OrderedSet.

At the following page:

I have proposed an more ambitious fix that provides a constant
but otherwise arbitrary ordering for all SETs based on comparing
the Lisp SXHASH of the elements:

order(x:S,y:S):Boolean == integer(SXHASH(x)$Lisp)$Sexpression
                          < integer(SXHASH(y)$Lisp)$Sexpression

This provides an easy to compute order but since this is a
hash the ordering is in general only a partial order, so perhaps
this is not such a good idea?

The reference:


"3. The hash-code for an object is always the same within a
single session provided that the object is not visibly modified
with regard to the equivalence test equal.

"4. The hash-code is intended for hashing. This places no
verifiable constraint on a conforming implementation, but the
intent is that an implementation should make a good-faith effort
to produce hash-codes that are well distributed within the
range of non-negative fixnums.


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'?

Also on page SandBoxSetAny I proposed a patch to the code for
the domain Any that makes use of the Lisp EQUAL comparison
instead of EQ. I think that in general EQ is too restrictive.
Do you think this change is reasonable and correct?

Bill Page.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]