Julia: allow firstindex, last, lastindex, length for SkipMissing

[bkamins]

Following the discussion with @nalimilan.

We currently allow:

julia> x = skipmissing([missing,1,2,3,missing])
skipmissing(Union{Missing, Int64}[missing, 1, 2, 3, missing])

julia> first(x)
1

but

julia> firstindex(x)
ERROR: MethodError: no method matching firstindex(::Base.SkipMissing{Array{Union{Missing, Int64},1}})

so it would be natural to have it.

Then it would be good to have lastindex(x) for symmetry. And if we add lastindex then we could also add last and length.

Now why I list these in that order, because in general all those methods are expensive (lust like first), but since we allowed first maybe for consistency other methods also could be allowed?

Finally when deciding if it should be allowed it is important to remember how indexing of SkipMissing works, as it is not a standard indexing:

julia> x = skipmissing([missing,1,2,3,missing])
skipmissing(Union{Missing, Int64}[missing, 1, 2, 3, missing])

julia> x[1]
ERROR: MissingException: the value at index (1,) is missing

julia> x[2]
1

julia> x[4]
3

julia> x[5]
ERROR: MissingException: the value at index (5,) is missing

julia> x[6]
ERROR: BoundsError: attempt to access 5-element Array{Union{Missing, Int64},1} at index [6]

[mbauman]

firstindex, last, and lastindex should definitely be added. length is a bit different because we've been very hesitant to implement O(n) length methods.

[bkamins]

This is the point why I ask, all of these methods, including first are O(n):

julia> x = skipmissing([fill(missing, 10^8); 1]);

julia> @btime first($x)
  37.867 ms (0 allocations: 0 bytes)
1

Of course "optimistic" time is lower, but pessimistic time is O(n). E.g. if x is AbstractArray when searching for last and lastindex we can go backwards which most of the time should be fast.

[simeonschaub]

I believe using Iterators.reverse, we should be able to implement last pretty efficiently and generically, at least for iterators that support it. I wonder whether it wouldn't make sense to have the generic definition last(itr) = first(Iterators.reverse(itr)).

[bkamins]

Incidentally this is what I have just commented as a general approach:), but in this particular case Iterators.reverse will fail as it is just first(r::Reverse) = last(r.itr).

[simeonschaub]

Ah, I see. Although for the purposes here, it would be possible to just iterate reverse(itr) once. The only problem would be stateful iterators (although they probably then also don't define reverse).

[nalimilan]

I agree with @mbauman that we should implement all of these, but not length, which is always O(n). The others are O(n) only in very atypical cases.

Also I think we should implement this only for SkipMissing{<:AbstractArray}, as for other iterators we will have to go over all values, which is always O(n), possibly consuming them. For arrays, the implementation should be straightforward.

[simeonschaub]

I think AbstractArray might be a bit too restrictive here, because we can also get the last element efficiently for strings and tuples, for example. That's why I proposed using Iterators.reverse for this, since that should catch all the important cases of iterators that can be iterated in reverse efficiently.

[nalimilan]

The problem with Iterators.reverse is that it supports any iterator, but may consume all values to find the last one. So it doesn't allow finding out whether a type supports fast identification of the last non-missing element.

We really need an Indexable trait. But for now yes, we could allow AbstractString and Tuple too.

[simeonschaub]

The problem with Iterators.reverse is that it supports any iterator, but may consume all values to find the last one. So it doesn't allow finding out whether a type supports fast identification of the last non-missing element.

I don't think that's true. From the docstring of Iterators.reverse:

Not all iterator types T support reverse-order iteration. If T doesn't, then iterating over
Iterators.reverse(itr::T) will throw a MethodError because of the missing iterate methods for
Iterators.Reverse{T}. (To implement these methods, the original iterator itr::T can be obtained from r =
Iterators.reverse(itr) by r.itr.)

It doesn't explicitely say that iterate(::Iterators.Reverse) is always supposed to be O(1), but that seems to be implied by all the iterators it is implemented for in Base.

[nalimilan]

Ah, right. first(itr::Reverse) just calls last(itr.itr), which throws an error if that's not implemented. Anyway, what we need is not the last element, but iterating starting from the end.

I guess we could define iterate(s::SkipMissing, args...) = iterate(s.itr, args...) and let it throw an error if that's not supported.