B.2 Insert

This function is mentioned in Sort, on sorting. It takes the virtual code for a partial order relational operator and returns the code for a function of two arguments. The left argument is a list item and the right argument is a list of items of the same type, which is already sorted with respect to the relational operator given as the argument to insert. The result of the function returned by insert is a list similar to its right argument but with the left argument inserted in the proper position to maintain the order.

This code makes use of the self, argument, head and tail declarations associated with pairwise.

insert =

bu(compose,refer) (hired conditional)(
   constant compose(right,argument),
   couple(
      (hired conditional)(
         (hired compose)(
            identity,
            constant compose(
               couple(left,compose(head,right)),
               argument)),
         constant (
            argument,
            couple(
               compose(head,compose(right,argument)),
               (hired meta)(
                  self,
                  couple(
                     compose(left,argument),
                     compose(tail,compose(right,argument))))))),
      constant argument))

As with the other higher order functions in this appendix, the only feasible ways to verify it would be either by formal proof or by some form of symbolic interpretation.

This document was generated on December 10, 2012 using texi2html 1.82.