Set: Difference between revisions
Content added Content deleted
(Added Quackery.) |
(Added second method to Quackery) |
||
Line 4,720: | Line 4,720: | ||
Sets are not implemented in Quackery, so we start with an implementation of sets as sorted nests of strings without duplicates. |
Sets are not implemented in Quackery, so we start with an implementation of sets as sorted nests of strings without duplicates. |
||
This was the first pass at coding sets. I felt that bitmap sets were the way to go, but I wanted to get my head around the problem space and fill in a gap in my understanding, specifically pertaining to bignum bitmaps and the universal set. By the time I had coded an inefficient version that avoided the issue, I realised the solution - we don't need to accommodate everything, just everything we know about so far. So in the second version the ancillary stack <code>elements</code> holds a nest of the names of every set element we know of so far, and the word <code>elementid</code> returns the position of an element in that nest, if it has been encountered before, and adds it to the nest if it is previously unknown, then returns its position. |
|||
In both versions, a set element is any string of non-whitespace characters apart from "}set". If you desperately need set elements with spaces or carriage returns, or called "}set" there are workarounds. |
|||
Use the second version, it's a lot more efficient and the set of everything so far encountered is available if wanted. It's <code>[ elements share size bit 1 - ]</code>. |
|||
The set of everything is -1, just don't try to enumerate it; your program will crash when it gets to naming things it hasn't heard of. |
|||
===Sorted Nests of Strings=== |
|||
<lang Quackery> [ [] $ "" rot |
<lang Quackery> [ [] $ "" rot |
||
Line 4,781: | Line 4,791: | ||
else subset ] is propersubset ( { { --> b ) |
else subset ] is propersubset ( { { --> b ) |
||
( ------------------------------ demo ------------------------------ ) |
|||
set{ red orange green blue |
set{ red orange green blue |
||
Line 4,821: | Line 4,832: | ||
{ apple banana blue green melon pear purple red } are fruits or colours but not both |
{ apple banana blue green melon pear purple red } are fruits or colours but not both |
||
{ apple banana melon pear } are fruits that are not colours |
{ apple banana melon pear } are fruits that are not colours |
||
{ blue green red } are all colours |
|||
fruits and colours are not exactly the same |
|||
orange is a fruit |
|||
{ orange } is not the only fruit</pre> |
|||
===Indexed Bitmaps=== |
|||
<lang Quackery> [ stack [ ] ] is elements ( --> s ) |
|||
[ elements share 2dup find |
|||
dup rot found iff nip done |
|||
swap elements take |
|||
swap nested join |
|||
elements put ] is elementid ( $ --> n ) |
|||
[ 0 temp put |
|||
[ trim |
|||
dup $ "" = if |
|||
[ $ '"set{" without "}set"' |
|||
message put bail ] |
|||
nextword |
|||
dup $ "}set" = iff drop done |
|||
elementid bit |
|||
temp take | temp put |
|||
again ] |
|||
temp take |
|||
swap dip |
|||
[ nested nested join ] ] builds set{ ( [ $ --> [ $ ) |
|||
[ [] 0 rot |
|||
[ dup while |
|||
dup 1 & if |
|||
[ over elements share |
|||
swap peek nested |
|||
swap dip |
|||
[ rot join swap ] ] |
|||
dip 1+ |
|||
1 >> |
|||
again ] |
|||
2drop ] is set->nest ( { --> [ ) |
|||
[ say "{ " |
|||
set->nest witheach [ echo$ sp ] |
|||
say "}" ] is echoset ( { --> ) |
|||
[ & ] is intersection ( { { --> { ) |
|||
[ | ] is union ( { { --> { ) |
|||
[ ^ ] is symmdiff ( { { --> { ) |
|||
[ tuck intersection symmdiff ] is difference ( { { --> { ) |
|||
[ over intersection = ] is subset ( { { --> b ) |
|||
[ dip [ elementid bit ] subset ] is element ( $ { --> b ) |
|||
[ 2dup = iff |
|||
[ 2drop false ] |
|||
else subset ] is propersubset ( { { --> b ) |
|||
( ----------------------------- demo ---------------------------- ) |
|||
set{ red orange green blue |
|||
purple apricot peach }set is colours ( --> { ) |
|||
set{ apple peach pear melon |
|||
apricot banana orange }set is fruits ( --> { ) |
|||
colours dup echoset say " are colours" cr |
|||
fruits dup echoset say " are fruits" cr |
|||
2dup intersection echoset say " are both fruits and colours" cr |
|||
2dup union echoset say " are fruits or colours" cr |
|||
2dup symmdiff echoset say " are fruits or colours but not both" cr |
|||
difference echoset say " are fruits that are not colours" cr |
|||
set{ red green blue }set dup echoset say " are" |
|||
colours subset not if [ say " not" ] say " all colours" cr |
|||
say "fruits and colours are" fruits colours = not if [ say " not" ] |
|||
say " exactly the same" cr |
|||
$ "orange" dup echo$ say " is" |
|||
fruits element not if [ say " not" ] say " a fruit" cr |
|||
set{ orange }set dup echoset say " is" |
|||
fruits propersubset dup if [ say " not" ] say " the only fruit" |
|||
not if [ say " or not a fruit" ] cr</lang> |
|||
{{out}} |
|||
<pre>{ peach apricot purple blue green orange red } are colours |
|||
{ banana melon pear apple peach apricot orange } are fruits |
|||
{ peach apricot orange } are both fruits and colours |
|||
{ banana melon pear apple peach apricot purple blue green orange red } are fruits or colours |
|||
{ banana melon pear apple purple blue green red } are fruits or colours but not both |
|||
{ banana melon pear apple } are fruits that are not colours |
|||
{ blue green red } are all colours |
{ blue green red } are all colours |
||
fruits and colours are not exactly the same |
fruits and colours are not exactly the same |