module Iterator(T)

Overview

An Iterator allows processing sequences lazily, as opposed to Enumerable which processes sequences eagerly and produces an Array in most of its methods.

As an example, let's compute the first three numbers in the range 1..10_000_000 that are even, multiplied by three. One way to do this is:

(1..10_000_000).select(&.even?).map { |x| x * 3 }.first(3) # => [6, 12, 18]

The above works, but creates many intermediate arrays: one for the select call, one for the map call and one for the first call. A more efficient way is to invoke Range#each without a block, which gives us an Iterator so we can process the operations lazily:

(1..10_000_000).each.select(&.even?).map { |x| x * 3 }.first(3) # => #< Iterator(T)::First...

Iterator redefines many of Enumerable's method in a lazy way, returning iterators instead of arrays.

At the end of the call chain we get back a new iterator: we need to consume it, either using each or Enumerable#to_a:

(1..10_000_000).each.select(&.even?).map { |x| x * 3 }.first(3).to_a # => [6, 12, 18]

Because iterators only go forward, when using methods that consume it entirely or partially – to_a, any?, count, none?, one? and size – subsequent calls will give a different result as there will be less elements to consume.

iter = (0...100).each
iter.size # => 100
iter.size # => 0

Iterating step-by-step

An iterator returns its next element on the method #next. Its return type is a union of the iterator's element type and the Stop type: T | Iterator::Stop. The stop type is a sentinel value which indicates that the iterator has reached its end. It usually needs to be handled and filtered out in order to use the element value for anything useful. Unlike Nil it's not an implicitly falsey type.

iter = (1..5).each

# Unfiltered elements contain `Iterator::Stop` type
iter.next + iter.next # Error: expected argument #1 to 'Int32#+' to be Int32, not (Int32 | Iterator::Stop)

# Type filtering eliminates the stop type
a = iter.next
b = iter.next
unless a.is_a?(Iterator::Stop) || b.is_a?(Iterator::Stop)
  a + b # => 3
end

Iterator::Stop is only present in the return type of #next. All other methods remove it from their return types.

Iterators can be used to build a loop.

iter = (1..5).each
sum = 0
while !(elem = iter.next).is_a?(Iterator::Stop)
  sum += elem
end
sum # => 15

Implementing an Iterator

To implement an Iterator you need to define a next method that must return the next element in the sequence or Iterator::Stop::INSTANCE, which signals the end of the sequence (you can invoke stop inside an iterator as a shortcut).

For example, this is an iterator that returns a sequence of N zeros:

class Zeros
  include Iterator(Int32)

  def initialize(@size : Int32)
    @produced = 0
  end

  def next
    if @produced < @size
      @produced += 1
      0
    else
      stop
    end
  end
end

zeros = Zeros.new(5)
zeros.to_a # => [0, 0, 0, 0, 0]

The standard library provides iterators for many classes, like Array, Hash, Range, String and IO. Usually to get an iterator you invoke a method that would usually yield elements to a block, but without passing a block: Array#each, Array#each_index, Hash#each, String#each_char, IO#each_line, etc.

Included Modules

• Enumerable(T)
• Numcry::Accumulate::Ext(T)

Defined in: