Iterator traits

iter.md

Iterator traits

In julia version 0.5 there are some changes how iterators are used in julia. The julia iteration protocol based on the methods start, size, next was already used in an intermediate step in the process of translating the general for syntax

    for elem in iter
        # do something
    end

to a lower level form

    state = start(iter);
    while !done(iter, state)
        i, state = next(iter, state)
        # do something
    end

The three functions start, next and done completely cover iterable objects in the context of for loops (and it is enough to define these three functions to make a new type iterable.) But in general iterable objects in julia come with further methods like length or size, see http://docs.julialang.org/en/release-0.4/manual/interfaces/#man-interfaces-iteration .
With #15123 (#15146 in its final form) iterators are also the workhorse behind the newly added Generators (#14848) and the implementation of map and collect. And indeed, the result of map(f,A) for an array A depends the size(A), but not all iterators implement size. To handle differences between iterable objects becoming important for the implementation of map etc. two kinds of traits where introduced: iteratorsize and iteratoreltype. For each iterator type Iter in base the function iteratorsize(Iter) returns instances SizeUnknown(), HasLength(), HasShape() or IsInfinite() of subtypes of abstract IteratorSize. iteratoreltype returns instances of EltypeUnknown() or HasEltype().

As function arguments, they allow to dispatch the version of collect or map best suited. For example, if an iterator has HasLength and HasEltype traits, collect can reserve an array of just the right size for the result before collecting the elements.

In short, for an iterator iter of type Iter

itersize(Iter) == HasLength() -- indicates that length(iter) is implemented and can be computed cheaply ... == HasShape() -- the result of collect is be an array of dimensions size(iter) (and size is implemented) ... == IsInfinite() -- done will never return true for ```iter(and an attempt tocollect(iter)`` will fail gracefully) ``... == SizeUnknown()`` -- none of the above

and

itereltype(Iter) == HasEltype() -- indicates to use the result of eltype(iter) to determine the type of array collect returns itereltype(Iter) == EltypeUnknown() -- otherwise

Using those traits allows to draw elaborate conclusions at compile time: for example that the length of the iterator collect(zip(countfrom(1), 'a':'z')) is computable (and not infinite) and collect would need to allocate a 26-element Array{Tuple{Int64,Char},1}. And

    julia> Base.iteratorsize(zip(countfrom(1), 'a':'z'))
    Base.HasLength()

For iterators defined by packages julia assumes to easen transition that iteratoreltype is HasEltype() and iteratorsize is HasLength() (and defines fallbacks of iteratorsize and iteratoreltype). This means iterable types MyIterator not defining a length method need to define

Base.iteratorsize(::Type{MyIterator}) = SizeUnknown()

or

iteratorsize{C<:MyParametrizedIterator}(::Type{C}) = SizeUnknown() # for a type MyParametrizedIterator{T}

in order to use collect and other types should define Base.iteratorsize(::Type{MyIterator}) and Base.iteratorsize(::Type{MyIterator}) in an appropriate way to make use of the new features and in case changes to the fallback definitions are made. (iteratorsize(iter) calls iteratorsize(typeof(iter))

itersize(Iter) == HasLength() -- indicates that length(iter) is implemented and can be computed cheaply

This is what I would have expected but it seems not to be the case.

julia> Base.iteratorsize(Nullable{Int}(1))
Base.HasLength()

julia> length(Nullable{Int}(1))
LoadError: MethodError: no method matching length(::Nullable{Int64})
Closest candidates are:
  length(!Matched::SimpleVector) at essentials.jl:178
  length(!Matched::Base.MethodList) at reflection.jl:401
  length(!Matched::MethodTable) at reflection.jl:473
  ...