1 /*! 2 @file 3 Defines `boost::hana::demux`. 4 5 @copyright Louis Dionne 2013-2017 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 __anon34b5b7d50102(auto&& f) 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::at_c<0>(storage_)( 215 hana::at_c<n+1>(storage_)(x...)... 216 ); 217 } 218 219 template <typename ...X> 220 constexpr decltype(auto) operator()(X&& ...x) & { 221 return hana::at_c<0>(storage_)( 222 hana::at_c<n+1>(storage_)(x...)... 223 ); 224 } 225 226 template <typename ...X> 227 constexpr decltype(auto) operator()(X&& ...x) && { 228 return static_cast<F&&>(hana::at_c<0>(storage_))( 229 static_cast<G&&>(hana::at_c<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::at_c<0>(storage_)( 246 hana::at_c<1>(storage_)(static_cast<X&&>(x)...) 247 ); 248 } 249 250 template <typename ...X> 251 constexpr decltype(auto) operator()(X&& ...x) & { 252 return hana::at_c<0>(storage_)( 253 hana::at_c<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::at_c<0>(storage_))( 260 static_cast<G&&>(hana::at_c<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 270