map confuses sets.

(1) -> A:Set Integer:=set [-2,-1,0]

(1)

B:Set Integer:=set [0,1,4]

(2)

C:=map(x +-> x^2,A)

(3)

test(C=B)

(4)

somehow a sort is missing after applying map.

Proposed Fix

If S has OrderedSet then map_! should include 'sort':

   map_!(f,s) ==
     map_!(f,s)$Rep
     sort_!(s)$Rep
     removeDuplicates_!

See diff

See also: SandBoxSetAny for a more ambitious fix that defines an ordering for all Sets.

)abbrev domain SET Set
++ Author: Michael Monagan; revised by Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last 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]

   if S has OrderedSet then
     s = t == s =$Rep t
     max s == inspect s
     min s == (empty? s => error "Empty set"; s(minIndex s))

     map_!(f,s) ==
       map_!(f,s)$Rep
       sort_!(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_! a

     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
     map_!(f,s) ==
       map_!(f,s)$Rep
       removeDuplicates_! s

     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

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/7072998645375249993-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 SEC.

************* USER ERROR **********
available signatures for brace: 
    NONE
NEED brace: () -> ?
****** comp fails at level 1 with expression: ******
((DEF (|brace|) (NIL) (|empty|)))
****** level 1  ******
$x:= (DEF (brace) (NIL) (empty))
$m:= $EmptyMode
$f:=
((((|#| #) (< #) (<= #) (= #) ...)))

   >> Apparent user error:
   unspecified error

Retest

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

(5)

B2:Set Integer:=set [0,1,4]

(6)

C2:=map(x +-> x^2,A)

(7)

test(B2=C2)

(8)

But unfortunately the documentation lies:

  ++ 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.

This example shows that Set is not maintained in sorterd order. So the code for Set still appears to be broken if the Set is constructed over a domain that is not an OrderedSet.

)set message any off

showTypeInOutput true;

Set Any has OrderedSet

(9)

B3:Set Any:=B;B3

(10)

C3:Set Any:=C;C3

(11)

test(B3=C3)

(12)

But why does this example work? Is set equality implemented as an order n^2 comparison if the domain is not an OrderedSet?

   s = t           == #s = #t and empty? difference(s,t)

   ...

   difference(s:%, t:%) ==
     m := copy s
     for x in parts t repeat remove_!(x, m)
     m