1 | Iterators |
---|
2 | ========= |
---|
3 | This is the proposal for adding iterators to Cforall and the standard |
---|
4 | libary. Iterators provide a common interface for sequences of values in |
---|
5 | the language. Many inputs and outputs can be described in terms of sequences, |
---|
6 | creating a common interface that can be used in many places. |
---|
7 | |
---|
8 | Related Traits |
---|
9 | -------------- |
---|
10 | There are two groups of types that interact with this proposal. |
---|
11 | |
---|
12 | Iterator |
---|
13 | |
---|
14 | An iterator has a very simple interface with a single operation. |
---|
15 | The operation is "get the next value in the sequence", but this actually has |
---|
16 | several parts, in that it has to check if there are move values, return the |
---|
17 | next one if there is, and update any internal information in the iterator. |
---|
18 | For example: `Maybe(Item) next(Iter &);`. |
---|
19 | |
---|
20 | Now, iterators can have other operations. Notably, they are often also |
---|
21 | iterables that return themselves. They can also have a veriaty of iterator |
---|
22 | transformers built in. |
---|
23 | |
---|
24 | Iterable |
---|
25 | |
---|
26 | Anything that you can get an iterator from is called an iterable. There |
---|
27 | is an operation to get an iterator from an iterator. |
---|
28 | |
---|
29 | Range For Loop |
---|
30 | -------------- |
---|
31 | One part of the language that could be reworked to make good use of this is |
---|
32 | for loops. In short, remove most of the special rules that can be done inside |
---|
33 | the identifer and make it a generic range for loop: |
---|
34 | |
---|
35 | ``` |
---|
36 | for ( IDENTIFIER ; EXPRESSION ) STATEMENT |
---|
37 | ``` |
---|
38 | |
---|
39 | The common way to implement this is that expression produces an iterable. |
---|
40 | The for loop gets an iterator from the iterable (which is why iterators are |
---|
41 | often iterables, so they can be passed in with the same iterface) and stores |
---|
42 | it. Then, for each value in the iterator, the loop binds the value to the |
---|
43 | identifier and then executes the statement. The loop exits after every value |
---|
44 | has been used and the iterator is exausted. |
---|
45 | |
---|
46 | For the chained for loop (`for (i; _: j; _)`) can still have its existing |
---|
47 | behaviour, advancing through each range in parallel and stopping as soon |
---|
48 | as the first one is exausted. |
---|
49 | |
---|
50 | Ranges |
---|
51 | ------ |
---|
52 | Ranges, which may be a data type or a trait, are containers that contain |
---|
53 | a sequence of values. Unlike an array or vector, these values are stored |
---|
54 | logically instead of by copy. |
---|
55 | |
---|
56 | The purpose of this container is to bridge the new iterator iterfaces with |
---|
57 | the existing range syntax. The range syntax would become an operator that |
---|
58 | returns a range object, which can be used as any other type. |
---|
59 | |
---|
60 | Library Enhancements |
---|
61 | -------------------- |
---|
62 | There are various other tools in the library that should be improved. |
---|
63 | The simplest is to make sure most containers are iterables. |
---|
64 | |
---|
65 | Also, new utilities for manipulating iterators should be created. The exact |
---|
66 | list would have to wait but here are some examples. |
---|
67 | |
---|
68 | Transformers take in an iterator and produce another iterator. |
---|
69 | Examples include map, which modifies each element in turn, and filter, |
---|
70 | which checks each element and removes the ones that fail. |
---|
71 | |
---|
72 | Producers create new iterators from other information. |
---|
73 | Most practical iterators tend to be iterable containers, which produce all |
---|
74 | the elements in the container, this includes ranges. Others include infinite |
---|
75 | series of one element. |
---|
76 | |
---|
77 | Consumers take an iterator and convert it into something else. |
---|
78 | They might be converted into a container or used in a for loop. Dedicated |
---|
79 | consumers will be some form of folding function. |
---|
80 | |
---|
81 | Related Work |
---|
82 | ------------ |
---|
83 | Python has a robust iterator tool set. It also has a `range` built-in which |
---|
84 | does many of the same things as the special for loops. |
---|
85 | |
---|
86 | + https://docs.python.org/3/reference/datamodel.html#object.__iter__ |
---|
87 | + https://docs.python.org/3/library/functions.html#func-range |
---|
88 | |
---|
89 | C++ has many iterator tools at well, except for the fact it's `iterators` are |
---|
90 | not what are usually called iterators (as above) but rather an abstraction of |
---|
91 | pointers. |
---|
92 | |
---|
93 | Rust also has a imparative implementation of a functional style of iterators, |
---|
94 | including a great number of standard transformers. Otherwise, it is very |
---|
95 | similar to Python. |
---|
96 | |
---|
97 | + https://doc.rust-lang.org/std/iter/index.html |
---|