source: doc/proposals/iterators.md @ c8238c0

ADTast-experimental
Last change on this file since c8238c0 was 0e3f80d, checked in by Andrew Beach <ajbeach@…>, 2 years ago

Added some more notes to the iterators proposal.

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