Julia: avoid calling `zero` in `reduce` when possible

[dlfivefifty]

See discussion https://discourse.julialang.org/t/interface-for-number/2723/5

I recently ran into an issue overriding zero for my own Number:

julia> immutable Infinity <: Number end

julia> Base.zero(::Infinity) = 0

julia> import Base: +

julia> +(::Infinity,::Int) = Infinity()
+ (generic function with 181 methods)

julia> reduce(+,[Infinity(),Infinity()])
ERROR: MethodError: Cannot `convert` an object of type Int64 to an object of type Infinity
This may have arisen from a call to the constructor Infinity(...),
since type constructors fall back to convert methods.
Stacktrace:
 [1] _mapreduce(::Base.#identity, ::Base.#+, ::IndexLinear, ::Array{Infinity,1}) at ./reduce.jl:260
 [2] reduce(::Function, ::Array{Infinity,1}) at ./reduce.jl:321

The issue appears to be that zero{T<:Number}(::T) needs is expected to be convertible to T.

Is this a bug? Otherwise, this should be documented somewhere (e.g., a description of the interface for Number)

[JeffBezanson]

I think you need to define zero(::Type{Infinity}). But there are certainly many cases where we expect to be able to convert numbers to other number types.

[dlfivefifty]

I think you need to define zero(::Type{Infinity})

That doesn't fix the issue. In any case, what is expected should be documented.

It's not clear to me what a Number means: not all sets of numbers include zero...another example would be numbers on the unit circle |z| = 1.

[JeffBezanson]

Ah, this case (reduce) seems to be one that just uses convert, and not always zero. I think it's deliberately unclear what Number means; for example should we require typeof(zero(T)) === T? I don't know.

After looking into it a bit more, I'd summarize this as a quasi-bug in reduce, in that it doesn't support types that can't be converted to the type of zero(T). It would be nice if we could maintain its functionality with fewer assumptions.

[dlfivefifty]

it's deliberately unclear what Number means

Hopefully this will be changed before 1.0. It would be good to have a Number interface outlined.

[nalimilan]

What looks like a bug to me is that reduce always tries to compute the zero element even when the collection is not empty. It seems like the error should happen only when the zero is actually needed. (Though I note the docstring says "It is unspecified whether v0 is used for non-empty collections.")

[timholy]

Now that one(T) does not return an object of type T, zero has become the new workhorse for "give me an object of type T." I think we need to require that...or that @dlfivefifty needs to do the work to figure out the larger implications. @dlfivefifty, can you audit the code in base/ and figure out how many uses there are of zero that implicitly assume it returns an object of type T?

[nalimilan]

Note that in the present case the issue isn't that the zero isn't of type T, it's that it cannot be converted to T at all.

[dlfivefifty]

I think we need to require that...or that @dlfivefifty needs to do the work to figure out the larger implications

I'm fine with that being a requirement, it just needs to be documented

[stevengj]

For non-empty collections, it would be good if reduce(+, x) didn't call zero at all. (This function has been notoriously difficult to get right in a type-stable way.)

[simonbyrne]

This now works for plain reduce:

julia> struct Infinity <: Number end

julia> Base.:+(::Infinity,::Infinity) = Infinity()

julia> reduce(+,[Infinity(),Infinity()])
Infinity()

julia> zero(Infinity())
ERROR: MethodError: no method matching Infinity(::Int64)

But not for reduce with dims:

julia> reduce(+,[Infinity(),Infinity()], dims=1)
ERROR: MethodError: no method matching Infinity(::Int64)