Direct access selectors

All implementations of Refal Plus enable quick and "cheap" direct access to the top-level terms of a ground expression, which turns out to be useful for solving problem by means of the technique known as "divide and conquer".

The general idea is to solve a problem by dividing it into subproblems - each an instance of the original problem but on inputs of smaller size - in such a way that the solution of the original problem can be assembled from the solutions to the subproblems. The principle "divide and conquer" is usually applied together with the principle of "balancing" requiring that the original problem should be divided into subproblems of roughly equal size [AHU1974].

A classic application of the principle "divide and conquer" is the problem of sorting (i.e. arranging in ascending order).

One of the sorting methods is the merge sort [AHU1974]. The idea is to divide the original set S into two disjoint sets S1 and S2 of roughly equal size, sort S1 and S2 to produce two ordered sequences Q1 and Q2, and then merge Q1 and Q2 into one ordered sequence Q, thereby obtaining the solution to the original problem.

Now let us define the function MSort, which takes an integer sequence as argument, divides it into two parts of approximately equal size, and calls itself recursively in order to sort both parts. Then the sequences thus obtained are merged by the function Merge to produce the final result.

$func MSort eS = eS;
$func Merge (eX)(eY) = eZ;

MSort  eS =
  <Length eS> :: sLen,
  {
  <Le (sLen) (1)>
    = eS;
    = <Div sLen 2> :: sK,
      <Left 0 sK eS> :: eS1,
      <Middle sK 0 eS> :: eS2,
        <Merge ( <MSort eS1> )( <MSort eS2> )>;
  };

Now we have to define the function Merge, which takes two ordered integer sequences as arguments and merges them into one ordered sequence.

Merge  (eX)(eY) =
  {
  eX :
    = eY;
  eY :
    = eX;
  (eX)(eY) : (sA eXRest)(sB eYRest)
    = {
      <Le (sA)(sB)>
        = sA <Merge (eXRest)(eY)>;
        = sB <Merge (eX)(eYRest)>;
    };
  };