Search code examples
interfaceiteratorjulia

How to define `last` iterator without collecting/allocating?

Using the example from the Julia Docs, we can define an iterator like the following:

struct Squares
    count::Int
end

Base.iterate(S::Squares, state=1) = state > S.count ? nothing : (state*state, state+1)

Base.eltype(::Type{Squares}) = Int # Note that this is defined for the type
Base.length(S::Squares) = S.count

But even though there's a length defined, asking for last(Squares(5)) results in an error:

julia> last(Squares(5))
ERROR: MethodError: no method matching lastindex(::Squares)

Since length is defined, is there a way to iterate through and return the last value without doing an allocating collect? If so, would it be bad to extend the Base.last method for my type?

Solution

  • As you can read in the docstring of last:

    Get the last element of an ordered collection, if it can be computed in O(1) time. This is accomplished by calling lastindex to get the last index.

    The crucial part is O(1) computation time. In your example the cost of computing last element is O(count) (of course if we want to use the definition of the iterator as in general it would be possible compute it in O(1) time).

    The idea is to avoid defining last for collections for which it is expensive to compute it. For this reason the default definition of last is:

    last(a) = a[end]

    which requires not only lastindex but also getindex defined for the passed value (as the assumption is that if someone defines lastindex and getindex for some type then these operations can be performed fast).

    If you look at Interfaces section of the Julia manual you will notice that the iteration interface (something that your example implements) is less demanding than indexing interface (something that is defined for your example in the next section of the manual). Usually the distinction is made that indexing interface is only added for collections that can be indexed efficiently.

    If you still want last to work on your type you can either:

    • add a definition to Base.last specifically - there is nothing wrong with doing this;
    • add a definition of getindex, firstindex, and lastindex to make the collection indexable (and then the default definition of last would work) - this is the approach presented in the Julia manual