sequence.hpp 7.2 KB

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