Set ordering

Unlike in classical set theory, sets in Rax are ordered. Every set expression has an associated ordering. For example both the expressions `{1..6}` and ```A >< B``` have an associated ordering. Set ordering in Rax is weak, which means that two sets can be equal, even if their ordering differs. Order of a set is defined in the following way:

• The elements of literal sets (e.g., ```{"aap", "noot", "mies", "does"}``` or `{1..10}`) and sets read from a file are ordered in the way they are given. For example, the first element of the set ```{"aap", "noot", "mies", "does"}``` is `"aap"` and the last element is `"does"`. The first element of the set `{1..10}` is `1`, etc. We call this ordering given order.

• Sets can be ordered explicitly by using the postfix `!` operator (order by). We call this ordering explicit order. For example, the result of the expression `S![.#1]` is a set with the same elements as set `S`, but ordered on the first tuple field. `T![.#2, .#1]` returns a set with the same elements as `T`, but ordered on the second field, and then the first field, etc. :

```    {#}: S := {5,7,19,3,17,13,2,11};
{[#,#]}: T := {[2,3],[1,4],[4,1],[3,1]};

// Print in explicit order.
{#}: S' := S![.#1];                       // S' becomes a sorted S.
`print S';                                // Output: {2,3,5,7,11,13,17,19}
`print T![.#2, .#1];                      // Output: {[3,1],[4,1],[2,3],[1,4]}
`print S == S';                           // Output: true
```

Note that in the example above that 'S' and 'S'' have the same type and can thus be meaningfully compared and that 'S' and 'S'' are considered equal because they have the same elements.

• For every operator and function that takes sets as arguments and returns a set, there is a well defined resulting order that is based on the ordering of the arguments. For example, `select` preserves the order of its argument. Continuing the previous example:

```    `print select [.#1 > 10] S;               // Output: {19,17,13,11};
`print select [.#1 > 10] S';              // Output: {11,13,17,19};
```

Table 8.4, “Resulting order” describes the result order for all set operators in Rax.

• Finally, sets for which the ordering cannot be determined using any of the above rules, are ordered by sorting on all tuple fields from the first to the last. We call this natural ordering. The most important class of such sets, are sets created by mapping an SQL table onto a Rax set using the `import` operator. For example:

```     {[\$:name, #:dept_id]}: people := import [(\$)"NAME", (#)"DEPT_ID"] "T_PEOPLE";
```

The set `people` will be ordered first on `name` and then on `dept_id`. Most operations on sets with natural ordering will return a set with natural ordering.

`![]` (Order-by operator)

As mentioned before, the postfix operator '!' (order by) is used to change the sorting order of an ordered set. If it is an ordered set of tuples, the set can be sorted on the fields of the tuple. For example:

```    `print people![.dept_id, .name];
```

Will print the contents of the set `people` sorted first on the department ID, and then on the name.

Sorting, by default, is ascending, that is from smallest to biggest. To sort in descending order, you can append a '-' sign to the field selector, see example below:

```    {#}: P := {5,7,19,3,17,13,2,11};
P := P![-.#1];                            // Sort P descending.
`print P;                                 // Output: {19,17,13,11,7,5,3,2}
```

Note how the new value for `P` is sorted in descending order.

Sorting can also be done on multiple fields as shown in the example below:

```    {[#:a,#:b,\$:c,&:d]}: U := {[2,3,"k",6.1],[1,3,"l",1.1],[4,1,"m",1.1]};
U := U![.b,-.c,.a];
`print U[2];                       // Output: [a: 1, b: 3, c: "l", d: 1.1]
```

To specify ordering fields, you can also use ranges:

```    {[#:a,#:b,\$:c,&:d]}: U := {[2,3,"k",6.1],[1,3,"l",1.1],[4,1,"m",1.1]};
\U: U';

U' := U![.a .. .c];               // Order on fields a, b, c
U' := U![.c ..];                  // Order on fields c, d
U' := U![.. .c];                  // Order on fields a, b, c
U' := U![..];                     // Order on all fields
U' := U![.c, ..];                 // Order on c and then all fields
U' := U![-.c ..];                 // Order descending on fields c, d
U' := U![-..];                    // Order descending on all fields
```

Ranges can be open-ended, for example `.. .c` means all fields up to field `c` and ```.c ..``` means all fields starting from field `c`. A range open on both ends, `..`, means all fields. Just like individual fields, ranges can be made descending by prepending a `-`.

Note that, especially when using ranges, some fields might be used more than once in an ordering specification. For example, in `[.c, ..]`, `c` is used twice. This is perfectly legal in Rax. The second and later occurrences of a field will be ignored, though, since they don't impact the actual ordering. In such situations, Rax issues a warning. If a field is reused explicitly, like so: ```[.c, .a, .c]```, a warning at level 3 will be issued. If a field is reused in a range, a warning at level 4 will be issued. Warnings at level 4 are not normally shown. All of the order-by statements in the below example will trigger a warning.

```    {[#:a,#:b,\$:c,&:d]}: U := {[2,3,"k",6.1],[1,3,"l",1.1],[4,1,"m",1.1]};

U := U![-.., .#1];                        // Warning at level 3.
U := U![-.#1, .#1];                       // Warning at level 3.
U := U![.#1, -.#1];                       // Warning at level 3.
U := U![.#1, .#1];                        // Warning at level 3.
U := U![.#1.., .#1];                      // Warning at level 3.

U := U![-.a,-b,-c,..];                    // Won't show a warning.
U := U![-.a..,-b..,..-c,..];              // Won't show a warning.

%warn 4;                                  // Up the warning level.
%warn ("Warning level at 4 now.");        // Warn about the high warning level.
U := U![-.a,-b,-c,..];                    // Warning at level 4.
U := U![-.a..,-b..,..-c,..];              // Warning at level 4.
%warn 3;                                  // Set the warning level back to 3.
```

The `%warn 4` command raises the warning level to 4, which causes displaying more warnings. This sometimes can help you to find out why Rax code does not behave as expected.

The set order defined with the order-by operator is not always total. Total order, is an order in which for every two elements `a` and `b`, either `a` precedes `b` or `b` precedes `a` or `a` equals `b`. In other words, total order is an order under which all elements are comparable[11]. If not all tuple fields are used in the order definition, and some tuples in the set are equal on the ordering fields, but not equal on other fields, these tuples will not be comparable under such ordering. This means that the result of expressions, for which order matters, for example set indexing expressions or ``print` calls, even between two consecutive calls. For example:

```    {[#,#]}: S := {[1,2],[1,1],[2,1],[2,2]};
\S: S' := S![.#1];
`print S';
```

The result of the print statement can be either of the following:

```    #1|#2    #1|#2    #1|#2    #1|#2
--|--    --|--    --|--    --|--
1| 1     1| 2     1| 1     1| 2
1| 2     1| 1     1| 2     1| 1
2| 1     2| 1     2| 2     2| 2
2| 2     2| 2     2| 1     2| 1
```

In practice, the order will only be different for different database back ends, but bear in mind that in case of non-total orders, the result of certain expressions cannot be relied upon.

Resulting order

In Rax, many expressions will return an ordered set. Every (valid) expression has a result type. Analogously, every (valid) expression that returns an ordered set has an result order. For example the order of a set returned by a `project` is the same as the order of the input set, see example below.

```    {#}: A := {5,6,7,8,1,2,3,4};
`print project [.#1 + 1] A;                   // Output: {6,7,8,9,2,3,4,5}

A := {1,2,3,4,5,6,7,8};
`print project [.#1 + 1] A;                   // Output: {2,3,4,5,6,7,8,9}
```

Note the order of the two output lines.

The table below describes the resulting order of expressions that (can) return an ordered set.

Table 8.4. Resulting order

ExpressionResulting Order
`A @? B` A temporal semi-touch will have the same ordering as the left hand side oset `A`. Note the temporal semi-touch is a special form of `select[]`.
`A @! B` A temporal anti-touch will have the same ordering as the left hand side oset `A`. Note the temporal anti-touch is a special form of `select[]`.
`b ? A : B` The immediate if (IIF) does not affect the order of its arguments. If oset `A` is returned its order is unchanged, the same goes for oset `B`. Note that the IIF operator is the only operator where the type of the resulting order depends on the value of a non-oset (i.e., boolean) type expression (`b`). This allow runtime control over the ordering of sets. For example with code like this: `reverse ? A![-.#0] : A![.#0]`.
`@\/ A` The (unary) temporal union will always return a result that is ordered naturally. It cannot uphold given-order because it aggregates rows and it cannot honor explicit order since the ordering columns might not be in the resulting table.
`A @!? B` A temporal anti-semi-touch will have the same ordering as the left hand side oset `A`.
`!A` The unique operator respects explicit order so if input oset `A` has been explicitly ordered, the resulting order of the expression will have the same explicit order. When the input `A` has a given order, the result will also have a given order. The resulting order is determined by removing all the repeat values but the first. E.g., `!{1,5,1,4,1,3,1,2,1,1}` will be ordered as such: `{1,5,4,3,2}`. Otherwise, the resulting order will be natural. Note that unique is based on value compares of the back-end database system. This can lead to "surprising" results, most common of which is case-insensitive compare. Dependent on the default collation and other settings in the back end, `!{"a", "A"}` could result in any of these three results: `!{"a", "A"}`, `!{"a"}`, or `!{"A"}`. Tough never in `!{"A", "a"}`.
`\/ A` If all the sets in the set-of-sets `A` have the same explicit ordering the resulting set will have that same explicit ordering. If all sets in the meta set `A` have given order and the meta set `A` itself is also in given order, then the resulting order will be given order too, where the elements of the resulting set are ordered first on their given position in the meta set and second on their given position in the sub set. E.g. the expression `\/{{1,2},{3,4},{0,-3}}` will result in the set ordered like this: `{1,2,3,4,0,-3}`. Any other ordering of the meta set `A` or any of its sub sets, will cause the result to have natural order.
`/\ A` If all the sets in the set-of-sets `A` have the same ordering the resulting set will have that same ordering. If not, the result will have the natural order.
`A /\ B` If both sets `A` and `B` have the same explicit ordering the resulting set will have that same explicit ordering. If not, the result will have the natural order. Note that if both arguments `A` and `B` have a given order, the result will be in natural order, even if the effective given order would coincide.
`A \/ B` If both sets `A` and `B` have the same ordering the resulting set will have that same ordering. If not, the result will have the natural order.
`A![` <fields> `]` After ordering a set explicitly with the `![` <fields> `]` postfix operator, the resulting set will be in the explicit order, unless the row number field is used, e.g., `![.#0]`. In that case, the resulting order will be as if the current order of `A` had been explicitly given. To mimic the default natural order explicitly, use all fields from low to high or the total range, e.g., `![..]`. To reverse any order, use: `![-.#0]`.
`A[` <range> `]` A range of an ordered set will have the same ordering as the input oset `A`. Note, this goes for both for open ended ranges like `A![..5]` as well as closed ranges like `A![222..444]`. Note that a range is a special case of `select[]`.
`project[` <exps> `] A` If the `A` set is in given order, the result of the project will be in that same order. Any other ordering will be ignored and the result will have the default natural ordering. E.g., `project[(\$)(-3*.#1)] {-1,4,0}` will be ordered like `{"3","-12","0"}` but `project[(\$)(-3*.#1)] {-1,4,0}![-.#1]` would be naturally ordered like so `{"-12","0","3"}`.
`fold[` <exps> `] A` The fold operator can return an oset, in which case this oset will be always naturally ordered. Fold cannot uphold given order because it aggregates rows and it cannot honor explicit order since the ordering fields might not be in the result.
`select[` <exps> `] A` The resulting oset will have the same ordering as the input set `A`. For example the expression `select[.#1 % 2 != 0] {1,8,3,8,23,0,5,7}` would be ordered as if the even numbers were taken out: `{1,3,23,5,7}`.
`{` <ranges> `}` A literal oset will always be in given order. Ranges can be given high to low, e.g., `4..2` these will be ordered from high to low as well. So the literal oset `{4..5,9..8,77,2..-2}` would be ordered like this: `{4,5,9,8,77,2,1,0,-1,-2}`.
`A |><| B` If two explicitly ordered sets, `A` and `B`, join naturally, the resulting set is explicitly ordered on all the fields `A` and `B` are ordered on minus the fields from `B` that are already in `A`. For example, with `A` and `B` defined as `{[@:a*2,#:b*4,\$:c*3,^:d*2]}: A;`, `{[#:b,\$:a,#:b*2,|:s,#:c,?:d]}: B;` and sorted with `A := A![.c,.b,.d]` and `B := B![.s,.b#3,.c,.b]` the natural join `A |><| B`, would have a resulting order as if ordered by `![.c,.b,.d,.s,.b#3]`. If either or both of the arguments are not ordered explicitly, the resulting set will be ordered naturally.
`A` α <exps> Auto-iteration will only respect given order of the input set `A`. Any other ordering will be ignored and the default natural order is used. E.g., `-1 * {1,-4,5,3,77}` will be ordered like `{-1,4,-5,-3,-77}` but `-1 * {1,-4,5,3,77}![-.#1]` would be naturally ordered like so `{-77,-5,-3,-1,4}`. The operator α (e.g., `+`, `:/`, etc.) cannot affect the resulting order and neither can iterated function calls. Note that auto-iteration is a special case of `project[]`.

[11] Note, that the given order and the natural order are always total.