boost/hana/functional/demux.hpp

   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
 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