Reduce operation

[innovate-invent]

We have map to apply the same operation resulting in the same size output, but we don't have a reduce operation that allows aggregating an arbitrary dataset.

The reduce operation is a bit complicated as the expression that is being evaluated for each input must accept two inputs, the aggregate so far and the current input. There is currently no way in JMESPath to refer to more than one item in context @. The let() function is slated to resolve that for most use cases, but it can not be used recursively.

To contrast map(&expression, array), expression accesses the current item via @ when being evaluated.

We could do some trickery with an implied let() around each evaluation of the expression with a reserved identifier for the aggregate, but that is a bit cludgey.

We could equally introduce an additional symbol rather than an identifier, but that is not much better and it adds single use grammar for a function.

The expression could have a wrapped context where @ is an object like {"acc":.., "cur":..} and the expression must explicitly refer to each, but that is not much better than the first suggestion, putting the current item behind an additional identifier as well. At least with this there is no possibility of the aggregate identifier colliding with an identifier in the current item.

I am interested to hear alternatives or if any of these suggestions are preferred.

[innovate-invent]

My post in the other discussion goes into more detail but I think we should consider implementing this as syntax.

As far as I can tell map(&expression, a) is redundant to a[*].expression. We could potentially extend the syntax to something like a[&].merge(acc, cur) for a reducing projection. I also think the wrapped context is the best way to move forward, it is a bit odd to suddenly have identifiers in a query that are not declared in the query or data though.

[springcomp]

I‘m not really statisfied with overloading a symbol with different behaviour.
Maybe that’s not a valid concern, but maybe we would also want to support the root reference within a reduce projection...

I agree that the magic {acc: , cur: } context within the reduce projection feels like a hack. For instance, currently we support:

search(sum([].age), [{"name": "Mark", "age": 50}, {"name": "Ted", "age": 42}]) -> 92

Incidentally, we would still not be able to express an hypothetical reduce function:

search(reduce([].age, 0, &acc + cur), [{"name": "Mark", "age": 50}, {"name": "Ted", "age": 42}]) -> 92

So what we are really after is the concept of lambda that expression-type falls short of. That is, we need a means to name arguments that would be specified to the expression. We could have something like this added to the grammar:

lambda-expression = lambda-arguments "=>" expression-type
lambda-arguments = "(" identifier *( "," identifier ) ")" 

Which would allow something like:

reduce([].age, 0, (acc, cur) => &acc + cur)

Where the order and semantics of the arguments would be defined by the specification of the reduce function.
If we now want to express this with a reduce-projection instead of a function, we still have to specify the symbol we want to use.

An expression-type expression would be a simplified syntax for a lambda-expression that does not take any arguments at all. That is, something like:

() => &expr

[springcomp]

I thinks any symbol that is not already used would be all right within reduce-projection expressions.

However, as a big fan of PowerShell, I like the following symbols ? and % used respectively for the where and foreach filters. As JMESPath already defines ? for the where filter, I like the symmetry it would provide if we think of a reduce-projection as being somewhat akin to a foreach filter (although it strictly is more akin to map, really).

That would allow us to make the following two expressions equivalent:

search(sum([].age), [{"name": "Mark", "age": 50}, {"name": "Ted", "age": 42}]) -> 92
search([%0].age.(acc, cur) => &acc + cur), [{"name": "Mark", "age": 50}, {"name": "Ted", "age": 42}]) -> 92

Although we touch on the subject of readibility and ease of use.

On another note, if we accept lambda-expression in the grammar, we would perhaps need a way to express discarded arguments.
In languages that support this concept, _ is a popular symbol but _ is a valid identifier in JMESPath. So we would need to find an alternative.

[innovate-invent]

It isn't clear why this wouldn't work:

search(reduce([].age, 0, &acc + cur), [{"name": "Mark", "age": 50}, {"name": "Ted", "age": 42}]) -> 92

Can you elaborate more?

[springcomp]

It definitely would.

However, it also has this "magic" use of acc and cur identifiers that pop out of nowhere. The magic is there irrespective of the fact reduce is implemented as a function or as syntax.

