source: doc/proposals/iterators.md@ 1260224

Iterators
=========
This is the proposal for adding iterators to Cforall and the standard
library. Iterators provide a common interface for sequences of values in
the language. Many inputs and outputs can be described in terms of sequences,
creating a common interface that can be used in many places.

Related Traits
--------------
There are two groups of types that interact with this proposal.

Iterator

An iterator has a very simple interface with a single operation.
The operation is "get the next value in the sequence", but this actually has
several parts, in that it has to check if there are move values, return the
next one if there is one, and update any internal information in the iterator.
For example: `Maybe(Item) next(Iter &);`.

Now, iterators can have other operations. Notably, they are often also
iterables that return themselves. They can also have a verity of iterator
transformers built in.

Iterable

Anything that you can get an iterator from is called an iterable. There
is an operation to get an iterator from an iterable.

Range For Loop
--------------
One part of the language that could be reworked to make good use of this is
for loops. In short, remove most of the special rules that can be done inside
the identifier and make it a generic range for loop:

    ```
    for ( IDENTIFIER ; EXPRESSION ) STATEMENT
    ```

The common way to implement this is that expression produces an iterable.
The for loop gets an iterator from the iterable (which is why iterators are
often iterables, so they can be passed in with the same interface) and stores
it. Then, for each value in the iterator, the loop binds the value to the
identifier and then executes the statement. The loop exits after every value
has been used and the iterator is exhausted.

For the chained for loop (`for (i; _: j; _)`) can still have its existing
behaviour, advancing through each range in parallel and stopping as soon
as the first one is exhausted.

Ranges
------
Ranges, which may be a data type or a trait, are containers that contain
a sequence of values. Unlike an array or vector, these values are stored
logically instead of by copy.

The purpose of this container is to bridge the new iterator interfaces with
the existing range syntax. The range syntax would become an operator that
returns a range object, which can be used as any other type.

It might not cover every single case with the same syntax (the `@` syntax may
not translate to operators very well), but should be able to maintain every
option with some library range.

Library Enhancements
--------------------
There are various other tools in the library that should be improved.
The simplest is to make sure most containers are iterables.

Also, new utilities for manipulating iterators should be created. The exact
list would have to wait but here are some examples.

Transformers take in an iterator and produce another iterator.
Examples include map, which modifies each element in turn, and filter,
which checks each element and removes the ones that fail.

Producers create new iterators from other information.
Most practical iterators tend to be iterable containers, which produce all
the elements in the container, this includes ranges. Others include infinite
series of one element.

Consumers take an iterator and convert it into something else.
They might be converted into a container or used in a for loop. Dedicated
consumers will be some form of folding function.

Related Work
------------
Python has a robust iterator tool set. It also has a `range` built-in which
does many of the same things as the special for loops (the finite and
half-open ranges).

In addition, it has many dedicated iterator constructors and transformers,
and many containers can both produce and be constructed from iterators.

+   https://docs.python.org/3/reference/datamodel.html#object.__iter__
+   https://docs.python.org/3/library/functions.html#func-range

C++ has many iterator tools at well, except for the fact it's "iterators" are
not what are usually called iterators (as above) but rather an abstraction of
pointers. The notable missing feature is that a single iterator has no
concept of being empty or not, instead it must be compared to the end
iterator.

However, C++ ranges have an interface much more similar to iterators.
They do appear to be a wrapper around the "pointer" iterators.

+   https://en.cppreference.com/w/cpp/ranges

Rust also has a imperative implementation of a functional style of iterators,
including a great number of standard transformers. Otherwise, it is very
similar to Python.

+   https://doc.rust-lang.org/std/iter/index.html