]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Sequence`. | |
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_SEQUENCE_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_SEQUENCE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | #include <boost/hana/core/when.hpp> | |
15 | ||
16 | ||
17 | BOOST_HANA_NAMESPACE_BEGIN | |
18 | //! @ingroup group-concepts | |
19 | //! @defgroup group-Sequence Sequence | |
20 | //! The `Sequence` concept represents generic index-based sequences. | |
21 | //! | |
22 | //! Compared to other abstract concepts, the Sequence concept is very | |
23 | //! specific. It represents generic index-based sequences. The reason | |
24 | //! why such a specific concept is provided is because there are a lot | |
25 | //! of models that behave exactly the same while being implemented in | |
26 | //! wildly different ways. It is useful to regroup all those data types | |
27 | //! under the same umbrella for the purpose of generic programming. | |
28 | //! | |
29 | //! In fact, models of this concept are not only _similar_. They are | |
30 | //! actually _isomorphic_, in a sense that we define below, which is | |
31 | //! a fancy way of rigorously saying that they behave exactly the same | |
32 | //! to an external observer. | |
33 | //! | |
34 | //! | |
35 | //! Minimal complete definition | |
36 | //! --------------------------- | |
37 | //! `Iterable`, `Foldable`, and `make` | |
38 | //! | |
39 | //! The `Sequence` concept does not provide basic methods that could be | |
40 | //! used as a minimal complete definition; instead, it borrows methods | |
41 | //! from other concepts and add laws to them. For this reason, it is | |
42 | //! necessary to specialize the `Sequence` metafunction in Hana's | |
43 | //! namespace to tell Hana that a type is indeed a `Sequence`. Explicitly | |
44 | //! specializing the `Sequence` metafunction can be seen like a seal | |
45 | //! saying "this data type satisfies the additional laws of a `Sequence`", | |
46 | //! since those can't be checked by Hana automatically. | |
47 | //! | |
48 | //! | |
49 | //! Laws | |
50 | //! ---- | |
51 | //! The laws for being a `Sequence` are simple, and their goal is to | |
52 | //! restrict the semantics that can be associated to the functions | |
53 | //! provided by other concepts. First, a `Sequence` must be a finite | |
54 | //! `Iterable` (thus a `Foldable` too). Secondly, for a `Sequence` tag | |
55 | //! `S`, `make<S>(x1, ..., xn)` must be an object of tag `S` and whose | |
56 | //! linearization is `[x1, ..., xn]`. This basically ensures that objects | |
57 | //! of tag `S` are equivalent to their linearization, and that they can | |
58 | //! be created from such a linearization (with `make`). | |
59 | //! | |
60 | //! While it would be possible in theory to handle infinite sequences, | |
61 | //! doing so complicates the implementation of many algorithms. For | |
62 | //! simplicity, the current version of the library only handles finite | |
63 | //! sequences. However, note that this does not affect in any way the | |
64 | //! potential for having infinite `Searchable`s and `Iterable`s. | |
65 | //! | |
66 | //! | |
67 | //! Refined concepts | |
68 | //! ---------------- | |
69 | //! 1. `Comparable` (definition provided automatically)\n | |
70 | //! Two `Sequence`s are equal if and only if they contain the same number | |
71 | //! of elements and their elements at any given index are equal. | |
72 | //! @include example/sequence/comparable.cpp | |
73 | //! | |
74 | //! 2. `Orderable` (definition provided automatically)\n | |
75 | //! `Sequence`s are ordered using the traditional lexicographical ordering. | |
76 | //! @include example/sequence/orderable.cpp | |
77 | //! | |
78 | //! 3. `Functor` (definition provided automatically)\n | |
79 | //! `Sequence`s implement `transform` as the mapping of a function over | |
80 | //! each element of the sequence. This is somewhat equivalent to what | |
81 | //! `std::transform` does to ranges of iterators. Also note that mapping | |
82 | //! a function over an empty sequence returns an empty sequence and never | |
83 | //! applies the function, as would be expected. | |
84 | //! @include example/sequence/functor.cpp | |
85 | //! | |
86 | //! 4. `Applicative` (definition provided automatically)\n | |
87 | //! First, `lift`ing a value into a `Sequence` is the same as creating a | |
88 | //! singleton sequence containing that value. Second, applying a sequence | |
89 | //! of functions to a sequence of values will apply each function to | |
90 | //! all the values in the sequence, and then return a list of all the | |
91 | //! results. In other words, | |
92 | //! @code | |
93 | //! ap([f1, ..., fN], [x1, ..., xM]) == [ | |
94 | //! f1(x1), ..., f1(xM), | |
95 | //! ... | |
96 | //! fN(x1), ..., fN(xM) | |
97 | //! ] | |
98 | //! @endcode | |
99 | //! Example: | |
100 | //! @include example/sequence/applicative.cpp | |
101 | //! | |
102 | //! 5. `Monad` (definition provided automatically)\n | |
103 | //! First, `flaten`ning a `Sequence` takes a sequence of sequences and | |
104 | //! concatenates them to get a larger sequence. In other words, | |
105 | //! @code | |
106 | //! flatten([[a1, ..., aN], ..., [z1, ..., zM]]) == [ | |
107 | //! a1, ..., aN, ..., z1, ..., zM | |
108 | //! ] | |
109 | //! @endcode | |
110 | //! This acts like a `std::tuple_cat` function, except it receives a | |
111 | //! sequence of sequences instead of a variadic pack of sequences to | |
112 | //! flatten.\n | |
113 | //! __Example__: | |
114 | //! @include example/sequence/monad.ints.cpp | |
115 | //! Also note that the model of `Monad` for `Sequence`s can be seen as | |
116 | //! modeling nondeterminism. A nondeterministic computation can be | |
117 | //! modeled as a function which returns a sequence of possible results. | |
118 | //! In this line of thought, `chain`ing a sequence of values into such | |
119 | //! a function will return a sequence of all the possible output values, | |
120 | //! i.e. a sequence of all the values applied to all the functions in | |
121 | //! the sequences.\n | |
122 | //! __Example__: | |
123 | //! @include example/sequence/monad.types.cpp | |
124 | //! | |
125 | //! 6. `MonadPlus` (definition provided automatically)\n | |
126 | //! `Sequence`s are models of the `MonadPlus` concept by considering the | |
127 | //! empty sequence as the unit of `concat`, and sequence concatenation | |
128 | //! as `concat`. | |
129 | //! @include example/sequence/monad_plus.cpp | |
130 | //! | |
131 | //! 7. `Foldable`\n | |
132 | //! The model of `Foldable` for `Sequence`s is uniquely determined by the | |
133 | //! model of `Iterable`. | |
134 | //! @include example/sequence/foldable.cpp | |
135 | //! | |
136 | //! 8. `Iterable`\n | |
137 | //! The model of `Iterable` for `Sequence`s corresponds to iteration over | |
138 | //! each element of the sequence, in order. This model is not provided | |
139 | //! automatically, and it is in fact part of the minimal complete | |
140 | //! definition for the `Sequence` concept. | |
141 | //! @include example/sequence/iterable.cpp | |
142 | //! | |
143 | //! 9. `Searchable` (definition provided automatically)\n | |
144 | //! Searching through a `Sequence` is equivalent to just searching through | |
145 | //! a list of the values it contains. The keys and the values on which | |
146 | //! the search is performed are both the elements of the sequence. | |
147 | //! @include example/sequence/searchable.cpp | |
148 | //! | |
149 | //! | |
150 | //! Concrete models | |
151 | //! --------------- | |
152 | //! `hana::tuple` | |
153 | //! | |
154 | //! | |
155 | //! [1]: http://en.wikipedia.org/wiki/Isomorphism#Isomorphism_vs._bijective_morphism | |
156 | #ifdef BOOST_HANA_DOXYGEN_INVOKED | |
157 | template <typename S> | |
158 | struct Sequence; | |
159 | #else | |
160 | template <typename S, typename = void> | |
161 | struct Sequence : Sequence<S, when<true>> { }; | |
162 | #endif | |
163 | BOOST_HANA_NAMESPACE_END | |
164 | ||
165 | #endif // !BOOST_HANA_FWD_CONCEPT_SEQUENCE_HPP |