Infinite length ranges inconsistently implemented

[dlfivefifty]

The following is inconsistent:

k=1:Inf
first(k)   # works
last(k)   # works
k[1]       # throws inexact error

In 0.5, show is also broken.

I would argue that infinite length ranges are worth implementing: it is more convenient to do

for k=1:Inf
   # do stuff and call break
end

than

k=1
while true
  # do stuff and call break
  k+=1
end

[nalimilan]

Looks like checkbounds doesn't like Inf. Cc: @mbauman

I think the error when trying to print the range is caused by isempty failing, which itself comes from length not working. And length cannot work for such ranges since Inf cannot be represented by an integer type.

Also, the for patterns you indicate are unlikely to be a good idea. Inf only exists for floating point types, so 1:Inf is a float range, while indices are (generally) integers. But you can do for x in itr and break when you want.

[mbauman]

Yeah, the root trouble here is length. You could try returning a floating point length, but I have a feeling that will cause lots of troubles elsewhere… we have a pretty well-entrenched assumption that lengths are integers.

In this case, you can use for i in countfrom(1). A mathconst-like infinity would allow colon(x::Int, ::Infinity) = countfrom(x), but adding that creates more difficulties than it solves: #6062.

[nalimilan]

Maybe 1:Inf should raise an error directly, and point users to countfrom?

[dlfivefifty]

I think allowing length to return a float is indeed troublesome.

Reading #6062 convinced me that I should create a MathConst{:∞} in my package: I have a data structure that represents infinite-dimensional arrays, and need to support

A[2:∞,2:∞]

to take subarrays. I can then overload colon(x::Int,::MathConst{:∞}) to return countfrom(x).

[eschnett]

You could also overload colon(x::Int, y::Float64), and add a run-time check whether y is Inf or -Inf.

