From: lfellman@a.crl.com (Len Fellman)
Newsgroups: comp.sys.hp48
Subject: Set theory on the HP48
Date: Sun, 06 Sep 1998 02:18:58 GMT
Organization: College of Alameda
Lines: 62
Message-ID: <35f1f04a.2443454@nnrp2.crl.com>
NNTP-Posting-Host: a101012.sfo1.as.crl.com
X-Newsreader: Forte Free Agent 1.11/32.235
Xref: republic.btigate.com comp.sys.hp48:15548

Recently someone on this forum asked if one could operate with "sets"
on the HP48 (although we weren't sure whether the person really meant
"groups"). I couldn't resist writing this little program in which one
stores a list of any types of objects as a "universal set" and
provides operations for union (join), intersection (meet), complement,
and the "symmetric difference" of two sets A and B, which refers to (A
union B) minus (A intersect B).        

The program sets up a TMENU with the above operations, and requires
the user to define a global variable called 'OBLIST' which serves as
the universal set (this can also be done from the TMENU by hitting
Left-shift and the UNIV soft key).  So for example, if the universal
set is { 'A' 'B' 'C' 'D' 'E' }, then one can operate on subsets of
this set.       

The set operations are nothing more than OR, AND, NOT, and XOR
respectively, as appear in the MATH BASE LOGIC menu.  In fact, a
binary number can be interpreted as defining a subset of a universal
set of cardinality equal to the current wordsize (RCWS): a one in
position n means object n belongs to the set.   To extend this
representation to sets of more than 64 elements (the maximum
wordsize), one could use a list containing just 0's and 1's (reals),
and use the fact that AND, OR, XOR, and NOT also work for real
numbers, and that these operations can be "threaded" over lists.
UNFORTUNATELY, the threadability doesn't extend to the empty list (one
of those seemingly shortsided HP design decisions), so in order to
have an empty set (null set), one has to add an extra (arbitrary) list
element at the end of the list (so the null set is { 0 }.  The
universal set { 'A' 'B' 'C' 'D' 'E' } listed above is represented by {
1 1 1 1 1 0 }. { 'A' 'B' 'D' } is then represented by { 1 1 0 1 0 0 }.


 I took this a step further and provided routines to convert back and
forth between the two representations ( SET-> and ->SET ) (so the 0's
and 1's representation becomes transparent to the user).  I also
included a reasonable amount of graceful error recovery.   

     
 %%HP: T(3)A(D)F(.); DIR  Sets    \<< DEPTH RCLMENU \-> depth menu
\<< { { "JOIN"        \<< DUP2          IFERR SET\-> SWAP SET\-> OR
\->SET 3 ROLLD DROP2          THEN DEPTH depth - DROPN 515 DOERR
END        \>> } { "MEET"        \<< DUP2          IFERR SET\-> SWAP
SET\-> AND \->SET 3 ROLLD DROP2          THEN DEPTH depth - DROPN 515
DOERR          END        \>> } { "SDIFF"        \<< DUP2
IFERR SET\-> SWAP SET\-> XOR \->SET 3 ROLLD DROP2          THEN DEPTH
depth - DROPN 515 DOERR          END        \>> } { "CMPL"        \<<
DUP          IFERR SET\-> NOT \->SET SWAP DROP          THEN DEPTH
depth - DROPN 515 DOERR          END        \>> } { "UNIV" { OBLIST
\<< 'OBLIST' STO        \>> } } { "QUIT"        \<< menu MENU CONT
\>> } } TMENU HALT      \>>    \>>  \->SET    \<< DUP TYPE 5 ==
\<< DUP SIZE DUP 1 \<=        \<< DROP2 { }        \>>        \<< 1
SWAP 1- SUB OBLIST { } ROT 1          \<< DUP TYPE            \<<
DROP2 515 DOERR            \>> IFT            \<< OVER NSUB
IFERR GET              THEN 4 DROPN 515 DOERR              ELSE +
END            \>> IFT          \>> DOSUBS SWAP DROP        \>> IFTE
\>>      \<< 514 DOERR      \>> IFTE    \>>  SET\->    \<< DUP DUP
TYPE 5 ==      \<< DUP OBLIST { 0 } 1 3 PICK SIZE        START 0 +
NEXT        IF 3 PICK SIZE        THEN ROT 1          \<< 3 PICK SWAP
IFERR POS 1 PUT            THEN 5 DROPN 515 DOERR            END
\>> DOSUBS 3 ROLLD DROP2        ELSE 4 ROLLD 3 DROPN        END SWAP
DROP      \>>      \<< DROP 514 DOERR      \>> IFTE    \>>  OBLIST { A
B C D } END