! 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 (..<bit>..))

  (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 <seq w duplications> <seq w no duplications>)
! - 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!