ceph/src/boost/libs/hana/include/boost/hana/fwd/concept/iterable.hpp

   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