]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Iterable`. | |
4 | ||
5 | @copyright Louis Dionne 2013-2016 | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_FWD_CONCEPT_ITERABLE_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_ITERABLE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-Iterable Iterable | |
19 | //! The `Iterable` concept represents data structures supporting external | |
20 | //! iteration. | |
21 | //! | |
22 | //! Intuitively, an `Iterable` can be seen as a kind of container whose | |
23 | //! elements can be pulled out one at a time. An `Iterable` also provides | |
24 | //! a way to know when the _container_ is empty, i.e. when there are no | |
25 | //! more elements to pull out. | |
26 | //! | |
27 | //! Whereas `Foldable` represents data structures supporting internal | |
28 | //! iteration with the ability to accumulate a result, the `Iterable` | |
29 | //! concept allows inverting the control of the iteration. This is more | |
30 | //! flexible than `Foldable`, since it allows iterating over only some | |
31 | //! part of the structure. This, in turn, allows `Iterable` to work on | |
32 | //! infinite structures, while trying to fold such a structure would | |
33 | //! never finish. | |
34 | //! | |
35 | //! | |
36 | //! Minimal complete definition | |
37 | //! --------------------------- | |
38 | //! `at`, `drop_front` and `is_empty` | |
39 | //! | |
40 | //! | |
41 | //! @anchor Iterable-lin | |
42 | //! The linearization of an `Iterable` | |
43 | //! ---------------------------------- | |
44 | //! Intuitively, for an `Iterable` structure `xs`, the _linearization_ of | |
45 | //! `xs` is the sequence of all the elements in `xs` as if they had been | |
46 | //! put in a (possibly infinite) list: | |
47 | //! @code | |
48 | //! linearization(xs) = [x1, x2, x3, ...] | |
49 | //! @endcode | |
50 | //! | |
51 | //! The `n`th element of the linearization of an `Iterable` can be | |
52 | //! accessed with the `at` function. In other words, `at(xs, n) == xn`. | |
53 | //! | |
54 | //! Note that this notion is precisely the extension of the [linearization] | |
55 | //! (@ref Foldable-lin) notion of `Foldable`s to the infinite case. This | |
56 | //! notion is useful for expressing various properties of `Iterable`s, | |
57 | //! and is used for that elsewhere in the documentation. | |
58 | //! | |
59 | //! | |
60 | //! Compile-time `Iterable`s | |
61 | //! ------------------------ | |
62 | //! A _compile-time_ `Iterable` is an `Iterable` for which `is_empty` | |
63 | //! returns a compile-time `Logical`. These structures allow iteration | |
64 | //! to be done at compile-time, in the sense that the "loop" doing the | |
65 | //! iteration can be unrolled because the total length of the structure | |
66 | //! is kown at compile-time. | |
67 | //! | |
68 | //! In particular, note that being a compile-time `Iterable` has nothing | |
69 | //! to do with being finite or infinite. For example, it would be possible | |
70 | //! to create a sequence representing the Pythagorean triples as | |
71 | //! `integral_constant`s. Such a sequence would be infinite, but iteration | |
72 | //! on the sequence would still be done at compile-time. However, if one | |
73 | //! tried to iterate over _all_ the elements of the sequence, the compiler | |
74 | //! would loop indefinitely, in contrast to your program looping | |
75 | //! indefinitely if the sequence was a runtime one. | |
76 | //! | |
77 | //! __In the current version of the library, only compile-time `Iterable`s | |
78 | //! are supported.__ While it would be possible in theory to support | |
79 | //! runtime `Iterable`s, doing it efficiently is the subject of some | |
80 | //! research. In particular, follow [this issue][1] for the current | |
81 | //! status of runtime `Iterable`s. | |
82 | //! | |
83 | //! | |
84 | //! Laws | |
85 | //! ---- | |
86 | //! First, we require the equality of two `Iterable`s to be related to the | |
87 | //! equality of the elements in their linearizations. More specifically, | |
88 | //! if `xs` and `ys` are two `Iterable`s of data type `It`, then | |
89 | //! @code | |
90 | //! xs == ys => at(xs, i) == at(ys, i) for all i | |
91 | //! @endcode | |
92 | //! | |
93 | //! This conveys that two `Iterable`s must have the same linearization | |
94 | //! in order to be considered equal. | |
95 | //! | |
96 | //! Secondly, since every `Iterable` is also a `Searchable`, we require | |
97 | //! the models of `Iterable` and `Searchable` to be consistent. This is | |
98 | //! made precise by the following laws. For any `Iterable` `xs` with a | |
99 | //! linearization of `[x1, x2, x3, ...]`, | |
100 | //! @code | |
101 | //! any_of(xs, equal.to(z)) <=> xi == z | |
102 | //! @endcode | |
103 | //! for some _finite_ index `i`. Furthermore, | |
104 | //! @code | |
105 | //! find_if(xs, pred) == just(the first xi such that pred(xi) is satisfied) | |
106 | //! @endcode | |
107 | //! or `nothing` if no such `xi` exists. | |
108 | //! | |
109 | //! | |
110 | //! Refined concepts | |
111 | //! ---------------- | |
112 | //! 1. `Searchable` (free model)\n | |
113 | //! Any `Iterable` gives rise to a model of `Searchable`, where the keys | |
114 | //! and the values are both the elements in the structure. Searching for | |
115 | //! a key is just doing a linear search through the elements of the | |
116 | //! structure. | |
117 | //! @include example/iterable/searchable.cpp | |
118 | //! | |
119 | //! 2. `Foldable` for finite `Iterable`s\n | |
120 | //! Every finite `Iterable` gives rise to a model of `Foldable`. For | |
121 | //! these models to be consistent, we require the models of both `Foldable` | |
122 | //! and `Iterable` to have the same linearization. | |
123 | //! | |
124 | //! @note | |
125 | //! As explained above, `Iterable`s are also `Searchable`s and their | |
126 | //! models have to be consistent. By the laws presented here, it also | |
127 | //! means that the `Foldable` model for finite `Iterable`s has to be | |
128 | //! consistent with the `Searchable` model. | |
129 | //! | |
130 | //! For convenience, finite `Iterable`s must only provide a definition of | |
131 | //! `length` to model the `Foldable` concept; defining the more powerful | |
132 | //! `unpack` or `fold_left` is not necessary (but still possible). The | |
133 | //! default implementation of `unpack` derived from `Iterable` + `length` | |
134 | //! uses the fact that `at(xs, i)` denotes the `i`th element of `xs`'s | |
135 | //! linearization, and that the linearization of a finite `Iterable` must | |
136 | //! be the same as its linearization as a `Foldable`. | |
137 | //! | |
138 | //! | |
139 | //! Concrete models | |
140 | //! --------------- | |
141 | //! `hana::tuple`, `hana::string`, `hana::range` | |
142 | //! | |
143 | //! | |
144 | //! [1]: https://github.com/boostorg/hana/issues/40 | |
145 | template <typename It> | |
146 | struct Iterable; | |
147 | BOOST_HANA_NAMESPACE_END | |
148 | ||
149 | #endif // !BOOST_HANA_FWD_CONCEPT_ITERABLE_HPP |