## Saturday, August 13, 2016

### Instructions to create and manipulate sets

The basic words for sets are

member \ element set -- flag
set= \ set1 set2 -- flag
subset \ set1 set2 -- flag

The parameters on the left sides above are located on the zst-stack. The 'element' could be a single (on the zst-stack) or a set. The flag is true or false on the ordinary stack. To check if a non negative single number on the parameter stack is a member in a set (located on the zst-stack), use the word

smember \ n set -- flag

3 { 1 2 3 4 } smember . -1  ok

Using member

3 >zst { 1 2 3 4 } member . -1  ok

Except from set operations like

union \ s1 s2 -- s3
intersection \ s1 s2 -- s3
diff \ s1 s2 -- s3
powerset \ s1 -- s2     (s2 = set of all subsets of s1)
cartprod \ s1 s2 -- s3  (Cartesian product)
cardinality \ s1 -- n   (n = number of elements in s1)

and the possibility to create small sets

{ 10 10000 | prime } cardinality . 1225  ok

there are a lot of cryptic words to manipulate even rather big sets of non negative integers

intcond \ low hi xt -- | -- s   "intervall condition"
setcond \ xt -- | s -- s'       "set condition"
intimage \ low hi xt -- | -- s  "intervall image"
setimage \ xt -- | s -- s'      "set image"
paircond \ xt -- | s -- s'
pairimage \ xt -- | s -- s'
int2cond \ low hi n xt -- | -- s   "intervall two-condition"
int2image \ low hi n xt -- | -- s  "intervall image"
set2cond \ n xt -- | s -- s'       "set condition"
set2image \ n xt -- | s -- s'      "set image"

Inspired by the idea of orthogonal instructions I created a simple syntax just for set manipulations, to summarize and simplify the use of the words above:

variable zp

variable cf2

: condition  ' 0 cf2 ! sp@ zp ! ;
: function  ' 2 cf2 ! sp@ zp ! ;
: 2dim  ' -1 cf2 ! sp@ zp ! ;
: syntax  sp@ zp @ - 0= if 0 0 else 1 then cf2 @ ;

The word syntax check the number of input parameters and put a dummy parameter on the stack when needed.

(I have started to use the ANS-Forth notation for locals and will reform the code and the blog. It's awkward, but "forthish" awkward since it loads the parameters in the reversed direction:

k l m n locals| n m l k |

It has some advantages even if it looks strange.)

The ten cryptic words are now squeezed into the three words

create-set
filter-set
transform-set

\ e.g. 1 20 condition < 7 create-set

: create-set \ m n xt nr -- set
syntax locals| cf k nr xt n m |
k cf or
case 0 of m n xt intcond endof
1 of m n nr xt int2cond endof
2 of m n xt intimage endof
3 of m n nr xt int2image endof
endcase ;

\ e.g. condition > 5 filter-set
: filter-set \ set xt nr -- set'
syntax locals| cf k nr xt |
cf 0< if xt paircond exit then k
case 0 of xt setcond endof
1 of nr xt set2cond endof
endcase ;

\ e.g. 2dim + transform-set
: transform-set \ set xt nr -- set'
syntax locals| cf k nr xt |
cf 0< if xt pairimage exit then k
case 0 of xt setimage endof
1 of nr xt set2image endof
endcase ;

Creating sets:

1 25 condition prime create-set cr zet.

{2,3,5,7,11,13,17,19,23} ok

10 29 condition coprime 6 create-set cr zet.
{11,13,17,19,23,25} ok

1 10 function 2* create-set cr zet.

{2,4,6,8,10,12,14,16,18} ok

1 10 function * 3 create-set cr zet.
{3,6,9,12,15,18,21,24,27} ok

The word after condition/function must be a defined condition or function for one or two parameters.

Filter sets:

{ 1 25 | all } condition odd filter-set cr zet.
{1,3,5,7,9,11,13,15,17,19,21,23} ok

{ 1 25 | all } condition < 10 filter-set cr zet.
{1,2,3,4,5,6,7,8,9} ok

{ 1 2 3 } zdup cartprod zdup cr zet.
{(3,3),(3,2),(3,1),(2,3),(2,2),(2,1),(1,3),(1,2),(1,1)} ok
2dim < filter-set cr zet.
{(1,2),(1,3),(2,3)} ok

Transform sets:

{ 1 100 | prime } function 2* transform-set  ok
function 1- transform-set  ok
condition prime filter-set cr zet.
{3,5,13,37,61,73,157,193} ok

1 1000000 condition prime create-set  ok
condition < 50 filter-set  ok
function + 2 transform-set cr zet.
{4,5,7,9,13,15,19,21,25,31,33,39,43,45,49} ok

{ 1 10 | odd } zdup cartprod  ok
2dim + transform-set cr zet.
{2,4,6,8,10,12,14,16,18} ok

The word 2dim works like condition and function but acts on a set of pairs and can be used both for 2-dim conditions and 2-dim functions.

So far those instructions don't works in definitions and they just works for numbers and pairs of numbers.