How does Query decide the order in which the functions are applied?

Question

First of all I know that Query is a nice way to organize your functions that are applying at specific levels of an expression. But I don't understand the order in which they are applied.

Consider the following dataset as an example.

data={
    <|"field 1"->1,"field 2"->2,"field 3"->3|>,
    <|"field 1"->4,"field 2"->5,"field 3"->6|>,
    <|"field 1"->7,"field 2"->8,"field 3"->9|>
}

If I were to apply the following Query on this dataset:

Query[
    ReverseSortBy["field 3"],
    StringJoin[ToString/@{#"field 1",#"field 2"}]&
]@data

Then I get:

{"78", "45", "12"}

This means that first the function ReverseSortBy["field 3"] is applied to the entire expression to reverse the order based on "field 3" and then on each sub level the function StringJoin[ToString/@{#"field 1",#"field 2"}]& is applied to get the joined values from the two fields.

Note the order of application cannot be the other way since if StringJoin[ToString/@{#"field 1",#"field 2"}]& is applied on each sub level then the association structure is lost and then ReverseSortBy will not be able to find the Key "field 3" by which to reverse the list of associations.

So following the same idea I add another function:

Query[
    ReverseSortBy["field 3"]@*Select[#"field 3">3&],
    StringJoin[ToString/@{#"field 1",#"field 2"}]&
]@data

The functions must be getting applied from outer to inwards but this fails! Since now magically the order of application has changed from inner to outer.

Note the Map allows me to move inner level function to outer level and thereby controlling the order precisely as follows to make the above Query work:

Query[
    Map[StringJoin[ToString/@{#"field 1",#"field 2"}]&]@*ReverseSortBy["field 3"]@*Select[#"field 3">3&]
]@data

I get

{"78", "45"}

as expected! But why did the second Query changed the order of function application and failed? What are the rules governing function application order inside Query?

Answer 1

@Lee's answer shows how to circumvent the problem by using RightComposition (/*) instead of Composition (@*), but it does not explain why this works. I will try to explain the "Why" in this answer.

Let's first look at the original example and see how the order is decided. The following is based on the extensive documentation of Query:

• Query differentiates between two types of operators: "Ascending" and "Descending". First, "descending" operators are applied starting from the outermost one, then "ascending" operators are applied starting from the innermost one:

  • An "ascending" operator is applied after all subsequent operators have been applied to deeper levels. … »

  • A "descending" operator is applied to corresponding parts of the original dataset, before subsequent operators are applied at deeper levels. … »

• "Descending" operators include everything that somehow selects parts of the structure ("key", i;;j, All, Select[…], …), or rearranges it (Sort, SortBy[…], …)
• Everything else is considered an "ascending" operator. In particular, this includes any unknown operators and custom functions.

With this, we understand why the first example works: As a "descending" operator, ReverseSortBy[…] is applied before the "ascending" operator StringJoin[…]&.

In the second case, the first operator is of the form …@*… or Composition[…,…]. Since this is not of any of the forms recognized as "descending" operator, both operators are "ascending". This means the inner one is applied first, followed by the outer one.

Now, why does …/*… (i.e. RightComposition) work? This is due to the special handling of RightComposition by Query. From the "Details & Options" section:

• When one or more descending operators are composed with one or more ascending operators (e.g. desc /* asc), the descending part will be applied, then subsequent operators will be applied to deeper levels, and lastly the ascending part will be applied to the result. »

This means that Query recognizes ReverseSortBy[…]/*Select[…] as composition of two "descending" operators, which are therefore applied before the "ascending" operator. Select[…]@*ReverseSortBy[…] on the other hand is not recognized in an analogous way. Unfortunately, I don't know why it was implemented this way, I myself have stumbled over this asymmetry several times already.

Answer 2

Using RightComposition in the expression which fails will produce the result you are looking for:

data = {
<|"field 1" -> 1, "field 2" -> 2, "field 3" -> 3|>, 
<|"field 1" -> 4, "field 2" -> 5, "field 3" -> 6|>, 
<|"field 1" -> 7, "field 2" -> 8, "field 3" -> 9|>
};

Query[ReverseSortBy["field 3"] /* Select[#"field 3" > 3 &], 
  StringJoin[ToString /@ {#"field 1", #"field 2"}] &]@data

You can see the difference between Composition and RightComposition by viewing the compiled form of the Query with Normal:

Query[ReverseSortBy["field 3"] @* Select[#"field 3" > 3 &], 
  StringJoin[ToString /@ {#"field 1", #"field 2"}] &] // Normal

Query[Select[#"field 3" > 3 &] /* ReverseSortBy["field 3"], 
  StringJoin[ToString /@ {#"field 1", #"field 2"}] &] // Normal

The first expression fails when applied to data because the output of Map is a list of strings, whereas Select is expecting an Association with a key of "field 3".