"Misprint", in Question 2 "x isset y" should be "x elementof y".
Kip Murray wrote: > See inserted comments and after them, discussion, examples, commented code, > "catechism", and closing examples! > > Raul Miller wrote: >> On Fri, Aug 14, 2009 at 11:33 AM, Kip Murray<[email protected]> wrote: >>> I think it would need to be >>> >>> NB. A "set" is 0$<1 or a 'realsetted' list of unique boxes. >> ... >>> What do you think? > > >> I am uncomfortable with this approach. > > I AGREE as you will see. I prefer a set to be either 0$<1 or a list of boxes > without duplicates. > >> It does not document the data structure concepts, >> like the previous versions did. > > I WILL PROVIDE a verb that tests whether an array is a set, and another which > tests whether an array is an element of a set. > >> Nor does it define an API. > > >> It's sort of half-way inbetween. > > WHAT'S AN API? (I'm serious, I do not know.) > >> Meanwhile, I would not try and be sneaky about >> this, and "hide the issue from the user". Otherwise, >> users will run into problems when they start coding >> systems which use sets of sets of sets nested >> arbitrary levels deep, or when they use sets of >> sequences of sets of sequences, or some other >> such variants. > > COME, SEELING NIGHT, SCARF UP THE TENDER EYE OF PITIFUL DAY; ... LIGHT > THICKENS; > AND THE CROW MAKES WING TO THE ROOKY WOOD: > > Macbeth: Act 3, Scene 2 > > SO FAR AS I KNOW, the present model handles sets of sets and nonset arrays > nested arbitrary levels deep. > ---------------------------- > > Discussion > > I think my model of finite set theory will work out. A set is simply 0$<1 or > a > list of boxes without duplicates; and an element is the open of one of the > boxes: if there are any. > > Following a plan of Fraser's for a much broader context (set = any array), > verb > realset sorts sets at need-time, i.e., when they need to be compared to > establish set identity or membership. The sorting begins with leaves and > works > its way up through the levels of the set as defined for verb L. . The user > is > free to use his or her own application-driven order for his sets, which are > not > replaced by "realsetted" sets, although differences, unions, > intersections,and > power sets may not be in an order the user recognizes. The user is free to > reorder these to suit his needs; they will still be sets. > > Illustrating realset: > > ]N =: pwrSet 1;0 > ++---+---+-----+ > ||+-+|+-+|+-+-+| > |||0|||1|||1|0|| > ||+-+|+-+|+-+-+| > ++---+---+-----+ > isset N > 1 > #N NB. one element is the empty set E =: 0$<1 > 4 > E elementof N > 1 > E -: 0 {:: N NB. fetching the contents of box zero > 1 > /:~ N NB. simple sort : N is already sorted > ++---+---+-----+ > ||+-+|+-+|+-+-+| > |||0|||1|||1|0|| > ||+-+|+-+|+-+-+| > ++---+---+-----+ > realset N NB. first, leaf 1;0 is sorted; then its list: > ++---+-----+---+ > ||+-+|+-+-+|+-+| > |||0|||0|1|||1|| > ||+-+|+-+-+|+-+| > ++---+-----+---+ > > NB. It's an "alphabetical" sort, as you see. Details next: > > > Commented code > > NB. "Real sets" 12 August 2009 and 14 August 2009 > > NB. 14 August 2009 Enclose with ( ... &realset) verbs needing set comparisons, > NB. i.e. elementof less u n subsetof . Verb equalset already has &realset. > > NB. A "set" is 0$<1 or a non-empty list of boxes with no duplicates. > NB. An "element" is the open of a box. As 0$<1 has no box it has no element. > > NB. verb isset below tests whether an array is a set; verb elementof below > tests > NB. whether an array is an element of a set. > > NB. M =: set element;element;...;element creates a set with those > elements. > > NB. Use M =: set element;...;element;<element if the rightmost element is > boxed. > > NB. Verb set =: ~. is defined below. > > NB. If you are CAREFUL TO HAVE NO DUPLICATES you can use > > NB. M =: element;element;...;element when rightmost element is open > > NB. M =: element;...;element;<element when rightmost element is boxed > > NB. Finally, use ,<element "a list of one box" for a set with only one > element. > > load 'validate' > > set =: ~. NB. creates a non-empty set when used as shown above > > isset =: -:&(0$<1) +. isvector *. isboxed *. (-: ~.) > NB. 0$<1 or list of boxes without duplicates > > NB. isboxed also implies a non-empty array. > > isrealset =: -: realset NB. see verb realset below > > Empty =: 0$<1 NB. empty set > > E =: Empty > > sortset =: ( ] : [: )`( /:~ : [: )@.( (isset f.) *. -.@((0$<1) -: ]) ) > NB. If argument is a set but not 0$<1 , sortset sorts the argument; > NB. sortset returns 0$<1 and nonsets unchanged. > > realset =: 3 : 0 NB. up-the-levels sortset; almost Fraser's sortSet > s =. y > for_k. i. >: L. y do. s =. sortset L:k s end. > ) > > NB. usage realset set produces an equivalent "real set": up-the-levels > NB. "sortsetted" for easy comparison with other "real sets". > > NB. Notice verb sortset applied to an array leaves the array unchanged if it > NB. is 0$<1 or not a set. > > > NB. Source: This program of Fraser's is a real break-through: > > sortSet =: 3 : 0 NB. Fraser's; the source of realset > s =. y > for_k. i. >: L. y do. s =. Set L:k s end. > ) > > > equalset =: -:&realset NB. i.e., equal as sets; &realset enables comparison > > eqs =: equalset > > elementof =: (<@[ e. ])&realset NB. &realset for set comparisons > > in =: elementof > > NB. verb less removes from y its elements which are elements of x > > less =: -.&realset NB. difference; &realset for set comparisons > > u =: (-. , ])&realset NB. union; R. E. Boss and Oleg Kobchenko, &realset... > > n =: ([ -. -.)&realset NB. intersection; R. E. Boss and Oleg Kobchenko, ... > > subsetof =: ([ -: [ -. -.)&realset NB. &realset for set comparisons > > part =: subsetof > > > NB. pwrSet below is Raul's powSet without the sort > > pwrSet =: (<@#~) 2 (#"1~ {:)@#:@i...@^ # > > > NB. Source: Raul's powSet, another mile-stone: > > NB. powSet=: /:~@:(<@#~) 2 (#"1~ {:)@#:@i...@^ # NB. Raul's; the source of > pwrSet > > NB. Commented out to avoid confusion with pwrSet > > > Catechism > > "Catechism" is a list of questions and answers recited by the implementor. > He > or she provides answers for the first two questions, explaining what a set is > in > the model, and what element of means in the model. The remaining answers are > handed to the implementor, who is responsible for seeing that the model obeys > them. > > Question 1. What is a set? > Answer: A set is an array y such that isset y returns 1. In words, a set > is > either 0$<1 or it is a list of boxes without duplicates. Verb isset makes > clear > that the list of boxes is not empty. > > Question 2. What does element of mean? > Answer: To say array x is an element of the set y neans that x is an array > and y is a set and x isset y returns 1. In words, no array is an element of > 0$<1, called the empty set; and an element of a list of boxes is the open of > one > of the boxes. > > Question 3. When are two sets said to be the same? > Answer: (a little smart-alecky) Well, you should never say _two_ things > are > the same thing. But to say set H is the same as set K means no element of H > is > not an element of K, and no element of K is not an element of H. > > Question 4. What is the empty set? > Answer: The empty set is the set which has no element. > > Question 5. _The_ set? > Answer: Suppose H is a set which has no element and K is a set which has > no > element. Then no element of H is not an element of K and no element of K is > not > an element of H -- because there is no element of H or K. By 3, H and K are > the > same set. The _existence_ of an empty set is established in 1 and 2. > > Question 6. What does it mean to say H is a subset of K? > Answer: It means H is a set and K is a set and no element of H is not an > element of K. > > Question 7. Why is the empty set a subset of every set? > Answer: Suppose phi is the empty set and K is a set. phi is a subset of K > because ... (details are left to the reader) > > More questions can be added from standard set theory, like what is the > definition of H less K, H union K, H intersect K, and power set, but you > probably know the questions and the answers. The above questions, about set, > element of, empty set, and subset, are the fundamental ones. > > Closing examples > > ]M =: pwrSet 0;1 > ++---+---+-----+ > ||+-+|+-+|+-+-+| > |||1|||0|||0|1|| > ||+-+|+-+|+-+-+| > ++---+---+-----+ > ]N =: pwrSet 1;0 > ++---+---+-----+ > ||+-+|+-+|+-+-+| > |||0|||1|||1|0|| > ||+-+|+-+|+-+-+| > ++---+---+-----+ > > (realset M),:(realset N) > ++---+-----+---+ > ||+-+|+-+-+|+-+| > |||0|||0|1|||1|| > ||+-+|+-+-+|+-+| > ++---+-----+---+ > ||+-+|+-+-+|+-+| > |||0|||0|1|||1|| > ||+-+|+-+-+|+-+| > ++---+-----+---+ > M equalset N > 1 > M u N > ++---+-----+---+ > ||+-+|+-+-+|+-+| > |||0|||0|1|||1|| > ||+-+|+-+-+|+-+| > ++---+-----+---+ > M eqs M u N NB. eqs is shorthand for equalset > 1 > M eqs E u M NB. E is empty set 0$<1 > 1 > E eqs E n M > 1 > ]S =: 'cdab';((3 4;2 1);5 6) > +----+---------+---+ > |cdab|+---+---+|5 6| > | ||3 4|2 1|| | > | |+---+---+| | > +----+---------+---+ > realset S NB. the nonsets are not sorted; the sets are > +---+----+---------+ > |5 6|cdab|+---+---+| > | | ||2 1|3 4|| > | | |+---+---+| > +---+----+---------+ > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
