1 /*! 2 @file 3 Forward declares `boost::hana::Sequence`. 4 5 @copyright Louis Dionne 2013-2017 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 166