Another option (that I took in https://github.com/eschnett/FlexibleArrays.jl) is to use a different syntax for this case, i.e. to not use the colon operator here. This has the advantage that it is easier to get correct, as you don't have to shoehorn your handling of infinity into Base's notion of a range. (What if other packages did the same -- would that lead to a conflict if one uses both packages?)

For example, you could define a type StartFrom that represents an open interval, and a function startfrom(x::Int) that returns such a type. While overloading getindex, you would then handle this type as well.

[dlfivefifty]

overriding colon(x::Int,y::Float64) is a bad idea: it may affect things outside the package. Creating a new type representing ∞ avoids this issue, as the type is package specific: No one is going to accidentally call 1:MyPackage.∞

[dlfivefifty]

For my own usage, I've done the following to make infinite-length ranges work as expected:

## New Inf

const ∞ = Irrational{:∞}()

Base.show(io::IO, x::Irrational{:∞}) = print(io, "∞")
Base.convert{F<:AbstractFloat}(::Type{F},::Irrational{:∞}) = convert(F,Inf)

## My Count
# Need to reimplement, to avoid changing behaviour in Base

immutable Count{S<:Number}
    start::S
    step::S
end
countfrom(start::Number, step::Number) = Count(promote(start, step)...)
countfrom(start::Number)               = Count(start, one(start))
countfrom()                            = Count(1, 1)

Base.eltype{S}(::Type{Count{S}}) = S

Base.start(it::Count) = it.start
Base.next(it::Count, state) = (state, state + it.step)
Base.done(it::Count, state) = false

Base.length(it::Count) = ∞
getindex(it::Count,k) = it.start + it.step*(k-1)


## Colon

Base.colon(a::Real,b::Irrational{:∞}) = countfrom(a)
Base.colon(::Irrational{:∞},::AbstractFloat,::Irrational{:∞}) = [∞]
Base.colon(a::Real,st::Real,b::Irrational{:∞}) = countfrom(a,st)

Base.isinf(::Irrational{:∞}) = true

[mbauman]

k=1.0:Inf now throws an error upon construction. I think doing this through a custom type is the way to go here (indeed: https://github.com/JuliaApproximation/InfiniteArrays.jl). Are there any other changes to base that you need to satisfy that case?

[dlfivefifty]

So far it works with very few modifications. The only modifications that might be worth changing Base I can think of are:

1. The use of OneTo: I had to override OneTo(::Infinity) to return a special type OneToInf: This is misleading as OneTo(x) should always return a type of OneTo. The proposed change to Base would be to change the function name to oneto.
2. Rewrite vcat and hcat in a broadcast-like manner with traits, etc. Lazy broadcasting works amazing, though I haven't tried it since the broadcast rewrite. Lazy concatination needs the user to call Vcat or Hcat.
3. ReshapedArray should work with non-Int lengths

Surprisingly, that's about it. And the package is really fun:

julia> using InfiniteArrays

julia> Vcat(Ones(1,∞), Hcat(Zeros(∞), Diagonal(1:∞)))
Vcat{Float64,2,Tuple{Ones{Float64,2,Tuple{Int64,InfiniteArrays.Infinity}},Hcat{Float64,Tuple{Zeros{Float64,1,Tuple{InfiniteArrays.Infinity}},Diagonal{Int64,InfiniteArrays.InfUnitRange{Int64}}}}}} with indices OneToInf()×OneToInf():
 1.0  1.0  1.0  1.0  1.0  1.0  1.0  …  
 0.0  1.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  2.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  3.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  4.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  5.0  0.0  …  
 0.0  0.0  0.0  0.0  0.0  0.0  6.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  …  
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  …  
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  …  
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  …  
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 0.0  0.0  0.0  0.0  0.0  0.0  0.0     
 ⋮                        ⋮         ⋱  

julia> exp.((-).((1:∞).^2))
BroadcastArray{Float64,1,getfield(Main, Symbol("##7#8")),Tuple{InfiniteArrays.InfUnitRange{Int64}},Tuple{InfiniteArrays.OneToInf{Int64}}} with indices OneToInf():
 0.36787944117144233    
 0.01831563888873418    
 0.00012340980408667956 
 1.1253517471925912e-7  
 1.3887943864964021e-11 
 2.3195228302435696e-16 
 5.242885663363464e-22  
 1.603810890548638e-28  
 6.639677199580735e-36  
 3.720075976020836e-44  
 2.8207700884601357e-53 
 2.8946403116483003e-63 
 4.020060215743355e-74  
 7.555819019711961e-86  
 1.921947727823849e-98  
 6.616261056709485e-112 
 3.082440696949098e-126 
 1.9435148500492928e-141
 1.6584104776811452e-157
 1.9151695967140057e-174
 2.993184452260193e-192 
 6.3309773362105915e-211
 1.8122540257939923e-230
 7.020667798504735e-251 
 3.6808558548018004e-272
 2.6117417612840555e-294
 2.507972e-317          
 0.0                    
 ⋮    

[dlfivefifty]

Also, I had to make Infinity <: Integer. This seemed like a bad idea at first, but I've come around to it: after all, Inf isa Real, and both Infinity and (positive) Integers are cardinalities.

[mbauman]

That's great. In your bulleted list, 3 is #17372, 2 is #2326, and 1 is interesting. Do you recall what the call-site(s) were that required that method? Or was it just you calling OneTo(∞) directly?

[dlfivefifty]

I don't recall in particular, but there are a number of calls to OneTo in abstractarray.jl. It probably was related to indices, e.g.

julia/base/abstractarray.jl

Line 91 in 6fb4569

indices1(iter) = OneTo(length(iter))

[dlfivefifty]

An alternative (but probably overkill) solution is change OneTo so that stop doesn't need to have the same type:

struct OneTo{T<:Integer,V<:Integer} <: AbstractUnitRange{T}
    stop::V
    OneTo{T,V}(stop) where {T<:Integer,V<:Integer} = new(max(zero(T), stop))
end
OneTo{T}(stop::V) where V = OneTo{T,V}(stop)
OneTo(stop) = OneTo{typeof(one(T))}(stop)