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
