]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Defines `boost::hana::demux`. | |
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_FUNCTIONAL_DEMUX_HPP | |
11 | #define BOOST_HANA_FUNCTIONAL_DEMUX_HPP | |
12 | ||
13 | #include <boost/hana/basic_tuple.hpp> | |
14 | #include <boost/hana/config.hpp> | |
15 | #include <boost/hana/detail/decay.hpp> | |
16 | ||
17 | #include <cstddef> | |
18 | #include <utility> | |
19 | ||
20 | ||
21 | BOOST_HANA_NAMESPACE_BEGIN | |
22 | //! @ingroup group-functional | |
23 | //! Invoke a function with the results of invoking other functions | |
24 | //! on its arguments. | |
25 | //! | |
26 | //! Specifically, `demux(f)(g...)` is a function such that | |
27 | //! @code | |
28 | //! demux(f)(g...)(x...) == f(g(x...)...) | |
29 | //! @endcode | |
30 | //! | |
31 | //! Each `g` is called with all the arguments, and then `f` is called | |
32 | //! with the result of each `g`. Hence, the arity of `f` must match | |
33 | //! the number of `g`s. | |
34 | //! | |
35 | //! This is called `demux` because of a vague similarity between this | |
36 | //! device and a demultiplexer in signal processing. `demux` takes what | |
37 | //! can be seen as a continuation (`f`), a bunch of functions to split a | |
38 | //! signal (`g...`) and zero or more arguments representing the signal | |
39 | //! (`x...`). Then, it calls the continuation with the result of | |
40 | //! splitting the signal with whatever functions where given. | |
41 | //! | |
42 | //! @note | |
43 | //! When used with two functions only, `demux` is associative. In other | |
44 | //! words (and noting `demux(f, g) = demux(f)(g)` to ease the notation), | |
45 | //! it is true that `demux(demux(f, g), h) == demux(f, demux(g, h))`. | |
46 | //! | |
47 | //! | |
48 | //! Signature | |
49 | //! --------- | |
50 | //! The signature of `demux` is | |
51 | //! \f[ | |
52 | //! \mathtt{demux} : | |
53 | //! (B_1 \times \dotsb \times B_n \to C) | |
54 | //! \to ((A_1 \times \dotsb \times A_n \to B_1) | |
55 | //! \times \dotsb | |
56 | //! \times (A_1 \times \dotsb \times A_n \to B_n)) | |
57 | //! \to (A_1 \times \dotsb \times A_n \to C) | |
58 | //! \f] | |
59 | //! | |
60 | //! This can be rewritten more tersely as | |
61 | //! \f[ | |
62 | //! \mathtt{demux} : | |
63 | //! \left(\prod_{i=1}^n B_i \to C \right) | |
64 | //! \to \prod_{j=1}^n \left(\prod_{i=1}^n A_i \to B_j \right) | |
65 | //! \to \left(\prod_{i=1}^n A_i \to C \right) | |
66 | //! \f] | |
67 | //! | |
68 | //! | |
69 | //! Link with normal composition | |
70 | //! ---------------------------- | |
71 | //! The signature of `compose` is | |
72 | //! \f[ | |
73 | //! \mathtt{compose} : (B \to C) \times (A \to B) \to (A \to C) | |
74 | //! \f] | |
75 | //! | |
76 | //! A valid observation is that this coincides exactly with the type | |
77 | //! of `demux` when used with a single unary function. Actually, both | |
78 | //! functions are equivalent: | |
79 | //! @code | |
80 | //! demux(f)(g)(x) == compose(f, g)(x) | |
81 | //! @endcode | |
82 | //! | |
83 | //! However, let's now consider the curried version of `compose`, | |
84 | //! `curry<2>(compose)`: | |
85 | //! \f[ | |
86 | //! \mathtt{curry_2(compose)} : (B \to C) \to ((A \to B) \to (A \to C)) | |
87 | //! \f] | |
88 | //! | |
89 | //! For the rest of this explanation, we'll just consider the curried | |
90 | //! version of `compose` and so we'll use `compose` instead of | |
91 | //! `curry<2>(compose)` to lighten the notation. With currying, we can | |
92 | //! now consider `compose` applied to itself: | |
93 | //! \f[ | |
94 | //! \mathtt{compose(compose, compose)} : | |
95 | //! (B \to C) \to (A_1 \to A_2 \to B) \to (A_1 \to A_2 \to C) | |
96 | //! \f] | |
97 | //! | |
98 | //! If we uncurry deeply the above expression, we obtain | |
99 | //! \f[ | |
100 | //! \mathtt{compose(compose, compose)} : | |
101 | //! (B \to C) \times (A_1 \times A_2 \to B) \to (A_1 \times A_2 \to C) | |
102 | //! \f] | |
103 | //! | |
104 | //! This signature is exactly the same as that of `demux` when given a | |
105 | //! single binary function, and indeed they are equivalent definitions. | |
106 | //! We can also generalize this further by considering | |
107 | //! `compose(compose(compose, compose), compose)`: | |
108 | //! \f[ | |
109 | //! \mathtt{compose(compose(compose, compose), compose)} : | |
110 | //! (B \to C) \to (A_1 \to A_2 \to A_3 \to B) | |
111 | //! \to (A_1 \to A_2 \to A_3 \to C) | |
112 | //! \f] | |
113 | //! | |
114 | //! which uncurries to | |
115 | //! \f[ | |
116 | //! \mathtt{compose(compose(compose, compose), compose)} : | |
117 | //! (B \to C) \times (A_1 \times A_2 \times A_3 \to B) | |
118 | //! \to (A_1 \times A_2 \times A_3 \to C) | |
119 | //! \f] | |
120 | //! | |
121 | //! This signature is exactly the same as that of `demux` when given a | |
122 | //! single ternary function. Hence, for a single n-ary function `g`, | |
123 | //! `demux(f)(g)` is equivalent to the n-times composition of `compose` | |
124 | //! with itself, applied to `g` and `f`: | |
125 | //! @code | |
126 | //! demux(f)(g) == fold_left([compose, ..., compose], id, compose)(g, f) | |
127 | //! // ^^^^^^^^^^^^^^^^^^^^^ n times | |
128 | //! @endcode | |
129 | //! | |
130 | //! More information on this insight can be seen [here][1]. Also, I'm | |
131 | //! not sure how this insight could be generalized to more than one | |
132 | //! function `g`, or if that is even possible. | |
133 | //! | |
134 | //! | |
135 | //! Proof of associativity in the binary case | |
136 | //! ----------------------------------------- | |
137 | //! As explained above, `demux` is associative when it is used with | |
138 | //! two functions only. Indeed, given functions `f`, `g` and `h` with | |
139 | //! suitable signatures, we have | |
140 | //! @code | |
141 | //! demux(f)(demux(g)(h))(x...) == f(demux(g)(h)(x...)) | |
142 | //! == f(g(h(x...))) | |
143 | //! @endcode | |
144 | //! | |
145 | //! On the other hand, we have | |
146 | //! @code | |
147 | //! demux(demux(f)(g))(h)(x...) == demux(f)(g)(h(x...)) | |
148 | //! == f(g(h(x...))) | |
149 | //! @endcode | |
150 | //! | |
151 | //! and hence `demux` is associative in the binary case. | |
152 | //! | |
153 | //! | |
154 | //! Example | |
155 | //! ------- | |
156 | //! @include example/functional/demux.cpp | |
157 | //! | |
158 | //! [1]: http://stackoverflow.com/q/5821089/627587 | |
159 | #ifdef BOOST_HANA_DOXYGEN_INVOKED | |
160 | constexpr auto demux = [](auto&& f) { | |
161 | return [perfect-capture](auto&& ...g) { | |
162 | return [perfect-capture](auto&& ...x) -> decltype(auto) { | |
163 | // x... can't be forwarded unless there is a single g | |
164 | // function, or that could cause double-moves. | |
165 | return forwarded(f)(forwarded(g)(x...)...); | |
166 | }; | |
167 | }; | |
168 | }; | |
169 | #else | |
170 | template <typename F> | |
171 | struct pre_demux_t; | |
172 | ||
173 | struct make_pre_demux_t { | |
174 | struct secret { }; | |
175 | template <typename F> | |
176 | constexpr pre_demux_t<typename detail::decay<F>::type> operator()(F&& f) const { | |
177 | return {static_cast<F&&>(f)}; | |
178 | } | |
179 | }; | |
180 | ||
181 | template <typename Indices, typename F, typename ...G> | |
182 | struct demux_t; | |
183 | ||
184 | template <typename F> | |
185 | struct pre_demux_t { | |
186 | F f; | |
187 | ||
188 | template <typename ...G> | |
189 | constexpr demux_t<std::make_index_sequence<sizeof...(G)>, F, | |
190 | typename detail::decay<G>::type...> | |
191 | operator()(G&& ...g) const& { | |
192 | return {make_pre_demux_t::secret{}, this->f, static_cast<G&&>(g)...}; | |
193 | } | |
194 | ||
195 | template <typename ...G> | |
196 | constexpr demux_t<std::make_index_sequence<sizeof...(G)>, F, | |
197 | typename detail::decay<G>::type...> | |
198 | operator()(G&& ...g) && { | |
199 | return {make_pre_demux_t::secret{}, static_cast<F&&>(this->f), static_cast<G&&>(g)...}; | |
200 | } | |
201 | }; | |
202 | ||
203 | template <std::size_t ...n, typename F, typename ...G> | |
204 | struct demux_t<std::index_sequence<n...>, F, G...> { | |
205 | template <typename ...T> | |
206 | constexpr demux_t(make_pre_demux_t::secret, T&& ...t) | |
207 | : storage_{static_cast<T&&>(t)...} | |
208 | { } | |
209 | ||
210 | basic_tuple<F, G...> storage_; | |
211 | ||
212 | template <typename ...X> | |
213 | constexpr decltype(auto) operator()(X&& ...x) const& { | |
214 | return hana::get_impl<0>(storage_)( | |
215 | hana::get_impl<n+1>(storage_)(x...)... | |
216 | ); | |
217 | } | |
218 | ||
219 | template <typename ...X> | |
220 | constexpr decltype(auto) operator()(X&& ...x) & { | |
221 | return hana::get_impl<0>(storage_)( | |
222 | hana::get_impl<n+1>(storage_)(x...)... | |
223 | ); | |
224 | } | |
225 | ||
226 | template <typename ...X> | |
227 | constexpr decltype(auto) operator()(X&& ...x) && { | |
228 | return static_cast<F&&>(hana::get_impl<0>(storage_))( | |
229 | static_cast<G&&>(hana::get_impl<n+1>(storage_))(x...)... | |
230 | ); | |
231 | } | |
232 | }; | |
233 | ||
234 | template <typename F, typename G> | |
235 | struct demux_t<std::index_sequence<0>, F, G> { | |
236 | template <typename ...T> | |
237 | constexpr demux_t(make_pre_demux_t::secret, T&& ...t) | |
238 | : storage_{static_cast<T&&>(t)...} | |
239 | { } | |
240 | ||
241 | basic_tuple<F, G> storage_; | |
242 | ||
243 | template <typename ...X> | |
244 | constexpr decltype(auto) operator()(X&& ...x) const& { | |
245 | return hana::get_impl<0>(storage_)( | |
246 | hana::get_impl<1>(storage_)(static_cast<X&&>(x)...) | |
247 | ); | |
248 | } | |
249 | ||
250 | template <typename ...X> | |
251 | constexpr decltype(auto) operator()(X&& ...x) & { | |
252 | return hana::get_impl<0>(storage_)( | |
253 | hana::get_impl<1>(storage_)(static_cast<X&&>(x)...) | |
254 | ); | |
255 | } | |
256 | ||
257 | template <typename ...X> | |
258 | constexpr decltype(auto) operator()(X&& ...x) && { | |
259 | return static_cast<F&&>(hana::get_impl<0>(storage_))( | |
260 | static_cast<G&&>(hana::get_impl<1>(storage_))(static_cast<X&&>(x)...) | |
261 | ); | |
262 | } | |
263 | }; | |
264 | ||
265 | constexpr make_pre_demux_t demux{}; | |
266 | #endif | |
267 | BOOST_HANA_NAMESPACE_END | |
268 | ||
269 | #endif // !BOOST_HANA_FUNCTIONAL_DEMUX_HPP |