unspecified behavior of `mapreduce` is bad

[fedeinthemix]

The documentation for mapreduce says that it is unspecified if the init key argument is used for non-empty collections. Since there is a single julia implementation leaving the behavior unspecified is bad. In general the init argument is a starting point that you want to combine with the rest. For example

sol = nlsolve(f!, initial_x)
 # mapreduce doesn't specify if `init` is used. Need to use reduce(..., map(...))
 if mapreduce(map(v -> v > 0, &,  sol.zero, init=converged(sol))
     return ...
 else
   ...
 end

Using the init argument to specify the result in case of an empty collection is a special case.

[jishnub]

From what I understand, the nomenclature is unfortunate, and init doesn't specify a starting point, rather it provides the identity element in the reduction. The documentation of mapreduce states this as well:

If provided, `init` must be a neutral element for `op` that will be returned for empty collections.

This implies that init is not arbitrary, and must satisfy op(op(init, x), y) == op(x, y). For the operator &, therefore, init should be set to true. In such a case, whether init is used or not doesn't change the result, and it's left as an implementation detail.

In your case, perhaps you might prefer foldl which guarantees that init is used exactly once, even if it's not set to the identity element. Or, perhaps the more explicit

if converged(sol) && mapreduce(map(v -> v > 0, &, sol.zero)

[fedeinthemix]

You are right that the documentation states that init must be a neutral element of the operation, but then the similarly worded documentation for reduce shows the following example

reduce(*, [2; 3; 4]; init=-1)

There are plenty of alternatives for my example, that's not the issue. My points are two. The first is that mathematically init doesn't have to be the neutral element (like -1 above) and it would be useful to allow this generality (like in the example I gave). Some other languages embrace this freedom
https://hackage.haskell.org/package/base-4.18.0.0/docs/Prelude.html#v:foldr

Second, documenting some behavior of an algorithm implementation as unspecified is unhelpful. Unspecified behavior may be acceptable in standards that want to allow for radically different implementations.

[jakobnissen]

Second, documenting some behavior of an algorithm implementation as unspecified is unhelpful. Unspecified behavior may be acceptable in standards that want to allow for radically different implementations.

Documenting it as unspecified allows Julia's implementation to change without being a breaking change. In other words, this is about being able to have different implementations across time.

That being said, the example you point to with reduce(*, [2; 3; 4]; init=-1) should indeed be changed, since its usage is incorrect.

Edit: Actually, it might be an issue (a bug?) that the two documented methods of reduce disagree on what init is. Is it the initial value, or the value returned on empty collections? Is it guaranteed to be used once? We should definitely clean this up.

Given that init has been documented to be the initial value for reduce on arrays, and it's called init, and the similar keyword in foldl, I think we should make it documented behaviour that it's used exactly once. Since we don't guarantee associativity, I'm not sure it's even meaningful to define it as the "initial value".

Are there any optimisation opportunities we lose if the guarantee that init is used exactly once?

[N5N3]

See #44819.

[fedeinthemix]

Since we don't guarantee associativity, I'm not sure it's even meaningful to define it as the "initial value".

I guess I don't clearly understand the difference between reduce and foldr/foldl. Using (for clarity) Haskell's notation for the type of functions, the latter two require functions with a different signature

foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b 

Associativity is irrelevant if the types a and b are the same, and the function is associative. In that case the two give the same result, but with different memory and speed results. Was reduce added as a way of helping picking the fastest one? If not, what is the actual semantic of reduce then?

[jakobnissen]

Re-ordering the operations can have various benefits. For example, re-ordering floating point operations allow you to use SIMD, making it much faster. It also enables pairwise summation, reducing the impact of float rounding errors.

So, if you have a function which is associative, you would use reduce in order to let the implementation decide the best order of operations. In that sense, foldl and foldr can be seen as special cases of reduce.

[mcabbott]

Are there any optimisation opportunities we lose if the guarantee that init is used exactly once?

CUDA does parallel reduction, and relies on init being the neutral element:

julia> let x = collect(1:10^4), init=2
        a = reduce(+, x; init)
        b = reduce(+, CuArray(x); init)
        a, b, sum(x)
       end
(50005002, 50046150, 50005000)

[ctarn]

It confuses me too. Both C++ and Python treat init of reduce as initial value or starting point.

C++: https://en.cppreference.com/w/cpp/algorithm/reduce

Generalized sum of init and *first, *(first+1), ... *(last-1) over binary_op

Python: https://docs.python.org/3/library/functools.html#functools.reduce

If the optional initializer is present, it is placed before the items of the iterable in the calculation, and serves as a default when the iterable is empty.

[jishnub]

The definition of functools.reduce in python seems to be equivalent to foldl in Julia

[fedeinthemix]

If init must be a unit and the operation op associative, then op and type ty form a monoid. Wouldn't it be useful to add something like monoidunit(ty, op) generalizing e.g. one, ones, zero and zeros. Then the init parameter could be either dropped or, more usefully, used as an initial value.

[jariji]

There is InitialValues.jl which says

InitialValues.jl provides a generic singleton initial value Init(f) that can be used as a₀ in f(a₀, x). For a binary operator op, it means that Init(op) acts like the left identity for any type of x

I'm not sure if it's better to do it with the two-argument monoidunit(t, op) or the one-argument wrapper Init(op).

[fedeinthemix]

I'm not sure if it's better to do it with the two-argument monoidunit(t, op) or the one-argument wrapper Init(op).

The type is important. For example for + if you specify the type you can use it for any scalar number, but also matrices, vectors, ... Also, without type you may loose type information. For example for vector concatenation the unit is the empty one, but without specifying the type you get

julia> v = [1, 2]
2-element Vector{Int64}:
 1
 2

julia> vcat(v, [])
2-element Vector{Any}:
 1
 2

[ctarn]

InitialValues.jl gives the following example:

julia> float(InitialValue(*))
1.0

julia> Integer(InitialValue(+))
0

So an InitialValue can also be casted to a specific type.

Personally I prefer to leave the feature as InitialValues.jl instead of adding it to standard lib of Julia.