Should reduce throw an error on infinite iterators?

Internals & Design
,
1

Currently, reduce (and by extension mapreduce, sum and other functions) operate on iterators without checking whether they are finite or not. For example

julia> sum(Iterators.cycle([1,2,3]))

would run forever. I wanted to check if this intended behavior before submitting an issue on Github.

I was thinking that Base.IteratorSize can be used to check if an iterator is infinite before handing it over to mapreduce/reduce, e.g.,

julia> mysum(f,a::Iterators.Cycle;kw...) = Base.IteratorSize(a)==Base.IsInfinite() ? error( "Can not sum over an infinite iterator") : mapreduce(f,add_sum,a;kw...)
julia> mysum(a;kw...)=mysum(identity,a;kw...)

This seems to handle this issue, but I discovered that Base.IteratorSize(Iterators.cycle(Int64[])==Base.IsInfinite(), so another test is needed to maintain compatibility with the current

julia> sum(Iterators.cycle(Int64[])) # 0

At this point, it seems like I missing something because isempty(cycle([]))==true and IteratorSize(cycle([])==IsInfinite, which seems contradictory.

Edit: I found a closely related open issue about the case of empty iterator. However, I did not see a mention of the issue of reducing over infinite iterators.

1 Like
2

on principle it sounds fair to make reduce or sum reject inputs known to be IsInfinite. however I think there are two issues off the bat:

  • not all infinite iterators are IsInfinite; many are SizeUnknown. while I can see the argument that catching some bad cases is superior to catching zero bad cases, we can’t expect any kind of clean invariant like “reduce terminates” either way.
  • short-circuiting reductions any and all may terminate on infinite iterators if their condition is met. and in theory (though in practice this is not implemented) even something like sum could terminate if the reduction value becomes NaN or missing. so since these functions are generally implemented in terms of reduce it would introduce breaking behavior in the form of new errors, which would be a bit clunky to work around.
1 Like
3

This sounds nice for reduce and making IsInfinite more accurate is good, but something in the rationale that makes me pause is sum isn’t always implemented by iterative reduce. Summing ranges only needs the first element, the step size, and length for a much more efficient formula, which is implemented in Julia. Infinite sums do exist and can be computed in finite steps, even though they’re obviously not suited for numbers with limited precision and are not implemented by any package I know of. But it wouldn’t be great for someone who eventually implements some infinite series’ natural indexing and iteration to run into the sum API demanding an error be thrown for any infinite series, even though the whole point was to give Inf for divergent series and compute known formulas for convergent ones.