Iterators
Iterators are objects that can be used to traverse collections such as an
Array
or a Map
. Typically iterators are implemented in one of two
ways:
- Internal iterators: these kind of iterators take care of the iteration process and operate using some kind of closure.
- External iterators: these iterators use some kind of cursor stored somewhere and require you to manually advance the iterator.
Both have their benefits and drawbacks. Internal iterators are easy to implement and typically faster, as they don't require the allocation of additional data structures.
External iterators can be composed together, suspended, and later resumed. External iterators can also be turned into internal iterators, while the inverse is not possible unless a language supports some form of coroutines or generators.
Inko supports both internal and external iteration. When all you need is to iterate over some values, you can use internal iteration. If you need to compose iterators together, you can use external iteration.
When an iterator is created, it's positioned before the first value. To access
the first and any following elements, you must send advance
to the
iterator, followed by sending current
. For example:
let numbers = Array.new(10, 20, 30)
let iter = numbers.iter
iter.advance # => true
iter.current # => 10
Creating iterators manually
Creating an iterator manually requires:
- A object that tracks the state of the iteration process.
- An implementation of the
Iterator
trait for this object.
The Iterator
trait requires that you implement one method: next
. This method
returns an Option
to signal the presence or lack of a value.
Let's say we want to create an iterator that yields the first 5 values in an
Array
, then terminates. We can do so as follows:
import std::iterator::Iterator
class LimitedIterator!(T) {
@array: Array!(T)
@index: Integer
static def new!(T)(array: Array!(T)) -> LimitedIterator!(T) {
Self { @array = array, @index = 0 }
}
}
impl Iterator!(T, Never) for LimitedIterator {
def next -> ?T {
(@index == 5).if_true { return Option.none }
let value = @array.get(@index)
@index += 1
value
}
}
The iterator type is defined as Iterator!(T, E)
with T
being the type of
values to produce, and E
being the type to throw; if any. If your iterator
doesn't throw, as is the case above, you can assign E
to the Never
type.
With our iterator defined, we can use it like so:
let mut iterator = LimitedIterator.new(Array.new(1, 2, 3, 4, 5, 6, 7, 8))
iterator.next # => Option.some(1)
iterator.next # => Option.some(2)
iterator.next # => Option.some(3)
iterator.next # => Option.some(4)
iterator.next # => Option.some(5)
iterator.next # => Option.none
Creating iterators using generators
Creating an iterator requires quite a bit of boilerplate code. For non-linear collections such as graphs, implementing an iterator can also be tricky.
To make this easier, we can use what is called a "generator". A generator is a
method that can be suspended, and resumed later on. We can use generators to
create iterators, without the boilerplate. Using a generator, we can implement
our LimitedIterator
as follows:
import std::loop::(while)
def limited_iterator!(T)(values: Array!(T)) => T {
let mut index = 0
while({ index < 5 }) {
yield values[index]
index += 1
}
}
Here the => T
signals that the method limited_iterator
is a generator,
yielding values of type T
.
Generator methods can't specify an explicit return type, and can't return values
using the return
keyword. Thus, the following is invalid:
import std::loop::(while)
def limited_iterator!(T)(values: Array!(T)) => T {
let mut index = 0
while({ index < 5 }) {
yield values[index]
index += 1
}
return 10
}
You can use return
without providing a value. This is useful if you wish to
stop the generator:
import std::loop::(while)
def limited_iterator!(T)(values: Array!(T)) => T {
let mut index = 0
while({ index < 5 }) {
yield values[index]
return
index += 1
}
}
The last expression of the generator is also ignored. Instead, generator methods
always return an instance of Generator
.
We can use our generator like so:
let gen = limited_iterator(Array.new(1, 2, 3, 4, 5, 6, 7, 8))
gen.resume # => Option.some(1)
gen.resume # => Option.some(2)
If the generator method throws, the resume
method re-throws that error. This
means you need to handle it. For example:
import std::loop::(while)
def limited_iterator!(T)(values: Array!(T)) !! String => T {
let mut index = 0
while({ index < 5 }) {
yield values[index]
throw 'oops'
index += 1
}
}
let gen = limited_iterator(Array.new(1, 2, 3, 4, 5, 6, 7, 8))
try! gen.resume # => Option.some(1)
try! gen.resume # => panic
Generators as iterators
Generators themselves are also iterators. So instead of using resume
, we can
also use next
:
import std::loop::(while)
def limited_iterator!(T)(values: Array!(T)) => T {
let mut index = 0
while({ index < 5 }) {
yield values[index]
index += 1
}
}
let iter = limited_iterator(Array.new(1, 2, 3))
iter.next # => Option.some(1)