Iterators ========= This is the proposal for adding iterators to Cforall and the standard libary. 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, 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 veriaty 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 iterator. 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 identifer 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 iterface) 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 exausted. 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 exausted. 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 iterfaces 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. 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. + 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. Rust also has a imparative 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