semantics of functions based on reduce

[mdrocco]

I think some consistency is missing in the semantics of the operators including a reduce operation: reduce, stream_reduce and map_reduce. I suggest to choose one of the reduce semantics that have been proposed in literature and use it consistently.

In general, I would avoid allowing user functions with "non-homogeneous" signature: U x T -> T, since this forces the reduce to be implemented sequentially. I suggest to stay with the simpler user function signature: T x T -> T and require it is both associative and commutative, as already done.

I can point out at least three variants of the reduce semantics:

1. no initial value: the result is the pairwise combination of the elements in the input collection;
2. with initial value: the result is the pairwise combination of the elements in the input collection, combined with the initial value;
3. with identity value: the result is the same as the "no initial value" variant, but the user is requested to pass in input the identity value for the user function; the result is undefined if such input value is not the identity value.

From my understanding, I would say currently the third variant is used (which seems the must cumbersome to me), and the non-homogeneous user function is supported (for which only the sequential implementation is correct). I would suggest to opt for either first or second variant and support only homogeneous user functions, that is also what is supported by std::reduce.

[jdgarciauc3m]

We will analyze this issue in detail for v0.3 and extend and harmonize the interface.

[jdgarciauc3m]

After discussion we plan to take the following actions.

1.- Guarantee that current support of reductions is restricted to homogeneous reductions.
2.- Open a separate issue to study and support heterogeneous reductions for specific cases.
3.- Support reductions with identity value, which assumes that the application programmer is passing an identity value which is consistent with the combination operator.
4.- Add an additional family of reductions without identity value only for those types that are default constructible. That version assumes that the default value for the type is the identity value. Not that this is consistent with addition in numeric types.

[jdgarciauc3m]

We have opened separate issues for different parts of this issue (#341, #342, #334, #343).

We are closing this issue as progress will be tracked by mentioned issues.

Please, feel free to reopen the issue if needed.

[mdrocco]

I am fine with the 4 points proposed, but I think that the 2 most useful semantics (those provided by std::reduce) are still missing:

1. reduction with no identity value at all, where the result is just the reduction of the input elements;
2. reduction + combination with initial (not identity) value

They correspond to variants 1-2 and 3-4, respectively, in:
http://en.cppreference.com/w/cpp/algorithm/reduce
with the only difference that in GrPPI the reduction kernel is arbitrary. Variants 5-6 of std::reduce have arbitrary kernel as well, but only the variant with initial value is supported in that case.

[jdgarciauc3m]

What you mention as 1 (std::reduce with no value) it is not specified the reduction of just the elements. In fact a call to std::reduce() without initial value invokes it passing as initial value the default value for the type (which requires it to be default constructible).

About the issue about using initial value instead of identity we defer this discussion to issue #343, Consequently, we keep this issue closed. Discussion about using identitiy value or initial value will go on at issue #343.

[mdrocco]

Sorry I missed the specification of 1 in terms of 3. Then better to be consistent with plain C++.

As just a note, this semantics looks a bit strange for someone used to functional programming (that is where std::reduce stems from). Usually, as for instance in Haskell, the reduction without initial/identity value is provided (foldr1 in Haskell), at least to avoid cumbersome syntaxes for simple things, like finding the maximum in a collection.

However, this discussion is probably out of scope here, better to stay with the current C++ way.