! form.ax - utility predicates based on the form of expressions


! == - identity relation

  (== % %).

! id - identity function

  (id % %).

 ! -- Same as == but we think of id as the identity function from argument to
 ! a result, while == is an equivalence relation for 2 identical expressions.

! concat - concatenation function
! (concat <seq1> <seq2> <seq1+seq2>)

  (concat ($1) ($2) ($1 $2)).

   !>>> This is called 'append' in traditional LP,
   !    but we use 'concat' to avoid confusion with 'append1':

! generalization of concat to >2 input arguments

  (concat %arg1 %arg2 $args ($) ($res $))<     ! adding an argument
    (concat %arg1 %arg2 $args ($res)).

! concatenation of a sequence of sequences (1-argument case)

  (concat () ()).
  (concat (($) $seqs) ($ $concat))<
    (concat ($seqs) ($concat)).

 ! Generalize other binary operators in this manner?  (plus, and, etc.)
 ! from ho.ax:

   (generalize concat ()).

! append1 - append one value to a sequence

  (append1 ($) % ($ %)).

! front_append - append expression to front of a sequence

  (fappend % ($) (% $)).

! last - last element in a sequence

  (last ($ %) %). 

! head - first element in a sequence

  (head (% $) %).

! tail - rest of a sequence after its head

  (tail (% $) ($)).

! in - expression is in a sequence

  (in % ($1 % $2)).

   !>>> This is called 'member' in traditional LP.

! insert - insert an expression at some (any) point in a sequence

  (insert %x ($1 $2) ($1 %x $2)).

! reverse - reverse a sequence

  (reverse () ()).
  (reverse (% $) ($rev %))<
    (reverse ($) ($rev)).

! zero_or_more - sequence is zero or more occurrences of an expression

  (zero_or_more % ()).
  (zero_or_more % (% $))< (zero_or_more % ($)).

  ! -- better name needed!  closure?

! ldistr - distribute an element over the front of multiple sequences

  (ldistr % () ()).
  (ldistr % (($) $seqs) ((% $) $seqs'))<
    (ldistr % ($seqs) ($seqs')).

  ! -- or could use higher-order definition:

   (ldistr $args)<
     ((1* fappend) $args).

! distr - distribute a sequence of elements over the fronts of sequences
! (Note that this is same as fappend*, once we define the <rel>* mapping
!  (which needs distr in its definition!).)

  (distr () () ()).
  (distr (%el $els) (($seq) $seqs) ((%el $seq) $seqs'))<
    (distr   ($els)        ($seqs)            ($seqs')).

! turn relation <rel> into <rel>* that applies to sequences of arguments

  ((` ($rel '*')) $nulls)< (zero_or_more () ($nulls)).  ! empty arg sequences
  ((` ($rel '*')) $argseqsx)<         ! non-empty arg sequences
    ((` ($rel '*')) $argseqs),
    ((` ($rel)) $args),               ! relation to be mapped
    (distr ($args) ($argseqs) ($argseqsx)).

! all_subsets - set of all subsets of a set (sequence)
! (all_subsets <set> (<subset> ... <subset>))
! -- note that element order is preserved
! -- note that we don't eliminate duplicate subsets (in case some original
!       set elements are the same)
! -- Better name needed to reflect that these are all subsets of elements
!    from the original sequence given in their original order.

  (all_subsets () (())).
  (all_subsets (% $) ($w% $w/o%))<
    (all_subsets ($) ($w/o%)),
    (ldistr % ($w/o%) ($w%)).

!/
  examples:
 
  (all_subsets () (()))        -- just the empty sequence itself

  (all_subsets (a) ((a) ()))

  (all_subsets (a b) ((a b) (a) (b) ()))

  (all_subsets (a b c) ((a b c) (a b) (a c) (a) (b c) (b) (c) ()))

  ...
!\

! insert_between - insert an expression between each element of a sequence
! (We do not insert before first element or after last.)

  (insert_between %x () ()).       ! no insertion here
  (insert_between %x (%) (%)).       ! or here
  (insert_between %x (%' % $) (%' %x $'))<   ! here's where we insert
    (insert_between %x (% $) ($')).

! =length - two sequences are equal length

  (=length () ()).
  (=length (%1 $1) (%2 $2))<
    (=length ($1) ($2)).

! `' - "constant" or "quote" function

  ((`' %) %ignored %).   ! result comes from the function, argument is ignored