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