dan@Apple.COM (Dan Allen) (04/11/90)
LIST and SET Operations for the HP-48SX
By Dan Allen, 10 April 1990
Revision 2
LIST PROCESSING
The HP-48SX supports lists of objects as a built-in data type. Several
functions are provided for working on lists:
Function Operation
-------- ---------
+ Concatenates two lists into one list
SIZE Returns the number of elements in a list
POS Checks if an element is in a list
SUB Returns a subset of a list as a list
GET Returns the nth element of a list
PUT Replaces the nth element of a list
Other than direct editing of a list, there is no way to add elements to a list
other than by appending elements to the front or back of a list through the +
operator, and there is no way to delete elements of a list.
Here are a few list operations that extend the functionality of the HP-48SX.
Ideally these should be in a future machine; in the meantime they should be
written in assembly language for better efficiency.
The first two functions are CAR and CDR, named after the LISP functions of
the same bizarre but historically interesting names. Common LISP also has the
functions FIRST and REST which are exactly the same as CAR and CDR, which
return the first and remaining parts of a list. The second pair of functions
are INS and DEL, which allow inserting and deleting specific elements of a
list.
These routines handle invalid arguments quietly, i.e., deleting the 5th
element of a 4 element list does nothing; it returns the 4 element list
unchanged, without any error mentioned. Similar handling of invalid
conditions is done by the other routines as well.
LISTS AS SETS
A list supports an ordering of its elements and can have duplicate members.
Sets are not ordered and can only have one occurance of a given object. With
these restrictions, a list can be used as a set with various functions
designed to support set operations. Such functions are provided here, with
many of the operations also being valid on lists as well.
ADJOIN allows items to be added to a set. ADJOIN makes sure that no
duplicate entries are allowed in the list, thus enforcing one of the rules of
sets.
MEMBER tests set membership, that is, it checks to see if an object is
included in a set (or list). It only searches the top level. It returns a
CDR-like list beginning with the item found, or the empty list { } if the
object is not found.
UNION and INTERSECT implement set union and intersection, while DIFF and
SDIFF are set difference and symmetric difference. If the lists given are not
sets (that is, they contain duplicates), duplicates may appear in the results.
These four operations are the main arithmetic operations for sets, with the
following similarities to arithmetic and boolean operations:
ARITHMETIC BOOLEAN SET OPERATION
---------- ------- -------------
addition (+) OR (inclusive) union
subtraction (-) AND NOT difference
multiplication (*) AND intersection
division (/) XOR symmetric difference
EXAMPLES
{ 1 2 3 } CAR --> 1 { } CAR --> { }
{ 1 2 3 } CDR --> { 2 3 } { } CDR --> { }
{ 1 2 3 } 1 0 INS --> { 0 1 2 3 } { 1 2 } 9999 48 INS --> { 1 2 48 }
{ 1 2 3 } 2 DEL --> { 1 3 } { 1 2 } 9999 DEL --> { 1 2 }
{ 1 2 3 } 2 MEMBER --> { 2 3 } { 1 2 3 } 4 MEMBER --> { }
{ 1 2 } 3 ADJOIN --> { 1 2 3 } { 1 2 3 } 3 ADJOIN --> { 1 2 3 }
{ 1 2 } { 3 4 } UNION --> {1 2 3 4} { 1 2 } { 1 2 } UNION --> { 1 2 }
{ 1 2 } { 3 4 } INTERSECT --> { } { 1 2 } { 2 3 } INTERSECT --> { 2 }
{ 1 2 } { 3 4 } DIFF --> { 1 2 } { 1 2 } { 2 3 } DIFF --> { 1 }
{ 1 2 } { 3 4 } SDIFF --> {1 2 3 4} { 1 2 } { 2 3 } SDIFF --> { 1 3 }
Comments are bracketed by @ signs. With minor changes, most of these
programs should run on the HP-28. Here then are some useful list and set
operations for the HP-48SX:
CAR @ Extracts the first object of a list as an atomic entity @
<< @ USAGE: list CAR --> obj @
IF DUP SIZE THEN 1 GET END @ CAR of empty list is an empty list @
>>
CDR @ Returns the tail (all but 1st object) of a list as a list @
<< @ USAGE: list CDR --> list @
OBJ->
IF DUP
THEN 1 - ->LIST SWAP DROP
ELSE DROP { } @ CDR of an empty list is the empty list @
END
>>
INS @ Inserts an object as the nth element of list @
<< @ USAGE: list integer obj INS --> list @
-> list n x
<<
list 1 n 1 - SUB x + list n list SIZE SUB +
>>
>>
DEL @ Deletes the nth element of list @
<< @ USAGE: list integer DEL --> list @
-> list n
<<
list 1 n 1 - SUB list n 1 + list SIZE SUB +
>>
>>
MEMBER @ Checks if obj is a member of list at the top level @
<< @ USAGE: list obj MEMBER --> list @
-> list obj
<<
list obj
IF POS DUP 0 >
THEN list SWAP list SIZE SUB
ELSE DROP { }
END
>>
>>
ADJOIN @ Adds an object to a list, preventing duplicates @
<< @ USAGE: list obj ADJOIN --> list @
-> list obj
<<
IF list obj MEMBER SIZE
THEN list
ELSE list obj +
END
>>
>>
UNION @ Returns the set union of two lists (c = a OR b) @
<< @ USAGE: list list UNION --> list @
OVER -> a b c @ efficiency tip: put smallest list on top of stack @
<<
IF a SIZE 0 == b SIZE 0 == OR
THEN a b + @ if either list is empty then concatenate lists @
ELSE @ step through the second list's elements @
b 1 1 b SIZE
START
GETI DUP c SWAP
IF POS
THEN DROP
ELSE 'c' SWAP STO+ @ adding appropriate new elements @
END
NEXT
DROP2 c
END
>>
>>
INTERSECT @ Returns the set intersection of two lists (c = a AND b) @
<< @ USAGE: list list INTERSECT --> list @
{ } -> a b c @ efficiency tip: put smallest list on top of stack @
<<
IF a SIZE 0 == b SIZE 0 == OR
THEN c
ELSE
b 1 1 b SIZE
START
GETI DUP a SWAP
IF POS
THEN 'c' SWAP STO+
ELSE DROP
END
NEXT
DROP2 c
END
>>
>>
DIFF @ Returns the set difference of two lists (c = a AND NOT b) @
<< @ USAGE: list list DIFF --> list @
{ } -> a b c
<<
IF a SIZE 0 == THEN c
ELSE IF b SIZE 0 == THEN a
ELSE
a 1 1 a SIZE
START
GETI DUP b SWAP
IF POS
THEN DROP
ELSE 'c' SWAP STO+
END
NEXT
DROP2 c
END
END
>>
>>
SDIFF @ Returns the set symmetric difference between two lists (c = a XOR b)
@
<< @ USAGE: list list SDIFF --> list @
{ } -> a b c @ Efficiency note: this is O(n^2) and could be improved @
<<
IF a SIZE 0 == THEN b @ if a is empty, then return b @
ELSE IF b SIZE 0 == THEN a @ if b is empty, then return a @
ELSE @ else loop through both lists @
a 1 1 a SIZE
START
GETI DUP b SWAP
IF POS
THEN DROP
ELSE 'c' SWAP STO+
END
NEXT
DROP2
b 1 1 b SIZE
START
GETI DUP a SWAP
IF POS
THEN DROP
ELSE 'c' SWAP STO+
END
NEXT
DROP2 c
END
END
>>
>>