[Top][All Lists]

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

Re: [Axiom-developer] Set Any and SXHASH

From: Waldek Hebisch
Subject: Re: [Axiom-developer] Set Any and SXHASH
Date: Thu, 5 Apr 2007 15:37:04 +0200 (CEST)

> In
> '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
> 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.

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.
> 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
                              Waldek Hebisch

reply via email to

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