! bit.ax.txt - bit and bit-inequality utilities
! uses form.ax, ho.ax.txt?
! -- helpful to have higher-order!
!/
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
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
===== negative (bit-distinguishable) binary relations =====
/prefix - arg 1 sequence is not a prefix of arg 2 sequence
/suffix - arg 2 sequence is not a suffix of arg 1 sequence
===== 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
--- tbd:
(merge ) - merge ordered sequences (given bit ordering)
(merge_op < <=op> ) - merge given ordering ops
(sort ) - sort a sequence of elements based on bit <
(sort_op < <=op> ) - sort given ordering ops
(par_sort ( ..data..) ( ..data'..)) - parallel-sort data seqs
(in_ ) - expr in sequence, but only one solution
- [only_]one_in or unique_in
(prefix (..x..) (..)) - bit expr prefix up to
(remove ) - remove 1st occurrence of expr from seq
(dup_elim ) - elim duplicate exprs in seq, keeping first occur
(dup_elim_front ) - elim dupl exprs in seq, keeping last occur
((subst %ex? %ex') ) - replace with if ==
((replace %ex? %ex') ) - replace with if matches
(replace_head ) - replace head of sequence if match
for eval.ax:
not_member < /in
char_string < charseq
-- also see eval.ax utilities:
member?, ==?, prefix?, , >= - reverse of <, <=
(def > (rev <)).
(def >= (rev <=)).
!or
(> %2 %1)< (< %1 %2).
(>= %2 %1)< (<= %1 %2)..
! ordered - adjacent sequence elements have <= bit-ordering relation
(def ordered (seq <=)).
!or:
(ordered ()). ! empty sequence is ordered
(ordered (%)). ! singleton sequence is ordered
(ordered (% %0 $))< ! adding element to ordered sequence
(<= % %0),
(ordered (%0 $)).
! /= - inequality based on bits
(/= %1 %2)< (one_valid (< %1 %2) (< %2 %1)).
!or:
(/= %1 %2)< (< %1 %2).
(/= %2 %1)< (< %2 %1).
! /in - element not-in a sequence (based on bit inequality)
(/in %x ()).
(/in %x (% $))< (/= %x %), (/in %x ($)).
!or
(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 _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 o dups
(/in %1 ($seqnd)), ! (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 % ($seqnd)), ! (elem has already occurred)
(dup_elim ($seq) %seqnd).
! sort - 2nd arg is ordering of first arg elements, given <= bit 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)).
! 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 - duplicates ok.)
! (Both substr and subseq imply subset, but not the inverse.)
(def subset all_in).
! -- Do we need this since it is identical to 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).
! -- Do we need this, too??
! ======== negative (bit-distinguishable) binary relations ========
! /prefix - arg 1 sequence is not a prefix of arg 2 sequence
(/prefix (%x $x) ()).
(/prefix (%x $x) (%h $t))<
(/= %x %h).
(/prefix (%x $x) (%h $t))<
(/prefix ($x) ($t)).
! /suffix - arg 2 sequence is not a suffix of arg 1 sequence
(/suffix () ($x %x)).
(/suffix ($f %l) ($x %x))<
(/= %l %x).
(/suffix ($f %l) ($x %x))<
(/suffix ($f) ($x)).
! ======== 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!
!/ ====== tbd:
! --- Merge sort based on bit ordering ---
! merge - merge ordered sequences into ordered sequence (based on <,<=)
(merge () () ()). ! merge of empty sequences gives empty seq
(merge (% $) () (% $)). ! if one seq empty, merge is just the other
(merge () (% $) (% $)).
(merge (%1 $1) (%2 $2) (%1 $))< ! choosing head of 1st seq
(<= %1 %2),
(merge ($1) (%2 $2) ($)).
(merge (%1 $1) (%2 $2) (%2 $))< ! choosing head of 2nd seq
(< %2 %1),
(merge (%1 $1) ($2) ($)).
! Note that if heads identical, 1st sequence head gets chosen.
! merge_op - merge ordered seqs into ordered seq (using specified ops)
(merge_op %< %= () () ()). ! merge of empty sequences gives empty seq
(merge_op %< %= (% $) () (% $)). ! if one seq empty, merge is just the other
(merge_op %< %= () (% $) (% $)).
(merge_op %< %= (%1 $1) (%2 $2) (%1 $))< ! choosing head of 1st seq
(one_valid (%< %1 %2) (%= %1 %2)), ! (1st head < or equivalent to 2nd)
(merge_op %< %= ($1) (%2 $2) ($)).
(merge_op %< %= (%1 $1) (%2 $2) (%2 $))< ! choosing head of 2nd seq
(< %2 %1), ! (2nd head < 1st)
(merge_op %< %= (%1 $1) ($2) ($)).
! Note that if heads equivalent, 1st sequence head gets chosen.
! sort - (merge) sort a sequence based on bit ordering
(sort () ()).
(sort (%) (%)).
(sort (%0 %1 $) %sorted)<
(split (%0 %1 $) %half1 %half2), ! split seq into halves
(sort %half1 %sorted1), ! sort each half
(sort %half2 %sorted2),
(merge %sorted1 %sorted2 %sorted). ! merge the sorted halves
! sort_op - (merge) sort a sequence based on specified <,= ordering operations
(sort_op %< %= () ()).
(sort_op %< %= (%) (%)).
(sort_op %< %= (%0 %1 $) %sorted)<
(split (%0 %1 $) %half1 %half2), ! split seq into halves
(sort_op %< %= %half1 %sorted1), ! sort each half
(sort_op %< %= %half2 %sorted2),
(merge_op %< %= %sorted1 %sorted2 %sorted). ! merge the sorted halves
! par_sort - parallel sort data sequences based on sort of keys
(par_sort %null_seqs %null_seqs)< ! if key/data seqs null, nothing done
(null_seqs %null_seqs).
(par_sort (%keys $data) (%keys' $data'))< ! seqs are non-empty
(transpose (%keys $data) %seqs), ! merge keys and data into sequences
(sort_op <1 =1 %seqs %seqs'), ! sort sequences based on keys
(transpose %seqs' (%keys' $data')). ! get sorted keys and data sequences
! prefix -- function returns sequence prefix up to a terminating expression
! - no solution if terminating prefix not present
(prefix (%x $) %x ()). ! terminating expr at front of sequence
(prefix (% $1) %x (% $2))<
(/= % %x), ! prefix consists of non-%x expressions
(prefix ($1) %x ($2)).
! prefix? -- test if one string is a prefix of another, returning true/false
! -- see eval.ax
! remove - remove first occurrence of an expression from a sequence
! - no solution if expression not present
(remove %x (%x $) ($)).
(remove %x (% $) (% $'))<
(/= %x %),
(remove %x ($) ($')).
! dup_elim - eliminate duplicate exprs in a sequence, keeping first occurrence
(dup_elim %seq %unique)<
(reverse %seq %seq_rev),
(dup_elim_front %seq_rev %unique_rev),
(reverse %unique_rev %unique).
! dup_elim_front - elim duplicate exprs from front of seq, keeping last occur
(dup_elim_front () ()).
(dup_elim_front (% $) ($'))< ! dupl expr not included
(in_ % ($)), ! head expr occurs in seq tail
(dup_elim_front ($) ($')).
(dup_elim_front (% $) (% $'))< ! unique expr is included
(/in % ($)), ! head expr does not occur in seq tail
(dup_elim_front ($) ($')).
! subset - a sequence is a subset of another
! (The subset may have multiple occurrences of an element.)
(subset () ($set)). ! empty set is a subset
(subset (% $) %set)< ! adding element to subset
(in_ % %set), ! new element is set member (single solution)
(subset ($) %set).
! /subset - sequence is not a subset of another
(/subset (%x $) %set)<
(/in %x %set). ! element not member of set
(/subset (% $) %set)<
(in_ % %set), ! (we want just a single solution)
(/subset ($) %set).
! replace - replace an expression if matched to another
! ((replace %ex? %ex') ) - replace with if ==
! - note that substitution parameters are incorporated into predicate name expr
((replace %ex? %ex') %ex? %ex'). ! arg expr is matched, replacement done
((replace %ex? %ex') %ex %ex)< ! no match, no replacement
(/= %ex? %ex).
! replace_head - replace head of sequence if match
! (replace_head ) - replace head of sequence if match
(replace_head (%h1 $tail) %h? %h' (%h2 $tail))<
((replace %h? %h') %h1 %h2).