Currying for templates in C++ metaprogramming

Question

This is more of a conceptual question. I'm trying to find the easiest way of converting a two-arg template (the arguments being types) into a one-arg template. I.e., binding one of the types.

This would be the meta-programming equivalent of bind in boost/std. My example includes a possible use-case, which is, passing std::is_same as template argument to a template that takes a one-arg template template argument (std::is_same being a two-arg template), i.e. to TypeList::FindIf. The TypeList is not fully implemented here, neither is FindIf, but you get the idea. It takes a "unary predicate" and returns the type for which that predicate is true, or void if not such type.

I have 2 working variants but the first is not a one-liner and the 2nd uses a rather verbose BindFirst contraption, that would not work for non-type template arguments. Is there a simple way to write such a one-liner? I believe the procedure I'm looking for is called currying.

#include <iostream>

template<template<typename, typename> class Function, typename FirstArg>
struct BindFirst
{
    template<typename SecondArg>
    using Result = Function<FirstArg, SecondArg>;
};

//template<typename Type> using IsInt = BindFirst<_EqualTypes, int>::Result<Type>;
template<typename Type> using IsInt = std::is_same<int, Type>;


struct TypeList
{
    template<template<typename> class Predicate>
    struct FindIf
    {
        // this needs to be implemented, return void for now
        typedef void Result;
    };
};

int main()
{

  static_assert(IsInt<int>::value, "");
  static_assert(!IsInt<float>::value, "");


  // variant #1: using the predefined parameterized type alias as predicate
  typedef TypeList::FindIf<IsInt>::Result Result1;

  // variant #2: one-liner, using BindFirst and std::is_same directly
  typedef TypeList::FindIf< BindFirst<std::is_same, int>::Result>::Result Result2;

  // variant #3: one-liner, using currying?
  //typedef TypeList::FindIf<std::is_same<int, _>>::Result Result2;

  return 0;
}

Click here for code in online compiler GodBolt.

Answer 1

Yeah, I had this issue to. It took a few iterations to figure out a decent way to do this. Basically, to do this, we need to specify a reasonable representation of what we want and need. I borrowed some aspects from std::bind() in that I want to specify the template that I wish to bind and the parameters that I want to bind to it. Then, within that type, there should be a template that will allow you to pass a set of types.

So our interface will look like this:

template <template <typename...> class OP, typename...Ts>
struct tbind;

Now our implementation will have those parameters plus a container of types that will be applied at the end:

template <template <typename...> class OP, typename PARAMS, typename...Ts>
struct tbind_impl;

Our base case will give us a template type, which I'll call ttype, that'll return a template of the contained types:

template <template <typename...> class OP, typename...Ss>
struct tbind_impl<OP, std::tuple<Ss...>>
{
    template<typename...Us>
    using ttype = OP<Ss...>;
};

Then we have the case of moving the next type into the container and having ttype refer to the ttype in the slightly simpler base case:

template <template <typename...> class OP, typename T, typename...Ts, typename...Ss>
struct tbind_impl<OP, std::tuple<Ss...>, T, Ts...>
{
    template<typename...Us>
    using ttype = typename tbind_impl<
          OP
        , std::tuple<Ss..., T>
        , Ts...
    >::template ttype<Us...>;
};

And finally, we need a remap of the templates that will be passed to ttype:

template <template <typename...> class OP, size_t I, typename...Ts, typename...Ss>
struct tbind_impl<OP, std::tuple<Ss...>, std::integral_constant<size_t, I>, Ts...>
{
    template<typename...Us>
    using ttype = typename tbind_impl<
          OP
        , typename std::tuple<
              Ss...
            , typename std::tuple_element<
                  I
                , typename std::tuple<Us...>
              >::type
          >
        , Ts...
    >::template ttype<Us...>;

Now, since programmers are lazy, and don't want to type std::integral_constant<size_t, N> for each parameter to remap, we specify some aliases:

using t0 = std::integral_constant<size_t, 0>;
using t1 = std::integral_constant<size_t, 1>;
using t2 = std::integral_constant<size_t, 2>;
...

Oh, almost forgot the implementation of our interface:

template <template <typename...> class OP, typename...Ts>
struct tbind : detail::tbind_impl<OP, std::tuple<>, Ts...>
{};

Note that tbind_impl was placed in a detail namespace.

And voila, tbind!

Unfortunately, there is a defect prior to c++17. If you pass tbind<parms>::ttype to a template that expects a template with a particular number of parameters, you will get an error as the number of parameters don't match (specific number doesn't match any number). This complicates things slightly requiring an additional level of indirection. :(

template <template <typename...> class OP, size_t N>
struct any_to_specific;

template <template <typename...> class OP>
struct any_to_specific<OP, 1> 
{
    template <typename T0>
    using ttype = OP<T0>;
};

template <template <typename...> class OP>
struct any_to_specific<OP, 2>
{
    template <typename T0, typename T1>
    using ttype = OP<T0, T1>;
};
...

Using that to wrap tbind will force the compiler to recognize the template having the specified number of parameters.

Example usage:

static_assert(!tbind<std::is_same, float, t0>::ttype<int>::value, "failed");

static_assert( tbind<std::is_same, int  , t0>::ttype<int>::value, "failed");

static_assert(!any_to_specific<
      tbind<std::is_same, float, t0>::ttype
    , 1
>::ttype<int>::value, "failed");

static_assert( any_to_specific<
      tbind<std::is_same, int  , t0>::ttype
    , 1
 >::ttype<int>::value, "failed");

All of which succeed.

Answer 2

I think the typical way of doing this is keep everything in the world of types. Don't take template templates - they're messy. Let's write a metafunction named ApplyAnInt that will take a "metafunction class" and apply int to it:

template <typename Func>
struct ApplyAnInt {
    using type = typename Func::template apply<int>;
};

Where a simple metafunction class might be just checking if the given type is an int:

struct IsInt {
    template <typename T>
    using apply = std::is_same<T, int>;
};

static_assert(ApplyAnInt<IsInt>::type::value, "");

Now the goal is to support:

static_assert(ApplyAnInt<std::is_same<_, int>>::type::value, "");

We can do that. We're going to call types that contain _ "lambda expressions", and write a metafunction called lambda which will either forward a metafunction class that isn't a lambda expression, or produce a new metafunction if it is:

template <typename T, typename = void>
struct lambda {
    using type = T;
};

template <typename T>
struct lambda<T, std::enable_if_t<is_lambda_expr<T>::value>>
{
    struct type {
        template <typename U>
        using apply = typename apply_lambda<T, U>::type;
    };
};

template <typename T>
using lambda_t = typename lambda<T>::type;

So we update our original metafunction:

template <typename Func>
struct ApplyAnInt
{
    using type = typename lambda_t<Func>::template apply<int>;
};

Now that leaves two things: we need is_lambda_expr and apply_lambda. Those actually aren't so bad at all. For the former, we'll see if it's an instantiation of a class template in which one of the types is _:

template <typename T>
struct is_lambda_expr : std::false_type { };

template <template <typename...> class C, typename... Ts>
struct is_lambda_expr<C<Ts...>> : contains_type<_, Ts...> { };

And for apply_lambda, we just will substitute the _ with the given type:

template <typename T, typename U>
struct apply_lambda;

template <template <typename...> class C, typename... Ts, typename U>
struct apply_lambda<C<Ts...>, U> {
    using type = typename C<std::conditional_t<std::is_same<Ts, _>::value, U, Ts>...>::type;
};

And that's all you need actually. I'll leave extending this out to support arg_<N> as an exercise to the reader.