That's what I addressed specifically with the concept of lambda.

[innovate-invent]

I see, this is why I was proposing using the $ symbol to represent acc. I think the $ symbol should be a context sensitive reference that refers to a "greater" context. This is the root node by default, the key value in a projection (if you think of the key as the parent of the value), and the accumulated value in a reduce projection. We could also potentially use it to refer to the defining context of an expression-type.

This removes the need for the magic identifiers with a more consistently defined symbol.

I am not thrilled about the idea of introducing a lambda syntax. I appreciate you are trying for a more declarative syntax to remove the "magic" identifiers, but I can't see a use case beyond a single additional special identifier other than @. This would also heavily overlap with my reusable expressions proposal.

[innovate-invent]

To summarize a few different discussions I think the best standing proposal is for the reduce operation to be:

reducing-projection = "[" "%" [expression] "]"

Like the projection operation, the expression following the reducing projection is applied to every value of an array or map. The $ symbol represents the accumulated/previous value of the projection and @ is the current value.

The expression within the brackets specifies the initial value of $, if expression is omitted the initial value of $ is the first value of the array/object and the first iteration has @ starting at the second value.

The resulting value of the reducing-projection is the accumulated value (or the value of the last iteration).

examples:

search([1, 2, 3, 4], [%1].$+@) -> 11
search([1, 2, 3, 4], [%].$+@) -> 10
search([5, 1, 2, 4], [%].(($<@) && $) || @) -> 1
search([[a, 1], [b, 2], [c, 3]], [% {} ].merge($, {@[0] : @[1]})) -> {a: 1, b: 2, c: 3}
search([true, false, true], [%].$ && @) -> false
search([true, false, true], [%].$ || @) -> true
search([1,2,2,2,3,4], [%{}].merge($, {@ : $[@] + 1})) -> {1: 1, 2: 3, 3: 1, 4: 1}

[springcomp]

Maybe % is not a good choice on my part. I can easily see this used as the modulo operator instead.

[springcomp]

Or it could serve both purposes because the context is unambiguous.

[springcomp]

Based on this comment I think the reduce operation is not a projection. In that it produces a single value and does not expect downstream expressions to apply on multiple items from the result of the operation.

[innovate-invent]

I think there is a misunderstanding, reduce does expect downstream expressions to apply. For [% init ].expr, expr is applied to each value in the current context.

[springcomp]

I see now.

What you are referring to as the reduce projection is only the bracket-specifier [% init] which does not actually reduce anything until downstream expressions would get applied against each projected value to accumulate the result.

I was referring to the reduce operation as the whole process yielding a single result value after applying the reduce logic.

So, yes, you are right. I agree the reduce bracket-specifier would indeed be a projection.

[springcomp]

For consistency reason, since we have map() function, I would tend to favor a corresponding reduce() function rather than implement dedicated syntax for this operation.

[springcomp]

Somes miscellaneous contrasting examples:

Return the highest length from a set of arrays, containing the number 2:

• syntax: search ( [? contains(@, `2`)]|[% `0`] -> max([$, length(@)]), [[1, 2, 3], [2, 3], [1, 4]] ) -> 3
• lambda: search ( reduce([?contains(@, `2`)], `0`, (acc, cur) => max([acc, length(cur)])), [[1, 2, 3], [2, 3], [1, 4]] ) -> 3

[innovate-invent]

This leaves us with one remaining candidate, which although not harmful, is actually useless, given the terminal precedence rules. Again, I think that is why it was excluded.
expression "." paren-expression

I am not sure I fully understand this. If we add paren-expression to sub-expression, that would solve the issue I mention above. We could additionally add arithmetic-expression, which would cover 90% of the expected reduce operations anyway.

This would allow [%].$+@ and [%].($ || @) ('sum' and 'any' operations respectively)

[springcomp]

I understand, that is a good idea.

[innovate-invent]

if arethmetic operators have a stronger binding than . then it should work. This would be different than the or/and operators.
This is all coming from a limited understanding of how this is being parsed, hopefully I am not way off.

