The nset package provides set functions, such as intersection and union, for finite sets that are defined by explicit enumeration. Unlike the package set in Maxima's share library, nset treats lists and sets as distinct objects. This feature makes it possible to work with sets that have members that are either lists or sets.
Download the archive nset-x.tar.gz, where x is the release identifier, from http://www.unk.edu/acad/math/people/willisb. Under Linux, unpack it using
gzip -d nset-x.tar.gz
tar -xvf nset-x.tar
This will create a directory nset-x (again x is the release identifier) that contains the source file nset.lisp, user documentation in html and texi formats, a sample maxima initialization file nset-init.lisp, a README file, and a testing routine test-nset.mac.
Copy nset.lisp to a directory that Maxima can find. A good location is the same directory that contains set.lisp. Under Maxima release 5.9.0 or higher for Linux, set.lisp is in the directory
/usr/local/share/maxima/<ver>/share/misc/set.lisp
where <ver> is your Maxima release identifier. If you don't have write permission for this directory, or if you want to install nset.lisp in a different location, that is fine as long as you place it in a directory that Maxima can find.
For increased speed, you can compile nset.lisp. To do this, start Maxima in the nset-x directory and issue the command
(C1) compile_file("nset.lisp")$
This will create a file nset.xxx in the nset-x directory. The file extension xxx depends on which Lisp your Maxima uses; under gcl, the extension is "o". Copy the compiled file to the same directory where you put nset.lisp.
If you are using Maxima version 5.9.0 or higher, finish the installation by appending the contents of nset-init.lisp to your own maxima-init.lisp file. The Lisp file nset-init.lisp contains replacements for the Maxima functions setup_autoload and generic_autoload. Unlike Maxima's setup_autload function, the version in nset-init.lisp uses file_search. Without this change, a full pathname must be given to setup_autload. The autoload function in Maxima 5.9.0 and lower does not recognize some file extensions, such as .x86f and .fasl, as valid extensions for compiled code. The version of generic_autoload in nset-init fixes this problem. Additionally, nset-init.lisp contains the command
(add2lnc '$set $props)
This command appends "set" to Maxima's prop list; finally, the setup_autoload command contained in nset-init.lisp makes nset load automatically whenever you enter an expression containing a function from nset.
Maxima versions prior to 5.9.0 do not support initialization files. You may still use nset under these versions of Maxima; you must, however, manually load nset.lisp before you use any functions (especially the set function) that are in nset.
To use the set functions, begin by loading nset. Provided you have installed the package correctly, load it with the command
(C1) load("nset")$
If Maxima is unable to find nset, use its full pathname. If you have included an autoload statement for all functions in nset in your maxima-init.lisp file, you will not have to manually load nset.
To construct a set with members a1,a2,...,an, use the command set(a1,a2,...,an); to construct the empty set, use set(). If a set member is listed more than once, the simplification processes eliminates the redundant member.
(C1) set(); (D1) {} (C2) set(a,b,a); (D2) {a, b} (C3) set(a,set(b)); (D3) {a, {b}} (C4) set(a,[b]); (D4) {a, [b]}
Sets are displayed as brace delimited lists; it isn't possible, however, to define a set by enclosing its members in braces.
To construct a set from the elements of a list, use setify
(C4) setify([b,a]); (D4) {a,b}
Set members x and y are equal provided is(x = y) evaluates to true. Thus rat(x) and x are equal as set members; consequently,
(C1) set(x,rat(x)); (D1) {x}
Further, since is((x-1)*(x+1) = x^2 - 1) evaluates to false, (x-1)*(x+1) and x^2-1 are distinct set members; thus
(C2) set((x-1)*(x+1),x^2-1); 2 (D2) {(x - 1) (x + 1), x - 1}
To reduce this set to a singleton set, apply rat to each set member
(C3) map(rat,%); 2 (D3) {x - 1}
A set is simplified when its members are non-redundant and sorted according to the Maxima predicate orderlessp. (The only way to change the set ordering is to modify the source code to nset.) Some operations on sets, such as substitution, automatically force a re-simplification; for example,
(C1) s : set(a,b,c)$ (C2) subst(c=a,s); (D2) {a, b} (C3) ev(s,a=x,b=x,c=x); (D3) {x} (C4) map(lambda([x],x^2),set(-1,0,1)); (D4) {0, 1}
Most functions in nset work either sets or lists; when the function receives a list, but needs a set, the list is automatically converted to a set. Here are some examples that use the set functions setdifference, intersect, and union
(C1) intersect([a,a,b],set(b,c)); (D1) {b} (C2) setdifference([3,1,4,1,6],[3]); (D2) {1, 4, 6} (C3) union([a,b,b],[c,d],set(e,f)); (D3) {a, b, c, d, e, f}
To extract all set elements of a set s that satisfy a predicate f, use subset(s,f). (In Maxima, a predicate is a boolean-valued function.) For example, to find the equations in a given set that do not depend on a variable z, use
(C1) subset([x+y+z,x-y+4,x+y-5],lambda([e],freeof(z,e))); (D1) {- y + x + 4, y + x - 5}
The section Definitions for Sets has a complete list of the functions in nset
The nset package contains the miscellaneous utility functions dupe, flatten, permutations, and a few others.
The nset package uses the Maxima function orderlessp to order set members and the (Lisp-level) function like to test for set member equality. Both of these functions have known bugs (versions 5.9.0rc3 and earlier) that may manifest if you attempt to use sets with members that are lists or matrices that contain expressions in CRE form. An example is
(C1) set([x],[rat(x)]);
This command causes Maxima to halt with an error (the error message depends on which version of Lisp your Maxima uses). Another example is
(C2) setify([[rat(a)],[rat(b)]]);
These bugs are caused by bugs in orderlessp and like; they are not caused by bugs in nset. To illustrate, try the commands
(C1) orderlessp([rat(a)],[rat(b)]); (C2) is([rat(a)]=[rat(a)]);
Until these bugs are fixed, do not construct sets with members that are lists or matrices containing expressions in CRE form; a set with a member in CRE form, however, shouldn't be a problem
(C1) set(x,rat(x)); (D1)/R/ {x}
There are two other minor bugs that may manifest while using nset. Maxima versions 5.5 and earlier had a bug in the tex function that makes the empty set incorrectly translate to TeX; this bug is fixed in the Maxima 5.9.0. Additionally, the setup_autoload function in Maxima 5.9.0 is broken; a fix is in the nset-init.lisp file located in the nset distribution.
If you find something that you think might be a nset bug, please report it to the authors or to the Maxima mailing list.
A ambitious project would be adding support for sets (possibly infinite) with membership determined by a rule; for example
{x in reals | x = n %pi and n in integers}.
Maxima's solver package, as well as others, could be improved by making use of sets like these. A somewhat less ambitious project would be to support symbolic sets and to add rules, such as
union(a,a) => a,
intersect(a,a) => a,
intersect(a, union(a,b)) => a,
for simplifying set functions on symbolic sets.
Barton Willis of the University of Nebraska at Kearney (UNK) and Stavros Macrakis wrote the nset package and its documentation.
Adjoin x to the set a and return a set. Thus adjoin(x,a) and union(set(x),a) are equivalent; however, using adjoin might be faster. If a isn't a list or a set, signal an error.
(C1) adjoin(c,set(a,b)); (D1) {a, b, c} (C2) adjoin(a,set(a,b)); (D2) {a, b}
Return the number of distinct elements of the set a.
(C1) cardinality(set()); (D1) 0 (C2) cardinality(set(a,a,b,c)); (D2) 3 (C3) cardinality(set(a,a,b,c)), simp : false; (D3) 3
In line (c3), we see that cardinality works correctly even when simplification has been turned off. Like most functions in nset, the argument to cardinality may either be a list or a set; when the argument is a list, cardinality still returns the number of distinct elements of the list; for example,
(C4) cardinality([a,a,b,c]); (D4) 3
(C1) cartesian_product(set(0,1)); (D1) {[0], [1]} (C2) cartesian_product(set(0,1),set(0,1)); (D2) {[0, 0], [0, 1], [1, 0], [1, 1]} (C3) cartesian_product(set(x),set(y),set(z)); (D3) {[x, y, z]} (C4) cartesian_product(set(x),set(-1,0,1)); (D4) {[x, - 1], [x, 0], [x, 1]}
(C1) equiv_classes(set(a,b,c),lambda([x,y],is(x=y))); (D1) {{a}, {b}, {c}}
Actually, equiv_classes(s,f) automatically applies the Maxima function is after applying the function f; accordingly, we can re-work the previous example with the command
(C2) equiv_classes(set(a,b,c),"="); (D2) {{a}, {b}, {c}}
Here is another example
(C3) equiv_classes(set(1,2,3,4,5,6,7),lambda([x,y],remainder(x-y,3)=0)); (D3) {{1, 4, 7}, {2, 5}, {3, 6}}
(C1) extremal_subset(set(-2,-1,0,1,2),abs); (D1) {- 2, 2} (C3) extremal_subset(set(sqrt(2), 1.57, %pi/2),sin); %PI (D3) {---} 2
To find the minimizing subset, give the optional third argument a value
(C2) extremal_subset(set(-2,-1,0,1,2),abs, min); (D2) {0}
(C2) flatten(f(g(f(f(x))))); (D2) f(g(f(f(x)))) (C3) declare(f,nary); (D3) DONE (C4) ev(d2); (D4) f(g(f(x)))
Applied to a set, flatten gathers all members of set elements that are sets; for example
(C1) flatten(set(a, set(b), set(set(c)))); (D1) {a, b, c} (C2) flatten(set(a,set([a],set(a)))); (D2) {a, [a]}
Flatten works correctly when the main operator is a subscripted function
(C3) flatten(f[5](f[5](x))); (D3) f (x) 5
To successfully flatten an expression, the main operator must be defined for zero or more arguments; if this isn't the case, Maxima can halt with an error.
(C1) fullsetify([a,[a]]); (D1) {a, {a}} (C2) fullsetify([a,f([b])]); (D2) {a, f([b])} (C3)
In line (C2), the argument of f isn't converted to a set because the main operator of f([b]) isn't a list.
To convert just the top-level operator of a list to a set, see setify.
(C1) partition_set(set(2,7,1,8,2,8),evenp); (D1) [{1, 7}, {2, 8}] (C2) partition_set(set(x,rat(y),rat(y)+z,1),lambda([x], ratp(x))); (D2)/R/ [{1, x}, {y, y + z}]
(C1) permutations([a,a]); (D1) {[a, a]} (C2) permutations([a,a,b]); (D2) {[a, a, b], [a, b, a], [b, a, a]} (C3)
If a isn't a list or set, signal an error.
(C1) setp(set(a,a)),simp : false; (D1) TRUE
The function setp could be coded in Maxima as
setp(a) := is(inpart(a) = set).
(C1) subset(set(1,2,x,x+y,z,x+y+z),atom); (D1) {1,2,z} (C2) subset(set(1,2,7,8,9,14),evenp); (D2) {2,8,14}
The second argument to subset must be a Maxima predicate (a boolean-valued function of one argument) if the first argument to subset isn't a list or a set, signal an error. See also partition_set.
This document was generated on 19 December 2002 using the texi2html translator version 1.51a.