! bit.ax.txt - bit and bit-inequality utilities
! uses ho.ax.txt - higher-order utilities
----+----|----+----|----+----|----+----|----+----|----+----|----+----|----+----8
!/ uses form.ax, ho.ax ...
bit0,bit1,bits - bit atoms
bit - set of bit atoms
bitseq - sequence of bits
< - ordering of bit exprs (where bits can be compared lexicographically)
<= - (bit) ordering from < and ==
>, >= - reverse of <, <=
ordered - sequence elements have <= bit-ordering relation
/= - inequality based on bits
/in - element not-in a sequence (based on bit inequality)
distinct - all elements of a sequence are bit-distinguishable
dup_elim - eliminate duplicate elements from a sequence (=> bit distinct)
sort - 2nd arg is ordering of first arg elements, given <= relation
all_in - all arg 1 elements are 'in' arg 2 sequence
some_in - at least one arg 1 elem is 'in' arg 2 sequence
none_in - no arg 1 elem is 'in' arg 2 sequence
all_/in - all arg 1 elements are not-in arg 2 sequence
some_/in - at least one arg 1 elem is not-in arg 2 sequence
subset - arg 1 is subset of arg 2
/subset - arg 1 is not subset of arg 2
===== bit-distinguishable binary operations ...
add_elem - append an element to a set if not already there
union - union of set-seqs of bit distinguishable elements
intersect - intersection of set-seqs of bit distinguishable elements
difference - difference of set-seqs of bit distinguishable elements
!\
! bit0, bit1, bits - bit atoms
(bit0 `0).
(bit1 `1).
(bits %bit0 %bit1)< (bit0 %bit0), (bit1 %bit1).
! - alternate bit representations could be atom `bit0 or symbols 0, bit0
! bit - set of bit atoms
(bit %bit)< (in %bit ($bits)), (bits $bits).
! bitseq - sequence of bits
! (bitseq (....))
(def bitseq (* bit)).
! < - ordering of bit exprs (based on bit ordering)
(< %bit0 %bit1)< (bits %bit0 %bit1). ! bit atoms are ordered
(< () (% $)). ! lexicographic ordering
(< (%1 $1) (%2 $2))< (< %1 %2).
(< (% $1) (% $2))< (< ($1) ($2)).
! <= - ordering from <, ==
(<= %1 %2)< (one_valid (< %1 %2) (== %1 %2)).
! >, >= - reverse of <, <=
(def > (rev <)).
(def >= (rev <=)).
! ordered - adjacent sequence elements have <= bit-ordering relation
(def ordered (seq <=)).
! /= - inequality based on bits
(/= %1 %2)< (one_valid (< %1 %2) (< %2 %1)).
! /in - element not-in a sequence (based on bit inequality)
!z (/in %x ()).
!z (/in %x (% $))< (/= %x %), (/in %x ($)).
(def /in (1* /=)).
! distinct - all elements of a sequence are bit-distinguishable
(def distinct (seq* /=)). ! bit-inequality rel applies between all elem pairs
! dup_elim - eliminate duplicate elements from a sequence (=> bit distinct)
! (dup_elim )
! - note that we keep the original element order
(dup_elim () ()).
(dup_elim ($seq %1) ($seqnd %1))< ! 1st occur of a new elem
! - appended to both orig seq and seq with no dups
(/in %1 ($seq)), ! (elem hasn't occurred before)
(dup_elim ($seq) ($seqnd)).
(dup_elim ($seq %) %seqnd)< ! elem occurs again
! - appended to orig seq but not to seq with no dups
(in % ($seq)), ! (elem has already occurred)
(dup_elim ($seq) %seqnd).
! sort - 2nd arg is ordering of first arg elements, given <= relation
(sort %seq %sorted)<
(perm %seq %sorted),
(ordered %sorted).
! - Other ordering relations will need stable sort!
! all_in - all arg 1 elements are 'in' arg 2 sequence
(def all_in (*1 in)).
! some_in - at least one arg 1 elem is 'in' arg 2 sequence
(def some_in (^1 in)).
! none_in - no arg 1 elem is 'in' arg 2 sequence
(def none_in (*1 /in)).
! all_/in - all arg 1 elements are not-in arg 2 sequence
(def all_/in (*1 /in)).
! some_/in - at least one arg 1 elem is not-in arg 2 sequence
(def some_/in (^1 /in)).
! subset - arg 1 is subset of arg 2 (synonym of all_in)
! (All arg 1 elements are in arg 2 - dups ok.)
! (Both substr and subseq imply subset, but not the inverse.)
(def subset all_in).
! /subset - arg 1 is not subset of arg 2 (synonym of some_/in)
! (At least one arg 1 element is not in arg 2.)
(def /subset some_/in).
! ======== bit-distinguishable binary operations ========
! add_elem - append an element to a sequence set if not already there
(add_elem ($set) %x ($set))< ! already there - not added
(in %x ($set)).
(add_elem ($set) %x ($set %x))< ! not already there - added
(/in %x ($set)).
! - equivalent to (union %set (%x) %set') except arg 1 set dups not eliminated
! union - union of set-seqs of bit distinguishable elements
! (Arguments may have duplications, but result does not. Result element
! order is order of arg 1 set, then arg 2 set.)
(union ($set1) ($set2) %union)<
(dup_elim ($set1 $set2) %union).
! -- note that union order is 1st occurrence in arg 1, then arg 2
! intersection - intersection of set-seqs of bit distinguishable elements
! (arguments may have duplications, but result does not)
! (order of intersection is arg 1 order)
(intersection () ($set2) ()).
(intersection ($set1 %1) %set2 %iset')<
(intersection ($set1) %set2 %iset),
(in %1 %set2), ! new element also in set 2
(add_elem %iset %1 %iset'). ! append shared elem if not already there
(intersection ($set1 %1) %set2 %iset)<
(intersection ($set1) %set2 %iset),
(/in %1 %set2). ! new element not in set 2, so not in intersection
! difference - difference of set-seqs of bit distinguishable elements
! (arguments may have duplications, but result does not)
! (order of difference is arg 1 order)
(difference () ($set2) ()).
(difference ($set1 %1) %set2 %dset')<
(difference ($set1) %set2 %dset),
(/in %1 %set2), ! new element not in set 2
(add_elem %dset %1 %dset'). ! append difference elem if not already there
(difference ($set1 %1) %set2 %dset)<
(difference ($set1) %set2 %dset),
(in %1 %set2). ! new element is in set 2, so not in difference
! *** "Bag" operations could be interesting!