help links subscribe changes refresh edit

	#347 bug in map$Set	#348 Equality in Any	SandBox
	↑

SandBox Set Any

Edit detail for SandBox Set Any revision 1 of 2

	1 2
Editor: Time: 2007/11/18 18:35:17 GMT-8
Note: works in Set Any if domains are the same

changed:
-
In Issue #347 it is shown that set equality fails after applying
a map to a set:
\begin{axiom}
A:Set Integer := set [-2,-1,0]
B:Set Integer := set [0,1,4]
C:=map(x +-> x^2,A)
test(C=B)
\end{axiom}

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":http://www.lisp.org/HyperSpec/Body/fun_sxhash.html#sxhash).
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":/axiom--test--1/src/interp/GgreaterLisp ::

   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

\begin{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
\end{spad}

Retest

\begin{axiom}
A2:Set Integer := set [-2,-1,0]
B2:Set Integer := set [0,1,4]
C2:=map(x +-> x^2,A)
test(B2=C2)
\end{axiom}

\begin{axiom}
)set message any off
showTypeInOutput true;
\end{axiom}

\begin{axiom}
Set Any has OrderedSet
B5:Set Any:=B
C5:Set Any:=C
test(B5=C5)
\end{axiom}

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/7429413995785552697-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.01 SEC.

************* USER ERROR **********
available signatures for extract_!: 
    NONE
NEED extract_!: (NIL) -> ?
   Semantic Errors: 
      [1] extract_!: argument s of (extract_! s) is not declared

****** comp fails at level 1 with expression: ******
((DEF (|extract_!| |s|) (NIL NIL) (NIL NIL)
  (SEQ
   (LET |x|
     (|inspect| |s|))
   (|delete_!| |s| (|maxIndex| |s|)) (|exit| 1 |x|))))
****** level 1  ******
$x:= (DEF (extract_! s) (NIL NIL) (NIL NIL) (SEQ (LET x (inspect s)) (delete_! s (maxIndex s)) (exit 1 x)))
$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