I am going to offer a competing model, which will hopefully clarify or improve
some things.
In this model, a set is simply a list of boxes with no other requirement. Sets
match if each is a subset of the other, and one set is a subset of another if
all of its elements are contained in that set.
Repeating elements is only a dumb way to write something, and can be rectified
with the verb stdform.
Cross product is supported with an arbitrary number of sets--see below.
set=: [: , <"0
empty=: 0$a:
isboxed=: 32 = 3!:0
islist=: 1...@$
isset=: isboxed *. islist
stdform=: /:~...@~.
isstdform=: -: stdform
ismemb=: boxo...@[ e. ]
issub=: *./@:e.
equal=: issub *. issub~
sor=: ,
sand=: [ #~ e.
sdif=: -.
ssymdif=: sor sdif sand
card=: #...@~.
NB. monad: accepts a list of sets in boxes. Take the cross product.
NB. dyad: find the cross product of sets x and y.
cross=: [: ,@{ ,&(] : <)
power=: <@#~ #:@i.@(2^#)
Marshall
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Kip Murray
Sent: Sunday, October 10, 2010 12:02 AM
To: Programming forum
Subject: [Jprogramming] Sets
Here is my latest attempt to model set theory in J. All sets have distinct
elements and are ordered by /:~ so that match -: determines whether two sets
are the same. Sets must be created by the verb set or by provided operations.
The intention is theoretical not practical! --Kip Murray
]A =: set 0;'b';2 NB. elements 0 'b' 2 are put in boxes preceding the last
┌─┬─┬─┬┐ │0│2│b││ └─┴─┴─┴┘
]B =: set 2;'b';'b';0 NB. same elements so same set ┌─┬─┬─┬┐ │0│2│b││
└─┴─┴─┴┘
A -: B
1
]C =: set 2;'b';'c';'d'
┌─┬─┬─┬─┬┐
│2│b│c│d││
└─┴─┴─┴─┴┘
B sand C NB. intersection, "set and"
┌─┬─┬┐
│2│b││
└─┴─┴┘
B sor C NB. union
┌─┬─┬─┬─┬─┬┐
│0│2│b│c│d││
└─┴─┴─┴─┴─┴┘
(A sand B sor C) -: (A sand B) sor (A sand C) NB. distributive law
1
pwrset A NB. A has 3 elements, power set has 2^3, including the empty set
┌──────┬────────┬────┬──────┬────┬──────┬──┬────┬┐
│┌─┬─┬┐│┌─┬─┬─┬┐│┌─┬┐│┌─┬─┬┐│┌─┬┐│┌─┬─┬┐│┌┐│┌─┬┐││
││0│2││││0│2│b││││0││││0│b││││2││││2│b│││││││b││││
│└─┴─┴┘│└─┴─┴─┴┘│└─┴┘│└─┴─┴┘│└─┴┘│└─┴─┴┘│└┘│└─┴┘││
└──────┴────────┴────┴──────┴────┴──────┴──┴────┴┘
NB. Elements are contained in boxes preceding the last which is always
NB. the Boxed Empty a: (Ace). The use of a: permits a unique and visible
NB. empty set, viz
(,a:) -: E =: A less A NB. see verb less below
1
E
┌┐
││
└┘
a:
┌┐
││
└┘
E -: a:
0
NB. Definitions
E =: ,a: NB. empty set
set =: a: ,~ [: /:~ ~. NB. create set from boxed list y
NB. each box of y encloses an element
get =: { }: NB. get boxed elements (from curtail because
NB. elements are inside boxes of curtail)
isin =: e. }: NB. Do boxes in list x contain elements of y?
less =: a: ,~ -.&}: NB. remove elements of y from x
sand =: [ less less NB. intersection, "set and"
sor =: a: ,~ [: /:~ [: ~. ,&}: NB. union, "set or"
diff =: less sor less~ NB. symmetric difference
card =: [: # }: NB. count elements: cardinality
issubs =: [ -: sand NB. Is x a subset of y?
pwrset =: a: ,~ [: /:~ ] (<@#~) 1 (,~"1) 2 (#"1~ {:)@#:@i...@^ #...@}:
NB. pwrset by Raul Miller, adapted
islist =: 1 = #...@$ NB. islist through isunique from validate.ijs
isboxed =: 0 < L.
issorted =: -: /:~
isunique =: -: ~.
isset =: islist *. isboxed *. (a: -: {:) *. issorted@:}: *. isunique@:}:
NB. isset y asks, is array y a set?
iselement =: <@[ isin ] NB. Is array x an element of set y?
NB. End
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
