Set: Difference between revisions
Added second method to Quackery
(Added Quackery.) |
(Added second method to Quackery) |
||
Line 4,720:
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
Line 4,781 ⟶ 4,791:
else subset ] is propersubset ( { { --> b )
( ------------------------------ demo ------------------------------ )
set{ red orange green blue
Line 4,821 ⟶ 4,832:
{ 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
{ 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
fruits and colours are not exactly the same
| |||