5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: REDUCE INTERACTIVE LESSON NUMBER 6
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: David R. Stoutemyer
5f892713c3 2021-03-03 trnsz@pobox.c: University of Hawaii
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT This is lesson 6 of 7 REDUCE lessons. A prerequisite is to
5f892713c3 2021-03-03 trnsz@pobox.c: read an introductory text about LISP, such as "A Concise Introduction
5f892713c3 2021-03-03 trnsz@pobox.c: to LISP" by David L. Matuszek, which is freely available at
5f892713c3 2021-03-03 trnsz@pobox.c: https://www.cis.upenn.edu/~matuszek/LispText/lisp.html. Then
5f892713c3 2021-03-03 trnsz@pobox.c: familiarize yourself with the Standard Lisp Report, which is freely
5f892713c3 2021-03-03 trnsz@pobox.c: available via http://reduce-algebra.sourceforge.net/documentation.php.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: To avoid confusion between RLISP and the SYMBOLIC-mode algebraic
5f892713c3 2021-03-03 trnsz@pobox.c: algorithms, this lesson will treat only RLISP. Lesson 7 deals with how
5f892713c3 2021-03-03 trnsz@pobox.c: the REDUCE algebraic mode is implemented in RLISP and how the user can
5f892713c3 2021-03-03 trnsz@pobox.c: interact directly with that implementation. That is why I suggested
5f892713c3 2021-03-03 trnsz@pobox.c: that you run this lesson in RLISP rather than full REDUCE. If you
5f892713c3 2021-03-03 trnsz@pobox.c: forgot or do not have a locally available separate RLISP, then please
5f892713c3 2021-03-03 trnsz@pobox.c: switch now to symbolic mode by typing the statement SYMBOLIC.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic;
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Your most frequent mistakes are likely to be forgetting to quote
5f892713c3 2021-03-03 trnsz@pobox.c: data examples, using commas as separators within lists, and not putting
5f892713c3 2021-03-03 trnsz@pobox.c: enough levels of parentheses in your data examples.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Having learnt from reading the Standard Lisp Report about the built-in
5f892713c3 2021-03-03 trnsz@pobox.c: RLISP functions CAR, CDR, CONS, ATOM, EQ, NULL, LIST, APPEND, REVERSE,
5f892713c3 2021-03-03 trnsz@pobox.c: DELETE, MAPLIST, MAPCON, LAMBDA, FLAG, FLAGP, PUT, GET, DEFLIST,
5f892713c3 2021-03-03 trnsz@pobox.c: NUMBERP, ZEROP, ONEP, AND, EVAL, PLUS, TIMES, CAAR, CADR, etc., here
5f892713c3 2021-03-03 trnsz@pobox.c: is an opportunity to reinforce the learning by practice. Write
5f892713c3 2021-03-03 trnsz@pobox.c: expressions using CAR, CDR, CDDR, etc. (which are defined only through
5f892713c3 2021-03-03 trnsz@pobox.c: 4 letters between C and R) to individually extract each atom from F,
5f892713c3 2021-03-03 trnsz@pobox.c: where:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: f := '((john . doe) (1147 hotel street) honolulu);
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT My solutions are CAAR F, CDAR F, CAADR F, CADADR F, CADDR CADR
5f892713c3 2021-03-03 trnsz@pobox.c: F, and CADDR F.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Although commonly the "." is only mentioned in conjunction with data, we
5f892713c3 2021-03-03 trnsz@pobox.c: can also use it as an infix alias for CONS. Do this to build from F and
5f892713c3 2021-03-03 trnsz@pobox.c: from the data 'MISTER the s-expression consisting of F with MISTER
5f892713c3 2021-03-03 trnsz@pobox.c: inserted before JOHN.DOE;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT My solution is ('MISTER . CAR F) . CDR F.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Enough of these inane exercises -- let's get on to something useful!
5f892713c3 2021-03-03 trnsz@pobox.c: Let's develop a collection of functions for operating on finite sets.
5f892713c3 2021-03-03 trnsz@pobox.c: We will let the elements be arbitrary s-expressions, and we will
5f892713c3 2021-03-03 trnsz@pobox.c: represent a set as a list of its elements in arbitrary order, without
5f892713c3 2021-03-03 trnsz@pobox.c: duplicates.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Here is a function which determines whether its first argument is a
5f892713c3 2021-03-03 trnsz@pobox.c: member of the set which is its second element;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure memberp(elem, set1);
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Returns T if s-expression ELEM is a top-level element
5f892713c3 2021-03-03 trnsz@pobox.c: of list SET1, returning NIL otherwise;
5f892713c3 2021-03-03 trnsz@pobox.c: if null set1 then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else if elem = car set1 then t
5f892713c3 2021-03-03 trnsz@pobox.c: else memberp(elem, cdr set1);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: memberp('blue, '(red blue green));
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT This function illustrates several convenient techniques for
5f892713c3 2021-03-03 trnsz@pobox.c: writing functions which process lists:
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: 1. To avoid the errors of taking the CAR or the CDR of an atom,
5f892713c3 2021-03-03 trnsz@pobox.c: and to build self confidence while it is not immediately
5f892713c3 2021-03-03 trnsz@pobox.c: apparent how to completely solve the problem, treat the trivial
5f892713c3 2021-03-03 trnsz@pobox.c: cases first. For an s-expression or list argument, the most
5f892713c3 2021-03-03 trnsz@pobox.c: trivial cases are generally when one or more of the arguments
5f892713c3 2021-03-03 trnsz@pobox.c: are NIL, and a slightly less trivial case is when one or more
5f892713c3 2021-03-03 trnsz@pobox.c: is an atom. (Note that we will get an error message if we use
5f892713c3 2021-03-03 trnsz@pobox.c: MEMBERP with a second argument which is not a list. We could
5f892713c3 2021-03-03 trnsz@pobox.c: check for this, but in the interest of brevity, I will not
5f892713c3 2021-03-03 trnsz@pobox.c: strive to make our set-package give set-oriented error
5f892713c3 2021-03-03 trnsz@pobox.c: messages.)
5f892713c3 2021-03-03 trnsz@pobox.c: 2. Use CAR to extract the first element and use CDR to refer to
5f892713c3 2021-03-03 trnsz@pobox.c: the remainder of the list.
5f892713c3 2021-03-03 trnsz@pobox.c: 3. Use recursion to treat more complicated cases by extracting the
5f892713c3 2021-03-03 trnsz@pobox.c: first element and using the same functions on smaller
5f892713c3 2021-03-03 trnsz@pobox.c: arguments.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT To make MEMBERP into an infix operator we make the declaration:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: infix memberp;
5f892713c3 2021-03-03 trnsz@pobox.c: '(john.doe) memberp '((fig.newton) fonzo (santa claus));
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Infix operators associate left, meaning expressions of the form
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: (operand1 operator operand2 operator ... operator operandN)
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: are interpreted left-to-right as
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: ((...(operand1 operator operand2) operator ...) operator operandN).
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Operators may also be flagged RIGHT by
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: FLAG ('(op1 op2 ...), 'RIGHT).
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: to give the interpretation
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: (operand1 operator (operand2 operator (... operandN))...).
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Of the built-in operators, only ".", "*=", "+", and "*" associate right.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: If we had made the infix declaration before the function definition, the
5f892713c3 2021-03-03 trnsz@pobox.c: latter could have begun with the more natural statement
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: SYMBOLIC PROCEDURE ELEM MEMBERP SET.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Infix functions can also be referred to by functional notation if one
5f892713c3 2021-03-03 trnsz@pobox.c: desires. Actually, an analogous infix operator named MEMBER is
5f892713c3 2021-03-03 trnsz@pobox.c: already built-into RLISP, so we will use MEMBER rather than MEMBERP
5f892713c3 2021-03-03 trnsz@pobox.c: from here on. (But note that MEMBER returns the sublist beginning
5f892713c3 2021-03-03 trnsz@pobox.c: with the first argument rather than T.);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: member(1147, cadr f);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Inspired by the simple yet elegant definition of MEMBERP, write
5f892713c3 2021-03-03 trnsz@pobox.c: a function named SETP which uses MEMBER to check for a duplicate element
5f892713c3 2021-03-03 trnsz@pobox.c: in its list argument, thus determining whether or not the argument of
5f892713c3 2021-03-03 trnsz@pobox.c: SETP is a set;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT My solution is;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure setp candidate;
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Returns T if list CANDIDATE is a set, returning NIL
5f892713c3 2021-03-03 trnsz@pobox.c: otherwise;
5f892713c3 2021-03-03 trnsz@pobox.c: if null candidate then t
5f892713c3 2021-03-03 trnsz@pobox.c: else if car candidate member cdr candidate then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else setp cdr candidate;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: setp '(kermit, (cookie monster));
5f892713c3 2021-03-03 trnsz@pobox.c: setp '(dog cat dog);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT If you used a BEGIN-block, local variables, loops, etc., then
5f892713c3 2021-03-03 trnsz@pobox.c: your solution is surely more awkward than mine. For the duration of
5f892713c3 2021-03-03 trnsz@pobox.c: the lesson, try to do everything without groups, BEGIN-blocks, local
5f892713c3 2021-03-03 trnsz@pobox.c: variables, assignments, and loops. Everything can be done using
5f892713c3 2021-03-03 trnsz@pobox.c: function composition, conditional expressions, and recursion. It will
5f892713c3 2021-03-03 trnsz@pobox.c: be a mind-expanding experience -- more so than transcendental
5f892713c3 2021-03-03 trnsz@pobox.c: meditation, psilopsybin, and EST. Afterward, you can revert to your
5f892713c3 2021-03-03 trnsz@pobox.c: old ways if you disagree.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Thus endeth the sermon.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Incidentally, to make the above definition of SETP work for non-list
5f892713c3 2021-03-03 trnsz@pobox.c: arguments all we have to do is insert "ELSE IF ATOM CANDIDATE THEN
5f892713c3 2021-03-03 trnsz@pobox.c: NIL" below "IF NULL CANDIDATE THEN T".
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Now try to write an infix procedure named SUBSETOF, such that SET1
5f892713c3 2021-03-03 trnsz@pobox.c: SUBSETOF SET2 returns NIL if SET1 contains an element that SET2 does
5f892713c3 2021-03-03 trnsz@pobox.c: not, returning T otherwise. You are always encouraged, by the way, to
5f892713c3 2021-03-03 trnsz@pobox.c: use any functions that are already builtin, or that we have previously
5f892713c3 2021-03-03 trnsz@pobox.c: defined, or that you define later as auxiliary functions.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT My solution is;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: infix subsetof;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure set1 subsetof set2;
5f892713c3 2021-03-03 trnsz@pobox.c: if null set1 then t
5f892713c3 2021-03-03 trnsz@pobox.c: else if car set1 member set2 then cdr set1 subsetof set2
5f892713c3 2021-03-03 trnsz@pobox.c: else nil;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: '(roof door) subsetof '(window door floor roof);
5f892713c3 2021-03-03 trnsz@pobox.c: '(apple banana) subsetof '((apple cobbler) (banana creme pie));
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Two sets are equal when they have identical elements, not
5f892713c3 2021-03-03 trnsz@pobox.c: necessarily in the same order. Write an infix procedure named EQSETP
5f892713c3 2021-03-03 trnsz@pobox.c: which returns T if its two operands are equal sets, returning NIL
5f892713c3 2021-03-03 trnsz@pobox.c: otherwise.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT The following solution introduces the PRECEDENCE declaration:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: infix eqsetp;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence eqsetp, =;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence subsetof, eqsetp;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure set1 eqsetp set2;
5f892713c3 2021-03-03 trnsz@pobox.c: set1 subsetof set2 and set2 subsetof set1;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: '(ballet tap) eqsetp '(tap ballet);
5f892713c3 2021-03-03 trnsz@pobox.c: '(pine fir aspen) eqsetp '(pine fir palm);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT The precedence declarations make SUBSETOF have a higher
5f892713c3 2021-03-03 trnsz@pobox.c: precedence than EQSETP and make the latter have higher precedence than
5f892713c3 2021-03-03 trnsz@pobox.c: "=", which is higher than "AND". Consequently, these declarations
5f892713c3 2021-03-03 trnsz@pobox.c: enabled me to omit parentheses around "SET1 SUBSUBSETOF SET2" and
5f892713c3 2021-03-03 trnsz@pobox.c: around "SET2 SUBSETOF SET1". All prefix operators have higher
5f892713c3 2021-03-03 trnsz@pobox.c: precedence than any infix operator, and to inspect the ordering among
5f892713c3 2021-03-03 trnsz@pobox.c: the latter, we merely inspect the value of the global variable named;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: preclis!*;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Now see if you can write a REDUCE infix function named
5f892713c3 2021-03-03 trnsz@pobox.c: PROPERSUBSETOF, which determines if its left operand is a proper
5f892713c3 2021-03-03 trnsz@pobox.c: subset of its right operand, meaning it is a subset which is not equal
5f892713c3 2021-03-03 trnsz@pobox.c: to the right operand.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT All of the above exercises have been predicates. In contrast,
5f892713c3 2021-03-03 trnsz@pobox.c: the next exercise is to write a function called MAKESET, which returns
5f892713c3 2021-03-03 trnsz@pobox.c: a list which is a copy of its argument, omitting duplicates.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT How about:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure makeset lis;
5f892713c3 2021-03-03 trnsz@pobox.c: if null lis then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else if car lis member cdr lis then makeset cdr lis
5f892713c3 2021-03-03 trnsz@pobox.c: else car lis . makeset cdr lis;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT As you may have guessed, the next exercise is to implement an
5f892713c3 2021-03-03 trnsz@pobox.c: operator named INTERSECT, which returns the intersection of its set
5f892713c3 2021-03-03 trnsz@pobox.c: operands.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Here is my solution:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: infix intersect;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence intersect, subsetof;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure set1 intersect set2;
5f892713c3 2021-03-03 trnsz@pobox.c: if null set1 then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else if car set1 member set2
5f892713c3 2021-03-03 trnsz@pobox.c: then car set1 . cdr set1 intersect set2
5f892713c3 2021-03-03 trnsz@pobox.c: else cdr set1 intersect set2;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Symbolic-mode REDUCE has a built-in function named SETDIFF,
5f892713c3 2021-03-03 trnsz@pobox.c: which returns the set of elements which are in its first argument but
5f892713c3 2021-03-03 trnsz@pobox.c: not the second. See if you can write an infix definition of a similar
5f892713c3 2021-03-03 trnsz@pobox.c: function named DIFFSET.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Presenting --:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: infix diffset;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence diffset, intersect;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure left diffset right;
5f892713c3 2021-03-03 trnsz@pobox.c: if null left then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else if car left member right then cdr left diffset right
5f892713c3 2021-03-03 trnsz@pobox.c: else car left . (cdr left diffset right);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: '(seagull wren condor) diffset '(wren lark);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT The symmetric difference of two sets is the set of all
5f892713c3 2021-03-03 trnsz@pobox.c: elements which are in only one of the two sets. Implement a
5f892713c3 2021-03-03 trnsz@pobox.c: corresponding infix function named SYMDIFF. Look for the easy way!
5f892713c3 2021-03-03 trnsz@pobox.c: There is almost always one for examinations and instructional
5f892713c3 2021-03-03 trnsz@pobox.c: exercises.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Presenting --:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: infix symdiff;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence symdiff, intersect;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure set1 symdiff set2;
5f892713c3 2021-03-03 trnsz@pobox.c: append(set1 diffset set2, set2 diffset set1);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: '(seagull wren condor) symdiff '(wren lark);
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT We can use APPEND because the two set differences are
5f892713c3 2021-03-03 trnsz@pobox.c: disjoint.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: The above set of exercises (exercises of set?) have all returned set
5f892713c3 2021-03-03 trnsz@pobox.c: results. The cardinality, size, or length of a set is the number of
5f892713c3 2021-03-03 trnsz@pobox.c: elements in the set. More generally, it is useful to have a function
5f892713c3 2021-03-03 trnsz@pobox.c: which returns the length of its list argument, and such a function is
5f892713c3 2021-03-03 trnsz@pobox.c: built-into RLISP. See if you can write a similar function named
5f892713c3 2021-03-03 trnsz@pobox.c: SIZEE.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Presenting --:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure sizee lis;
5f892713c3 2021-03-03 trnsz@pobox.c: if null lis then 0
5f892713c3 2021-03-03 trnsz@pobox.c: else 1 + sizee cdr lis;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: sizee '(how marvelously concise);
5f892713c3 2021-03-03 trnsz@pobox.c: sizee '();
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Literal atoms, meaning atoms which are not numbers, are stored
5f892713c3 2021-03-03 trnsz@pobox.c: uniquely in LISP and in RLISP, so comparison for equality of literal
5f892713c3 2021-03-03 trnsz@pobox.c: atoms can be implemented by comparing their addresses, which is
5f892713c3 2021-03-03 trnsz@pobox.c: significantly more efficient than a character-by-character comparison
5f892713c3 2021-03-03 trnsz@pobox.c: of their names. The comparison operator "EQ" compares addresses, so
5f892713c3 2021-03-03 trnsz@pobox.c: it is the most efficient choice when comparing only literal atoms.
5f892713c3 2021-03-03 trnsz@pobox.c: The assignments
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: N2 := N1 := 987654321,
5f892713c3 2021-03-03 trnsz@pobox.c: S2 := S1 := '(FROG (SALAMANDER.NEWT)),
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: make N2 have the same address as N1 and make S2 have the same address
5f892713c3 2021-03-03 trnsz@pobox.c: as S1, but if N1 and N2 were constructed independently, they would not
5f892713c3 2021-03-03 trnsz@pobox.c: generally have the same address, and similarly for S1 vs. S2. The
5f892713c3 2021-03-03 trnsz@pobox.c: comparison operator "=", which is an alias for "EQUAL", does a general
5f892713c3 2021-03-03 trnsz@pobox.c: test for identical s-expressions, which need not be merely two
5f892713c3 2021-03-03 trnsz@pobox.c: pointers to the same address. Since "=" is built-in, compiled, and
5f892713c3 2021-03-03 trnsz@pobox.c: crucial, I will define my own differently-named version denoted "..="
5f892713c3 2021-03-03 trnsz@pobox.c: as follows:;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: newtok '((!. !. !=) myequal);
5f892713c3 2021-03-03 trnsz@pobox.c: infix eqatom, myequal;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence myequal, equal;
5f892713c3 2021-03-03 trnsz@pobox.c: precedence eqatom, eq;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure s1 myequal s2;
5f892713c3 2021-03-03 trnsz@pobox.c: if atom s1 then
5f892713c3 2021-03-03 trnsz@pobox.c: if atom s2 then s1 eqatom s2
5f892713c3 2021-03-03 trnsz@pobox.c: else nil
5f892713c3 2021-03-03 trnsz@pobox.c: else if atom s2 then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else car s1 myequal car s2 and cdr s1 myequal cdr s2;
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure a1 eqatom a2;
5f892713c3 2021-03-03 trnsz@pobox.c: if numberp a1 then
5f892713c3 2021-03-03 trnsz@pobox.c: if numberp a2 then zerop(a1-a2)
5f892713c3 2021-03-03 trnsz@pobox.c: else nil
5f892713c3 2021-03-03 trnsz@pobox.c: else if numberp a2 then nil
5f892713c3 2021-03-03 trnsz@pobox.c: else a1 eq a2;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Here I introduced a help function named EQATOM, because I was
5f892713c3 2021-03-03 trnsz@pobox.c: beginning to become confused by detail when I got to the line which
5f892713c3 2021-03-03 trnsz@pobox.c: uses EQATOM. Consequently, I procrastinated on attending to some fine
5f892713c3 2021-03-03 trnsz@pobox.c: detail by relegating it to a help function which I was confident could
5f892713c3 2021-03-03 trnsz@pobox.c: be successfully written later. After completing MYEQUAL, I was
5f892713c3 2021-03-03 trnsz@pobox.c: confident that it would work provided EQATOM worked, so I could then
5f892713c3 2021-03-03 trnsz@pobox.c: turn my attention entirely to EQATOM, freed of further distraction by
5f892713c3 2021-03-03 trnsz@pobox.c: concern about the more ambitious overall goal. It turns out that
5f892713c3 2021-03-03 trnsz@pobox.c: EQATOM is a rather handy utility function anyway, and practice helps
5f892713c3 2021-03-03 trnsz@pobox.c: develop good judgement about where best to so subdivide tasks. This
5f892713c3 2021-03-03 trnsz@pobox.c: psychological divide-and-conquer programming technique is important in
5f892713c3 2021-03-03 trnsz@pobox.c: most other programming languages too.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: "..=" is different from our previous examples in that "..=" recurses
5f892713c3 2021-03-03 trnsz@pobox.c: down the CAR as well as down the CDR of an s-expression.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT If a list has n elements, our function named MEMBERP or the
5f892713c3 2021-03-03 trnsz@pobox.c: equivalent built-in function named MEMBER requires on the order of n
5f892713c3 2021-03-03 trnsz@pobox.c: "=" tests. Consequently, the above definitions of SETP and MAKESET,
5f892713c3 2021-03-03 trnsz@pobox.c: which require on the order of n membership tests, will require on the
5f892713c3 2021-03-03 trnsz@pobox.c: order of n^2 "=" tests. Similarly, if the two operands have m and n
5f892713c3 2021-03-03 trnsz@pobox.c: elements, the above definitions of SUBSETOF, EQSETP, INTERSECT,
5f892713c3 2021-03-03 trnsz@pobox.c: DIFFSET, and SYMDIFF require on the order of m*n "=" tests. We could
5f892713c3 2021-03-03 trnsz@pobox.c: decrease the growth rates to order of n and order of m+n respectively
5f892713c3 2021-03-03 trnsz@pobox.c: by sorting the elements before giving lists to these functions. The
5f892713c3 2021-03-03 trnsz@pobox.c: best algorithms sort a list of n elements in the order of n*log(n)
5f892713c3 2021-03-03 trnsz@pobox.c: element comparisons, and this need be done only once per input set.
5f892713c3 2021-03-03 trnsz@pobox.c: To do so we need a function which returns T if the first argument is
5f892713c3 2021-03-03 trnsz@pobox.c: "=" to the second argument or should be placed to the left of the
5f892713c3 2021-03-03 trnsz@pobox.c: second argument. Such a function, named ORDP, is already built-into
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic-mode REDUCE, based on the following rules:
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: 1. Any number orders left of NIL.
5f892713c3 2021-03-03 trnsz@pobox.c: 2. Larger numbers order left of smaller numbers.
5f892713c3 2021-03-03 trnsz@pobox.c: 4. Literal atoms order left of numbers.
5f892713c3 2021-03-03 trnsz@pobox.c: 3. Literal atoms order among themselves by address, as determined
5f892713c3 2021-03-03 trnsz@pobox.c: by the built-in RLISP function named ORDERP.
5f892713c3 2021-03-03 trnsz@pobox.c: 5. Non-atoms order left of atoms.
5f892713c3 2021-03-03 trnsz@pobox.c: 6. Non-atoms order among themselves according to ORDP of their
5f892713c3 2021-03-03 trnsz@pobox.c: CARs, with ties broken according to ORDP of their CDRs.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: Try writing an analogous function named MYORD, and, if you are in
5f892713c3 2021-03-03 trnsz@pobox.c: REDUCE rather than RLISP, test its behavior in comparison to ORDP.;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: pause;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Whether or not we use sorted sets, we can reduce the
5f892713c3 2021-03-03 trnsz@pobox.c: proportionality constant associated with the growth rate by replacing
5f892713c3 2021-03-03 trnsz@pobox.c: "=" by "EQ" if the set elements are restricted to literal atoms.
5f892713c3 2021-03-03 trnsz@pobox.c: However, with such elements we can use property-lists to achieve the
5f892713c3 2021-03-03 trnsz@pobox.c: growth rates of the sorted algorithms without any need to sort the
5f892713c3 2021-03-03 trnsz@pobox.c: sets. On any LISP system that is efficient enough to support REDUCE
5f892713c3 2021-03-03 trnsz@pobox.c: with acceptable performance, the time required to access a property of
5f892713c3 2021-03-03 trnsz@pobox.c: an atom is modest and very insensitive to the number of distinct atoms
5f892713c3 2021-03-03 trnsz@pobox.c: in the program and data. Consequently, the basic technique for any of
5f892713c3 2021-03-03 trnsz@pobox.c: our set operations is:
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: 1. Scan the list argument or one of the two list arguments,
5f892713c3 2021-03-03 trnsz@pobox.c: flagging each element as "SEEN".
5f892713c3 2021-03-03 trnsz@pobox.c: 2. During the first scan, or during a second scan of the same
5f892713c3 2021-03-03 trnsz@pobox.c: list, or during a scan of the second list, check each element
5f892713c3 2021-03-03 trnsz@pobox.c: to see whether or not it has already been flagged, and act
5f892713c3 2021-03-03 trnsz@pobox.c: accordingly.
5f892713c3 2021-03-03 trnsz@pobox.c: 3. Make a final pass through all elements which were flagged to
5f892713c3 2021-03-03 trnsz@pobox.c: remove the flag "SEEN". (Otherwise, we may invalidate later set
5f892713c3 2021-03-03 trnsz@pobox.c: operations which utilize any of the same atoms.)
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: We could use indicators rather than flags, but the latter are slightly
5f892713c3 2021-03-03 trnsz@pobox.c: more efficient when an indicator would have only one value (such as
5f892713c3 2021-03-03 trnsz@pobox.c: having "SEEN" as the value of an indicator named "SEENORNOT").
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: As an example, here is INTERSECT defined using this technique;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: symbolic procedure intersect(s1, s2);
5f892713c3 2021-03-03 trnsz@pobox.c: begin scalar ans, set2;
5f892713c3 2021-03-03 trnsz@pobox.c: flag(s1, 'seen);
5f892713c3 2021-03-03 trnsz@pobox.c: set2 := s2;
5f892713c3 2021-03-03 trnsz@pobox.c: while set2 do <<
5f892713c3 2021-03-03 trnsz@pobox.c: if flagp(car set2, 'seen) then ans := car set2 . ans;
5f892713c3 2021-03-03 trnsz@pobox.c: set2 := cdr set2 >>;
5f892713c3 2021-03-03 trnsz@pobox.c: remflag(s1, 'seen);
5f892713c3 2021-03-03 trnsz@pobox.c: return ans
5f892713c3 2021-03-03 trnsz@pobox.c: end;
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: COMMENT Perhaps you noticed that, having used a BEGIN-block, group,
5f892713c3 2021-03-03 trnsz@pobox.c: loop, and assignments, I have not practiced what I preached about
5f892713c3 2021-03-03 trnsz@pobox.c: using only function composition, conditional expressions, and
5f892713c3 2021-03-03 trnsz@pobox.c: recursion during this lesson. Well, now that you have had some
5f892713c3 2021-03-03 trnsz@pobox.c: exposure to both extremes, I think you should always fairly consider
5f892713c3 2021-03-03 trnsz@pobox.c: both together with appropriate compromises, in each case choosing
5f892713c3 2021-03-03 trnsz@pobox.c: whatever is most clear, concise, and natural. For set operations
5f892713c3 2021-03-03 trnsz@pobox.c: based on the property-list approach, I find the style exemplified
5f892713c3 2021-03-03 trnsz@pobox.c: immediately above most natural.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: As your last exercise for this lesson, develop a file containing a
5f892713c3 2021-03-03 trnsz@pobox.c: package for set operations based upon either property-lists or
5f892713c3 2021-03-03 trnsz@pobox.c: sorting.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: This is the end of lesson 6. When you are ready to run the final
5f892713c3 2021-03-03 trnsz@pobox.c: lesson 7, load a fresh copy of REDUCE.
5f892713c3 2021-03-03 trnsz@pobox.c:
5f892713c3 2021-03-03 trnsz@pobox.c: ;end;