1/*!
2@file
3Forward declares `boost::hana::Sequence`.
4
5Copyright Louis Dionne 2013-2022
6Distributed 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
17namespace boost { namespace hana {
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}} // end namespace boost::hana
164
165#endif // !BOOST_HANA_FWD_CONCEPT_SEQUENCE_HPP
166

source code of boost/libs/hana/include/boost/hana/fwd/concept/sequence.hpp