scan_left.hpp 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
  1. /*!
  2. @file
  3. Forward declares `boost::hana::scan_left`.
  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_SCAN_LEFT_HPP
  9. #define BOOST_HANA_FWD_SCAN_LEFT_HPP
  10. #include <boost/hana/config.hpp>
  11. #include <boost/hana/core/when.hpp>
  12. BOOST_HANA_NAMESPACE_BEGIN
  13. //! Fold a Sequence to the left and return a list containing the
  14. //! successive reduction states.
  15. //! @ingroup group-Sequence
  16. //!
  17. //! Like `fold_left`, `scan_left` reduces a sequence to a single value
  18. //! using a binary operation. However, unlike `fold_left`, it builds up
  19. //! a sequence of the intermediary results computed along the way and
  20. //! returns that instead of only the final reduction state. Like
  21. //! `fold_left`, `scan_left` can be used with or without an initial
  22. //! reduction state.
  23. //!
  24. //! When the sequence is empty, two things may arise. If an initial state
  25. //! was provided, a singleton list containing that state is returned.
  26. //! Otherwise, if no initial state was provided, an empty list is
  27. //! returned. In particular, unlike for `fold_left`, using `scan_left`
  28. //! on an empty sequence without an initial state is not an error.
  29. //!
  30. //! More specifically, `scan_left([x1, ..., xn], state, f)` is a sequence
  31. //! whose `i`th element is equivalent to `fold_left([x1, ..., xi], state, f)`.
  32. //! The no-state variant is handled in an analogous way. For illustration,
  33. //! consider this left fold on a short sequence:
  34. //! @code
  35. //! fold_left([x1, x2, x3], state, f) == f(f(f(state, x1), x2), x3)
  36. //! @endcode
  37. //!
  38. //! The analogous sequence generated with `scan_left` will be
  39. //! @code
  40. //! scan_left([x1, x2, x3], state, f) == [
  41. //! state,
  42. //! f(state, x1),
  43. //! f(f(state, x1), x2),
  44. //! f(f(f(state, x1), x2), x3)
  45. //! ]
  46. //! @endcode
  47. //!
  48. //! Similarly, consider this left fold (without an initial state) on
  49. //! a short sequence:
  50. //! @code
  51. //! fold_left([x1, x2, x3, x4], f) == f(f(f(x1, x2), x3), x4)
  52. //! @endcode
  53. //!
  54. //! The analogous sequence generated with `scan_left` will be
  55. //! @code
  56. //! scan_left([x1, x2, x3, x4], f) == [
  57. //! x1,
  58. //! f(x1, x2),
  59. //! f(f(x1, x2), x3),
  60. //! f(f(f(x1, x2), x3), x4)
  61. //! ]
  62. //! @endcode
  63. //!
  64. //! @param xs
  65. //! The sequence to scan from the left.
  66. //!
  67. //! @param state
  68. //! The (optional) initial reduction state.
  69. //!
  70. //! @param f
  71. //! A binary function called as `f(state, x)`, where `state` is the
  72. //! result accumulated so far and `x` is an element in the sequence.
  73. //! If no initial state is provided, `f` is called as `f(x1, x2)`,
  74. //! where `x1` and `x2` are both elements of the sequence.
  75. //!
  76. //!
  77. //! Example
  78. //! -------
  79. //! @include example/scan_left.cpp
  80. #ifdef BOOST_HANA_DOXYGEN_INVOKED
  81. constexpr auto scan_left = [](auto&& xs[, auto&& state], auto const& f) {
  82. return tag-dispatched;
  83. };
  84. #else
  85. template <typename S, typename = void>
  86. struct scan_left_impl : scan_left_impl<S, when<true>> { };
  87. struct scan_left_t {
  88. template <typename Xs, typename State, typename F>
  89. constexpr auto operator()(Xs&& xs, State&& state, F const& f) const;
  90. template <typename Xs, typename F>
  91. constexpr auto operator()(Xs&& xs, F const& f) const;
  92. };
  93. constexpr scan_left_t scan_left{};
  94. #endif
  95. BOOST_HANA_NAMESPACE_END
  96. #endif // !BOOST_HANA_FWD_SCAN_LEFT_HPP