boost/hof/fold.hpp

0001 /*=============================================================================
0002     Copyright (c) 2015 Paul Fultz II
0003     fold.h
0004     Distributed under the Boost Software License, Version 1.0. (See accompanying
0005     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 ==============================================================================*/
0007
0008 #ifndef BOOST_HOF_GUARD_FOLD_H
0009 #define BOOST_HOF_GUARD_FOLD_H
0010
0011 /// fold
0012 /// ========
0013 ///
0014 /// Description
0015 /// -----------
0016 ///
0017 /// The `fold` function adaptor uses a binary function to apply a
0018 /// [fold](https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)
0019 /// operation to the arguments passed to the function. Additionally, an
0020 /// optional initial state can be provided, otherwise the first argument is
0021 /// used as the initial state.
0022 ///
0023 /// The arguments to the binary function, take first the state and then the
0024 /// argument.
0025 ///
0026 /// Synopsis
0027 /// --------
0028 ///
0029 ///     template<class F, class State>
0030 ///     constexpr fold_adaptor<F, State> fold(F f, State s);
0031 ///
0032 ///     template<class F>
0033 ///     constexpr fold_adaptor<F> fold(F f);
0034 ///
0035 /// Semantics
0036 /// ---------
0037 ///
0038 ///     assert(fold(f, z)() == z);
0039 ///     assert(fold(f, z)(x, xs...) == fold(f, f(z, x))(xs...));
0040 ///     assert(fold(f)(x) == x);
0041 ///     assert(fold(f)(x, y, xs...) == fold(f)(f(x, y), xs...));
0042 ///
0043 /// Requirements
0044 /// ------------
0045 ///
0046 /// State must be:
0047 ///
0048 /// * CopyConstructible
0049 ///
0050 /// F must be:
0051 ///
0052 /// * [BinaryInvocable](BinaryInvocable)
0053 /// * MoveConstructible
0054 ///
0055 /// Example
0056 /// -------
0057 ///
0058 ///     #include <boost/hof.hpp>
0059 ///     #include <cassert>
0060 ///
0061 ///     struct max_f
0062 ///     {
0063 ///         template<class T, class U>
0064 ///         constexpr T operator()(T x, U y) const
0065 ///         {
0066 ///             return x > y ? x : y;
0067 ///         }
0068 ///     };
0069 ///     int main() {
0070 ///         assert(boost::hof::fold(max_f())(2, 3, 4, 5) == 5);
0071 ///     }
0072 ///
0073 /// References
0074 /// ----------
0075 ///
0076 /// * [Fold](https://en.wikipedia.org/wiki/Fold_(higher-order_function))
0077 /// * [Variadic sum](<Variadic sum>)
0078 ///
0079
0080 #include <boost/hof/detail/callable_base.hpp>
0081 #include <boost/hof/detail/delegate.hpp>
0082 #include <boost/hof/detail/compressed_pair.hpp>
0083 #include <boost/hof/detail/move.hpp>
0084 #include <boost/hof/detail/make.hpp>
0085 #include <boost/hof/detail/static_const_var.hpp>
0086
0087 namespace boost { namespace hof { namespace detail {
0088
0089 struct v_fold
0090 {
0091     BOOST_HOF_RETURNS_CLASS(v_fold);
0092     template<class F, class State, class T, class... Ts>
0093     constexpr BOOST_HOF_SFINAE_MANUAL_RESULT(const v_fold&, id_<const F&>, result_of<const F&, id_<State>, id_<T>>, id_<Ts>...)
0094     operator()(const F& f, State&& state, T&& x, Ts&&... xs) const BOOST_HOF_SFINAE_MANUAL_RETURNS
0095     (
0096         (*BOOST_HOF_CONST_THIS)(f, f(BOOST_HOF_FORWARD(State)(state), BOOST_HOF_FORWARD(T)(x)), BOOST_HOF_FORWARD(Ts)(xs)...)
0097     );
0098
0099     template<class F, class State>
0100     constexpr State operator()(const F&, State&& state) const noexcept
0101     {
0102         return BOOST_HOF_FORWARD(State)(state);
0103     }
0104 };
0105
0106 }
0107
0108 template<class F, class State=void>
0109 struct fold_adaptor
0110 : detail::compressed_pair<detail::callable_base<F>, State>
0111 {
0112     typedef detail::compressed_pair<detail::callable_base<F>, State> base_type;
0113     BOOST_HOF_INHERIT_CONSTRUCTOR(fold_adaptor, base_type)
0114
0115     template<class... Ts>
0116     constexpr const detail::callable_base<F>& base_function(Ts&&... xs) const noexcept
0117     {
0118         return this->first(xs...);
0119     }
0120
0121     template<class... Ts>
0122     constexpr State get_state(Ts&&... xs) const noexcept
0123     {
0124         return this->second(xs...);
0125     }
0126
0127     BOOST_HOF_RETURNS_CLASS(fold_adaptor);
0128
0129     template<class... Ts>
0130     constexpr BOOST_HOF_SFINAE_RESULT(detail::v_fold, id_<const detail::callable_base<F>&>, id_<State>, id_<Ts>...)
0131     operator()(Ts&&... xs) const BOOST_HOF_SFINAE_RETURNS
0132     (
0133         detail::v_fold()(
0134             BOOST_HOF_MANGLE_CAST(const detail::callable_base<F>&)(BOOST_HOF_CONST_THIS->base_function(xs...)),
0135             BOOST_HOF_MANGLE_CAST(State)(BOOST_HOF_CONST_THIS->get_state(xs...)),
0136             BOOST_HOF_FORWARD(Ts)(xs)...
0137         )
0138     )
0139 };
0140
0141
0142 template<class F>
0143 struct fold_adaptor<F, void>
0144 : detail::callable_base<F>
0145 {
0146     BOOST_HOF_INHERIT_CONSTRUCTOR(fold_adaptor, detail::callable_base<F>)
0147
0148     template<class... Ts>
0149     constexpr const detail::callable_base<F>& base_function(Ts&&... xs) const noexcept
0150     {
0151         return boost::hof::always_ref(*this)(xs...);
0152     }
0153
0154     BOOST_HOF_RETURNS_CLASS(fold_adaptor);
0155
0156     template<class... Ts>
0157     constexpr BOOST_HOF_SFINAE_RESULT(detail::v_fold, id_<const detail::callable_base<F>&>, id_<Ts>...)
0158     operator()(Ts&&... xs) const BOOST_HOF_SFINAE_RETURNS
0159     (
0160         detail::v_fold()(
0161             BOOST_HOF_MANGLE_CAST(const detail::callable_base<F>&)(BOOST_HOF_CONST_THIS->base_function(xs...)),
0162             BOOST_HOF_FORWARD(Ts)(xs)...
0163         )
0164     )
0165 };
0166
0167 BOOST_HOF_DECLARE_STATIC_VAR(fold, detail::make<fold_adaptor>);
0168
0169 }} // namespace boost::hof
0170
0171 #endif