In Issue #347 it is shown that set equality fails after applying
a map to a set:
fricas
A:Set Integer := set [-2,-1,0]
Type: Set(Integer)
fricas
B:Set Integer := set [0,1,4]
Type: Set(Integer)
fricas
C:=map(x +-> x^2,A)
Type: Set(Integer)
fricas
test(C=B)
Type: Boolean
A possible fix is given in #347 for Sets whose members have
OrderedSet.
A More Ambitious Fix
As suggested by the documentation in the code for Set domain,
sets must be sorted based some ordering applicable to all Axiom
object. One such order can be defined by the SXHASH value
(ref).
For example:
order(x:S,y:S):Boolean == integer(SXHASH(x)$Lisp)$SExpression<integer(SXHASH(y)$Lisp)$SExpression
map_!(f,s) ==
map_!(f,s)$Rep
sort_!(order,s)$Rep
removeDuplicates_! s
construct l ==
zero?(n := #l) => empty()
a := new(n, first l)
for i in minIndex(a).. for x in l repeat a.i := x
removeDuplicates_! sort_!(order,a)
although the ordering may fail to be total because of collisions.
A better ordering is given by the lexical ordering function LEXGREATERP
defined in the Axiom interpreter code
ggreater.lisp :
order(x:S,y:S):Boolean == null? LEXGREATERP(a,b)$Lisp
This ordering is compatible with the "natural" ordering in each
domain if the domain has OrderedSet
Modified Domain Set
spad
)abbrev domain SET Set
++ Author: Michael Monagan; revised by Richard Jenks
++ Date Created: August 87 through August 88
++ Date Previously Updated: May 1991
++ Basic Operations:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A set over a domain D models the usual mathematical notion of a finite set
++ of elements from D.
++ Sets are unordered collections of distinct elements
++ (that is, order and duplication does not matter).
++ The notation \spad{set [a,b,c]} can be used to create
++ a set and the usual operations such as union and intersection are available
++ to form new sets.
++ 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.
++ Given two sets s and t where \spad{#s = m} and \spad{#t = n},
++ the complexity of
++ \spad{s = t} is \spad{O(min(n,m))}
++ \spad{s < t} is \spad{O(max(n,m))}
++ \spad{union(s,t)}, \spad{intersect(s,t)}, \spad{minus(s,t)}, \spad{symmetricDifference(s,t)} is \spad{O(max(n,m))}
++ \spad{member(x,t)} is \spad{O(n log n)}
++ \spad{insert(x,t)} and \spad{remove(x,t)} is \spad{O(n)}
Set(S:SetCategory): FiniteSetAggregate S == add
Rep := FlexibleArray(S)
# s == _#$Rep s
brace() == empty()
set() == empty()
empty() == empty()$Rep
copy s == copy(s)$Rep
parts s == parts(s)$Rep
inspect s == (empty? s => error "Empty set"; s(maxIndex s))
extract! s ==
x := inspect s
delete!(s, maxIndex s)
x
find(f, s) == find(f, s)$Rep
map(f, s) == map!(f,copy s)
reduce(f, s) == reduce(f, s)$Rep
reduce(f, s, x) == reduce(f, s, x)$Rep
reduce(f, s, x, y) == reduce(f, s, x, y)$Rep
if S has ConvertibleTo InputForm then
convert(x:%):InputForm ==
convert [convert("set"::Symbol)@InputForm,
convert(parts x)@InputForm]
order(x:S,y:S):Boolean == null?(LEXGREATERP(x,y)$Lisp)$SExpression
-- Not as good?
-- integer(SXHASH(x)$Lisp)$SExpression<integer(SXHASH(y)$Lisp)$SExpression
map!(f, s) ==
map!(f, s)$Rep
sort!(order, s)$Rep
removeDuplicates! s
construct l ==
zero?(n := #l) => empty()
a := new(n, first l)
for i in minIndex(a).. for x in l repeat a.i := x
removeDuplicates! sort!(order, a)
if S has OrderedSet then
s = t == s =$Rep t
max s == inspect s
min s == (empty? s => error "Empty set"; s(minIndex s))
insert!(x, s) ==
n := inc maxIndex s
k := minIndex s
while k < n and x > s.k repeat k := inc k
k < n and s.k = x => s
insert!(x, s, k)
member?(x, s) == -- binary search
empty? s => false
t := maxIndex s
b := minIndex s
while b < t repeat
m := (b+t) quo 2
if x > s.m then b := m+1 else t := m
x = s.t
remove!(x:S, s:%) ==
n := inc maxIndex s
k := minIndex s
while k < n and x > s.k repeat k := inc k
k < n and x = s.k => delete!(s, k)
s
-- the set operations are implemented as variations of merging
intersect(s, t) ==
m := maxIndex s
n := maxIndex t
i := minIndex s
j := minIndex t
r := empty()
while i <= m and j <= n repeat
s.i = t.j => (concat!(r, s.i); i := i+1; j := j+1)
if s.i < t.j then i := i+1 else j := j+1
r
difference(s:%, t:%) ==
m := maxIndex s
n := maxIndex t
i := minIndex s
j := minIndex t
r := empty()
while i <= m and j <= n repeat
s.i = t.j => (i := i+1; j := j+1)
s.i < t.j => (concat!(r, s.i); i := i+1)
j := j+1
while i <= m repeat (concat!(r, s.i); i := i+1)
r
symmetricDifference(s, t) ==
m := maxIndex s
n := maxIndex t
i := minIndex s
j := minIndex t
r := empty()
while i <= m and j <= n repeat
s.i < t.j => (concat!(r, s.i); i := i+1)
s.i > t.j => (concat!(r, t.j); j := j+1)
i := i+1; j := j+1
while i <= m repeat (concat!(r, s.i); i := i+1)
while j <= n repeat (concat!(r, t.j); j := j+1)
r
subset?(s, t) ==
m := maxIndex s
n := maxIndex t
m > n => false
i := minIndex s
j := minIndex t
while i <= m and j <= n repeat
s.i = t.j => (i := i+1; j := j+1)
s.i > t.j => j := j+1
return false
i > m
union(s:%, t:%) ==
m := maxIndex s
n := maxIndex t
i := minIndex s
j := minIndex t
r := empty()
while i <= m and j <= n repeat
s.i = t.j => (concat!(r, s.i); i := i+1; j := j+1)
s.i < t.j => (concat!(r, s.i); i := i+1)
(concat!(r, t.j); j := j+1)
while i <= m repeat (concat!(r, s.i); i := i+1)
while j <= n repeat (concat!(r, t.j); j := j+1)
r
else
insert!(x, s) ==
for k in minIndex s .. maxIndex s repeat
s.k = x => return s
insert!(x, s, inc maxIndex s)
remove!(x:S, s:%) ==
n := inc maxIndex s
k := minIndex s
while k < n repeat
x = s.k => return delete!(s, k)
k := inc k
s
spad
Compiling FriCAS source code from file
/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3506829172687478687-25px002.spad
using old system compiler.
SET abbreviates domain Set
------------------------------------------------------------------------
initializing NRLIB SET for Set
compiling into NRLIB SET
compiling exported # : $ -> NonNegativeInteger
;;; *** |SET;#;$Nni;1| REDEFINED
Time: 0.02 SEC.
compiling exported brace : () -> $
;;; *** |SET;brace;$;2| REDEFINED
Time: 0 SEC.
compiling exported set : () -> $
;;; *** |SET;set;$;3| REDEFINED
Time: 0 SEC.
compiling exported empty : () -> $
;;; *** |SET;empty;$;4| REDEFINED
Time: 0 SEC.
compiling exported copy : $ -> $
;;; *** |SET;copy;2$;5| REDEFINED
Time: 0 SEC.
compiling exported parts : $ -> List S
;;; *** |SET;parts;$L;6| REDEFINED
Time: 0 SEC.
compiling exported inspect : $ -> S
;;; *** |SET;inspect;$S;7| REDEFINED
Time: 0.02 SEC.
compiling exported extract! : $ -> S
;;; *** |SET;extract!;$S;8| REDEFINED
Time: 0 SEC.
compiling exported find : (S -> Boolean,$) -> Union(S,failed)
;;; *** |SET;find;M$U;9| REDEFINED
Time: 0 SEC.
compiling exported map : (S -> S,$) -> $
;;; *** |SET;map;M2$;10| REDEFINED
Time: 0 SEC.
compiling exported reduce : ((S,S) -> S,$) -> S
;;; *** |SET;reduce;M$S;11| REDEFINED
Time: 0 SEC.
compiling exported reduce : ((S,S) -> S,$,S) -> S
;;; *** |SET;reduce;M$2S;12| REDEFINED
Time: 0 SEC.
compiling exported reduce : ((S,S) -> S,$,S,S) -> S
;;; *** |SET;reduce;M$3S;13| REDEFINED
Time: 0 SEC.
****** Domain: S already in scope
augmenting S: (ConvertibleTo (InputForm))
compiling exported convert : $ -> InputForm
;;; *** |SET;convert;$If;14| REDEFINED
Time: 0.16 SEC.
compiling local order : (S,S) -> Boolean
Time: 0 SEC.
compiling exported map! : (S -> S,$) -> $
Time: 0 SEC.
compiling exported construct : List S -> $
Time: 0.01 SEC.
****** Domain: S already in scope
augmenting S: (OrderedSet)
compiling exported = : ($,$) -> Boolean
Time: 0 SEC.
compiling exported max : $ -> S
Time: 0 SEC.
compiling exported min : $ -> S
Time: 0.01 SEC.
compiling exported insert! : (S,$) -> $
Time: 0 SEC.
compiling exported member? : (S,$) -> Boolean
Time: 0 SEC.
compiling exported remove! : (S,$) -> $
Time: 0 SEC.
compiling exported intersect : ($,$) -> $
Time: 0.01 SEC.
compiling exported difference : ($,$) -> $
Time: 0.01 SEC.
compiling exported symmetricDifference : ($,$) -> $
Time: 0.01 SEC.
compiling exported subset? : ($,$) -> Boolean
Time: 0.01 SEC.
compiling exported union : ($,$) -> $
Time: 0.01 SEC.
compiling exported insert! : (S,$) -> $
Time: 0.01 SEC.
compiling exported remove! : (S,$) -> $
Time: 0 SEC.
****** Domain: S already in scope
augmenting S: (Evalable S)
****** Domain: S already in scope
augmenting S: (ConvertibleTo (InputForm))
****** Domain: S already in scope
augmenting S: (Finite)
****** Domain: S already in scope
augmenting S: (OrderedSet)
(time taken in buildFunctor: 0)
;;; *** |Set| REDEFINED
;;; *** |Set| REDEFINED
Time: 0 SEC.
Cumulative Statistics for Constructor Set
Time: 0.28 seconds
finalizing NRLIB SET
Processing Set for Browser database:
--------constructor---------
; compiling file "/var/aw/var/LatexWiki/SET.NRLIB/SET.lsp" (written 31 JUL 2013 05:25:17 PM):
; /var/aw/var/LatexWiki/SET.NRLIB/SET.fasl written
; compilation finished in 0:00:00.146
------------------------------------------------------------------------
Set is now explicitly exposed in frame initial
Set will be automatically loaded when needed from
/var/aw/var/LatexWiki/SET.NRLIB/SET
Retest
fricas
A2:Set Integer := set [-2,-1,0]
Type: Set(Integer)
fricas
B2:Set Integer := set [0,1,4]
Type: Set(Integer)
fricas
C2:=map(x +-> x^2,A)
Type: Set(Integer)
fricas
test(B2=C2)
Type: Boolean
fricas
)set message any off
showTypeInOutput true;
Type: String
fricas
Set Any has OrderedSet
Type: Boolean
fricas
B5:Set Any:=B
Type: Set(Any)
fricas
C5:Set Any:=C
Type: Set(Any)
fricas
test(B5=C5)
Type: Boolean