I think you ninja edited something and I am responding to nothing 😋

[springcomp]

TL;DR

reduce() function and lambda-expression

A reduce() function is straightforward to implement as it is reasonably scoped. The work done while implementing the let() function is paying dividends as we can reuse the concept of scopes out of the box.

The current implementation uses a lamba-expression to eliminate some magic around naming the acc and cur values but this is not strictly necessary. If we were to introduce the root-node expression instead, a new stack of accumulated values would need to be introduced, so that the accumulator could be set by the reduce() function and accessed by the downstream root-node expression.

[% expression] -> expression syntax-based reduce-expression

A reduce-expression that encompasses the bracket portion and the reducing logic is possibly syntactically. We need to introduce an additional token as the whole expression cannot be a sub-expression.

Implementing reduce as syntax requires that a new stack of accumulated values be passed on to each interested expression, In the current implementation, only the reduce-expression and corresponding root-node expression would need to access to the current value of the accumulator.

reduce-projection

A reduce-projection is only possible if the reducing mechanism is built into the core concept of projection in the implementation. This is needed for a projection usually does not carry any state, so downstream expressions have no way to understand that in this special case, reduction needs to happen.

A reduce-projection has the syntax we initially envisioned, but needs to be special-cased.

[springcomp]

For the record, here is an alternate proposal for a reduce() function.

any reduce(array[any], object $seed, expression->expression->any $expr)

The $seed object would be pushed into the current scope (much like the first argument of the let() function does).

The first property of the $seed object would be the seed to the reduce operation.

In a reduce operation, the accumulated value starts as the seed. So the name of the first property in the $seed object would be the name under which the accumulated value is known and could be referred to in the $expr expression.

Thus, any() and sum() could be emulated by the following expressions, assuming an appropriate input JSON array.

• any: reduce(@, { acc: `false` }, &acc || @) (is there any truthy value in the input array)
• sum: reduce(@, { acc: `0` }, &acc + @) (subject to arithmetic-expression)

Pros

Reuses concepts already introduced by the let() function.

Cons

None 🤣

[springcomp]

Interesting to note that this proposal was considered early on in the design of JMESPath.

[springcomp]

Some of us are keen to try and support a reduce operation through pure syntax instead of relying on a function.
The current syntax being proposed looks like this:

• [% `false`].$ || @

Here $ would refer to the accumulated value within a reduce operation and is irrelevant to this present comment. Let’s focus instead on the overall syntax. This syntax uses a sub-expression whose rhs is an or-operation. That is not currently not supported in the grammar.

Instead of thinking of the reduce being split into a left projection that projects its values to a right reduce operation, let’s invert the process and have a reduce-expression accept an array and operate on it.

• @.[% `false`, &$ || @]

Here the bracket part is not a multi-select-list. Instead, it is a reduce-expressionthat is defined like so:

expression =/ reduce-expression
sub-expression =/ expression "." reduce-expression

reduce-expression = "[%" [ expression ] "," expression-type "]"

Popular functions, like any() or sum() could be emulated using the following syntax:

• any [% `false`, &$ || @]
• sum [% `0`, &$ + @] (subject to arithmetic-expression being part of the language)

[springcomp]

Maybe overloading bracket notation on the rhs is confusing.

[springcomp]

expression-type is currently only supported for function arguments. However, the grammar shown above still works perfectly fine and has not ambiguity.

[springcomp]

In light of a newly proposed let-expression it might be worth revisiting those proposals here, and include a feature that centers around:

• Defining anonymous functions witha arguments.

Maybe a new reduce() function that would be invoked like this:

reduce(
  array,
  `0`, 
  ($acc, $cur) => & $cur + $acc
)

Where $acc => $acc + @ would be a lambda-expression defining an anonymous function with a two arguments named $acc and $cur whose implementation is an expression-type that sums those two values.

reduce() itself would take three arguments,

• An array,
• An initial value for the accumulator
• The lambda-expression

And it would call the lamba-expression for all items in the array, gathering the result as an input to the next iteration.

[springcomp]

Here is an initial attempt at this initiating feedback on this proposal.