login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Edit detail for SandBox Set Any revision 2 of 2

1 2
Editor: test1
Time: 2013/07/31 17:25:19 GMT+0
Note:

changed:
-   extract_! s ==
   extract! s ==

changed:
-     delete_!(s, maxIndex s)
     delete!(s, maxIndex s)

changed:
-   map(f, s) == map_!(f,copy s)
   map(f, s) == map!(f,copy s)

changed:
-   map_!(f,s) ==
-     map_!(f,s)$Rep
-     sort_!(order,s)$Rep
-     removeDuplicates_! s
   map!(f, s) ==
     map!(f, s)$Rep
     sort!(order, s)$Rep
     removeDuplicates! s

changed:
-     removeDuplicates_! sort_!(order,a)
     removeDuplicates! sort!(order, a)

changed:
-     insert_!(x, s) ==
     insert!(x, s) ==

changed:
-       insert_!(x, s, k)
       insert!(x, s, k)

changed:
-     remove_!(x:S, s:%) ==
     remove!(x:S, s:%) ==

changed:
-       k < n and x = s.k => delete_!(s, k)
       k < n and x = s.k => delete!(s, k)

changed:
-         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; j := j+1)

changed:
-         s.i < t.j => (concat_!(r, s.i); i := i+1)
         s.i < t.j => (concat!(r, s.i); i := i+1)

changed:
-       while i <= m repeat (concat_!(r, s.i); i := i+1)
-       r
       while i <= m repeat (concat!(r, s.i); i := i+1)
       r

changed:
-         s.i < t.j => (concat_!(r, s.i); i := i+1)
-         s.i > t.j => (concat_!(r, t.j); j := j+1)
         s.i < t.j => (concat!(r, s.i); i := i+1)
         s.i > t.j => (concat!(r, t.j); j := j+1)

changed:
-       while i <= m repeat (concat_!(r, s.i); i := i+1)
-       while j <= n repeat (concat_!(r, t.j); j := j+1)
-       r
       while i <= m repeat (concat!(r, s.i); i := i+1)
       while j <= n repeat (concat!(r, t.j); j := j+1)
       r

changed:
-         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
         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

changed:
-     insert_!(x, s) ==
     insert!(x, s) ==

changed:
-       insert_!(x, s, inc maxIndex s)
-
-     remove_!(x:S, s:%) ==
       insert!(x, s, inc maxIndex s)

     remove!(x:S, s:%) ==

changed:
-         x = s.k => return delete_!(s, k)
         x = s.k => return delete!(s, k)

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]

\label{eq1}\left\{ - 2, \: - 1, \: 0 \right\}(1)
Type: Set(Integer)
fricas
B:Set Integer := set [0,1,4]

\label{eq2}\left\{ 0, \: 1, \: 4 \right\}(2)
Type: Set(Integer)
fricas
C:=map(x +-> x^2,A)

\label{eq3}\left\{ 0, \: 1, \: 4 \right\}(3)
Type: Set(Integer)
fricas
test(C=B)

\label{eq4} \mbox{\rm true} (4)
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.
************* USER ERROR ********** available signatures for brace: NONE NEED brace: () -> ? ****** comp fails at level 1 with expression: ****** ((DEF (|brace|) (NIL) (NIL) (|empty|))) ****** level 1 ****** $x:= (DEF (brace) (NIL) (NIL) (empty)) $m:= $EmptyMode $f:= ((((|#| #) (< #) (<= #) (= #) ...)))
>> Apparent user error: unspecified error

Retest

fricas
A2:Set Integer := set [-2,-1,0]

\label{eq5}\left\{ - 2, \: - 1, \: 0 \right\}(5)
Type: Set(Integer)
fricas
B2:Set Integer := set [0,1,4]

\label{eq6}\left\{ 0, \: 1, \: 4 \right\}(6)
Type: Set(Integer)
fricas
C2:=map(x +-> x^2,A)

\label{eq7}\left\{ 0, \: 1, \: 4 \right\}(7)
Type: Set(Integer)
fricas
test(B2=C2)

\label{eq8} \mbox{\rm true} (8)
Type: Boolean

fricas
)set message any off
showTypeInOutput true;
Type: String

fricas
Set Any has OrderedSet

\label{eq9} \mbox{\rm false} (9)
Type: Boolean
fricas
B5:Set Any:=B

\label{eq10}\left\{{0 : \hbox{\axiomType{Integer}\ }}, \:{1 : \hbox{\axiomType{Integer}\ }}, \:{4 : \hbox{\axiomType{Integer}\ }}\right\}(10)
Type: Set(Any)
fricas
C5:Set Any:=C

\label{eq11}\left\{{0 : \hbox{\axiomType{Integer}\ }}, \:{1 : \hbox{\axiomType{Integer}\ }}, \:{4 : \hbox{\axiomType{Integer}\ }}\right\}(11)
Type: Set(Any)
fricas
test(B5=C5)

\label{eq12} \mbox{\rm true} (12)
Type: Boolean