[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 |
In http://wiki.axiom-developer.org/347BugInMapSet
'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)
test(C=B)
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
http://wiki.axiom-developer.org/axiom--test--1/src/algebra/SetsSpad
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:
http://wiki.axiom-developer.org/SandBoxSetAny
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:
http://www.lisp.org/HyperSpec/Body/fun_sxhash.html#sxhash
says:
"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?
Regards,
Bill Page.
- [Axiom-developer] Set Any and SXHASH,
Bill Page <=
- Re: [Axiom-developer] Set Any and SXHASH, Waldek Hebisch, 2007/04/05
- RE: [Axiom-developer] Set Any and SXHASH, Bill Page, 2007/04/05
- Re: [Axiom-developer] Set Any and SXHASH, Waldek Hebisch, 2007/04/05
- RE: [Axiom-developer] Set Any and SXHASH, Bill Page, 2007/04/05
- Re: [Axiom-developer] Set Any and SXHASH, Waldek Hebisch, 2007/04/05
- RE: [Axiom-developer] Set Any and SXHASH, Bill Page, 2007/04/05
- Re: [Axiom-developer] Set Any and SXHASH, Waldek Hebisch, 2007/04/06
- RE: [Axiom-developer] Set Any and SXHASH, Bill Page, 2007/04/06
- Re: [Axiom-developer] Set Any and SXHASH, Martin Rubey, 2007/04/06