• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/*=============================================================================
2    Copyright (c) 2015 Paul Fultz II
3    fold.h
4    Distributed under the Boost Software License, Version 1.0. (See accompanying
5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6==============================================================================*/
7
8#ifndef BOOST_HOF_GUARD_FOLD_H
9#define BOOST_HOF_GUARD_FOLD_H
10
11/// fold
12/// ========
13///
14/// Description
15/// -----------
16///
17/// The `fold` function adaptor uses a binary function to apply a
18/// [fold](https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)
19/// operation to the arguments passed to the function. Additionally, an
20/// optional initial state can be provided, otherwise the first argument is
21/// used as the initial state.
22///
23/// The arguments to the binary function, take first the state and then the
24/// argument.
25///
26/// Synopsis
27/// --------
28///
29///     template<class F, class State>
30///     constexpr fold_adaptor<F, State> fold(F f, State s);
31///
32///     template<class F>
33///     constexpr fold_adaptor<F> fold(F f);
34///
35/// Semantics
36/// ---------
37///
38///     assert(fold(f, z)() == z);
39///     assert(fold(f, z)(x, xs...) == fold(f, f(z, x))(xs...));
40///     assert(fold(f)(x) == x);
41///     assert(fold(f)(x, y, xs...) == fold(f)(f(x, y), xs...));
42///
43/// Requirements
44/// ------------
45///
46/// State must be:
47///
48/// * CopyConstructible
49///
50/// F must be:
51///
52/// * [BinaryInvocable](BinaryInvocable)
53/// * MoveConstructible
54///
55/// Example
56/// -------
57///
58///     #include <boost/hof.hpp>
59///     #include <cassert>
60///
61///     struct max_f
62///     {
63///         template<class T, class U>
64///         constexpr T operator()(T x, U y) const
65///         {
66///             return x > y ? x : y;
67///         }
68///     };
69///     int main() {
70///         assert(boost::hof::fold(max_f())(2, 3, 4, 5) == 5);
71///     }
72///
73/// References
74/// ----------
75///
76/// * [Fold](https://en.wikipedia.org/wiki/Fold_(higher-order_function))
77/// * [Variadic sum](<Variadic sum>)
78///
79
80#include <boost/hof/detail/callable_base.hpp>
81#include <boost/hof/detail/delegate.hpp>
82#include <boost/hof/detail/compressed_pair.hpp>
83#include <boost/hof/detail/move.hpp>
84#include <boost/hof/detail/make.hpp>
85#include <boost/hof/detail/static_const_var.hpp>
86
87namespace boost { namespace hof { namespace detail {
88
89struct v_fold
90{
91    BOOST_HOF_RETURNS_CLASS(v_fold);
92    template<class F, class State, class T, class... Ts>
93    constexpr BOOST_HOF_SFINAE_MANUAL_RESULT(const v_fold&, id_<const F&>, result_of<const F&, id_<State>, id_<T>>, id_<Ts>...)
94    operator()(const F& f, State&& state, T&& x, Ts&&... xs) const BOOST_HOF_SFINAE_MANUAL_RETURNS
95    (
96        (*BOOST_HOF_CONST_THIS)(f, f(BOOST_HOF_FORWARD(State)(state), BOOST_HOF_FORWARD(T)(x)), BOOST_HOF_FORWARD(Ts)(xs)...)
97    );
98
99    template<class F, class State>
100    constexpr State operator()(const F&, State&& state) const noexcept
101    {
102        return BOOST_HOF_FORWARD(State)(state);
103    }
104};
105
106}
107
108template<class F, class State=void>
109struct fold_adaptor
110: detail::compressed_pair<detail::callable_base<F>, State>
111{
112    typedef detail::compressed_pair<detail::callable_base<F>, State> base_type;
113    BOOST_HOF_INHERIT_CONSTRUCTOR(fold_adaptor, base_type)
114
115    template<class... Ts>
116    constexpr const detail::callable_base<F>& base_function(Ts&&... xs) const noexcept
117    {
118        return this->first(xs...);
119    }
120
121    template<class... Ts>
122    constexpr State get_state(Ts&&... xs) const noexcept
123    {
124        return this->second(xs...);
125    }
126
127    BOOST_HOF_RETURNS_CLASS(fold_adaptor);
128
129    template<class... Ts>
130    constexpr BOOST_HOF_SFINAE_RESULT(detail::v_fold, id_<const detail::callable_base<F>&>, id_<State>, id_<Ts>...)
131    operator()(Ts&&... xs) const BOOST_HOF_SFINAE_RETURNS
132    (
133        detail::v_fold()(
134            BOOST_HOF_MANGLE_CAST(const detail::callable_base<F>&)(BOOST_HOF_CONST_THIS->base_function(xs...)),
135            BOOST_HOF_MANGLE_CAST(State)(BOOST_HOF_CONST_THIS->get_state(xs...)),
136            BOOST_HOF_FORWARD(Ts)(xs)...
137        )
138    )
139};
140
141
142template<class F>
143struct fold_adaptor<F, void>
144: detail::callable_base<F>
145{
146    BOOST_HOF_INHERIT_CONSTRUCTOR(fold_adaptor, detail::callable_base<F>)
147
148    template<class... Ts>
149    constexpr const detail::callable_base<F>& base_function(Ts&&... xs) const noexcept
150    {
151        return boost::hof::always_ref(*this)(xs...);
152    }
153
154    BOOST_HOF_RETURNS_CLASS(fold_adaptor);
155
156    template<class... Ts>
157    constexpr BOOST_HOF_SFINAE_RESULT(detail::v_fold, id_<const detail::callable_base<F>&>, id_<Ts>...)
158    operator()(Ts&&... xs) const BOOST_HOF_SFINAE_RETURNS
159    (
160        detail::v_fold()(
161            BOOST_HOF_MANGLE_CAST(const detail::callable_base<F>&)(BOOST_HOF_CONST_THIS->base_function(xs...)),
162            BOOST_HOF_FORWARD(Ts)(xs)...
163        )
164    )
165};
166
167BOOST_HOF_DECLARE_STATIC_VAR(fold, detail::make<fold_adaptor>);
168
169}} // namespace boost::hof
170
171#endif
172