Variadic variadic template templates, again

Question

I have seen e.g. a relevant question on the same issue, but I have a different problem, which I think cannot be solved in any other way.

Here is function any that computes whether unary predicate F is true for any of the elements in a template argument pack representation (list of types) P:

template <template <typename...> class F, typename P>
struct any;

template <
    template <typename...> class F,
    template <typename...> class C, typename E, typename... En
>
struct any <F, C <E, En...> > :
    public _if <F <E>{}, _true, any <F, C <En...> > > { };

template <template <typename...> class F, template <typename...> class C>
struct any <F, C <> > : public _false { };

where my _true/_false are equivalent to std::integral_constant <bool, true/false>, and _if <C, T, E> is equivalent to typename std::conditional <C, T, E>::type (details are irrelevant to the question, see below).

For instance, one may write

template <typename...> struct pack { };
template <typename T> using is_int = eq <int, T>;

any <is_int, pack <int, void, float, double> >();   // evaluates to true
any <is_int, pack <char, void, float, double> >();  // evaluates to false

where eq is equivalent to std::is_same.

An extension to binary predicates goes as follows:

template <template <typename...> class F, typename P, typename Q>
struct any2;

template <
    template <typename...> class F,
    template <typename...> class C, typename E, typename... En,
    template <typename...> class D, typename H, typename... Hn
>
struct any2 <F, C <E, En...>, D <H, Hn...> > :
    public _if <F <E, H>{}, _true, any2 <F, C <En...>, D <Hn...> > > { };

template <
    template <typename...> class F,
    template <typename...> class C, typename Q
>
struct any2 <F, C <>, Q> : public _false { };

where we may now write

typedef pack <int, void, float, double> A;
typedef pack <void, float, double, int> B;
typedef pack <void, float, double, double> C;

any2 <eq, A, B>();  // false
any2 <eq, A, C>();  // true

Here comes the question. Can we extend the approach to n-ary predicates, operating on n input "packs" ?

This problem is different from the previous one, in that one element of each input pack is needed at the same time for the evaluation of F <...>.

Here is a fictional attempt:

template <template <typename...> class F, typename... P>
struct any_n;

template <
    template <typename...> class F,
    template <typename...> class... C, typename... E, typename... En
>
struct any_n <F, C <E, En...>...> :
    public _if <F <E...>{}, _true, any_n <F, C <En...>...> > { };

template <
    template <typename...> class F,
    template <typename...> class C, typename... P
>
struct any_n <F, C <>, P...> : public _false { };

which of course does not compile. So, can one write things like C <E, En...>... ? What would be the types of C, E, En then?

I suspect the answer is no.

Such syntax would be extremely convenient, as e.g. in Scheme macros. I have written a C++ template implementation of this syntax in the past supporting up to two levels, using symbol dots or etc for .... But it would be entirely different to have support from the compiler (especially if you need to compile the thing on the same day).

brunocodutra · Accepted Answer · 2013-09-13T22:47:21.577

Clang 3.3 and GCC 4.8.1 both accept your definition of any_n<> without a warning, what leads me to believe it is perfectly valid, besides the fact it is logic.

WHY DOESN'T IT WORK?

In the way any_n<> is defined, it requires that all but the first element of every pack be exactly the same, for in struct any_n <F, C <E, En...>...>, En... must be repeted for every parameter pack C<> expanded.

That is, considering

template<typename...>
struct Pack;

typedef Pack<int, float, double, bool> A;
typedef Pack<void, float, double, bool> B;
typedef Pack<float, float, double, bool> C;

and

template<typename...>
struct SomeMetaFunction
{...};

The instantiation any_n<SomeMetaFunction, A, B, C> successfully binds the templates parameters of any_n<> as follows:

F => SomeMetaFunction
C => std::tuple
E... => [int, void, float]
F... => [float, double, bool]

according to its second specialization.

Attempting to instantiate any_n<SomeMetaFunction, A, B, C, D> for instance, where D is defined as

typedef std::tuple <char, int, double, bool> D;

causes an undefined any_n<> error, as expected.

HOW TO DO IT

You can achieve exactly what you want by only a minor modification to the definition of any_n<>. The idea is to use the concept of recursive lists, much like functional languages do.

First of all, you'll need a meta-function to convert pack<a, b, c, ..., z> into pack<a, pack<b, c, ... z>>.

template<typename...>
struct toRecursiveList;

//a recursive list already
template<template <typename...> class Pack, typename H, typename... T>
struct toRecursiveList<Pack<H, Pack<T...>>>
{
    using type = Pack<H, Pack<T...>>;
};

//several elements
template<template <typename...> class Pack, typename H, typename... T>
struct toRecursiveList<Pack<H, T...>>
{
    using type = Pack<H, Pack<T...>>;
};

//one element
template<template <typename...> class Pack, typename H>
struct toRecursiveList<Pack<H> >
{
    using type = Pack<H, Pack<>>;
};

//empty
template<template <typename...> class Pack>
struct toRecursiveList<Pack<>>
{
    using type = Pack<>;
};

//missing pack
template<typename H, typename... T>
struct toRecursiveList<H, T...>
{
    template<typename...>
    struct Pack;
    using type = Pack<H, Pack<T...>>;
};

The base case of any_n<> ensures the arguments get converted to a recursive list on the first step if necessary.

template <template <typename...> class F, typename... P>
struct any_n :
        public any_n<F, typename toRecursiveList<P>::type...>
{};

Now we are guaranteed every pack will have at most two elements, for, if not, the base case would have converted it to this representation. Using this fact, the main recursion becomes the following.

template <
    template <typename...> class F,
    template <typename...> class... C, typename... E, typename... En
>
struct any_n <F, C <E, En>...> : //two elements each, no need for double pack expansion on En
    public _if <F <E...>{}, _true, any_n <F, typename toRecursiveList<En>::type...>>::type { }; 
    //                                                ^ ensures a recursive list is passed onto the next recursion step

The recursion guard stays the same.

template <
    template <typename...> class F,
    template <typename...> class C, typename... P
>
struct any_n <F, C <>, P...> : public _false { };

The previous example any_n<SomeMetaFunction, A, B, C, D> now compiles just as expected.

For a live SSCCE example, please click here.

@brunocodutra Just browsing, I saw this answer and I don't recall seeing it at that time! I prefer that to using boost. My question was rather if this is supported by the language, which is clear it is not, and you have to program it yourself. — iavr, Apr 18 '14 at 10:55
@brunocodutra In the meantime, I have found another solution that does *not* have to convert to old-style recursive lists. Roughly, I define metafunctions `car`, `cdr` (head/tail equivalents in lisp) and then generalize to `cars`, `cdrs` which can do the same to multiple lists in parallel: `cars` takes as input a pack of lists (packs) and returns a pack containing the 1st element (head) of each list; similarly, `cdrs` returns a pack containing the tail of each list. This resembles boost's zip view a little. It would need some work to post it as another answer, so I just summarize it here. — iavr, Apr 18 '14 at 11:00

score 1 · Answer 2 · edited May 23 '17 at 11:50

I would use boost::mpl::zip_view to iterate through all your lists at once. In fact I think the example in the link is exactly what you need except instead of transform_view you would want find_if.

    #include <boost/mpl/zip_view.hpp>
    #include <boost/mpl/find_if.hpp>
    #include <boost/mpl/placeholders.hpp>
    #include <boost/mpl/unpack_args.hpp>
    #include <boost/mpl/vector.hpp>
    #include <boost/mpl/range_c.hpp>
    #include <boost/mpl/or.hpp>
    #include <boost/mpl/vector_c.hpp>
    #include <boost/mpl/equal_to.hpp>
    #include <boost/mpl/not_equal_to.hpp>
    #include <boost/mpl/not.hpp>
    #include <boost/mpl/and.hpp>
    #include <iostream>

    using namespace boost::mpl;
    using namespace boost::mpl::placeholders;

    template <class Predicate, class ... Sequences>
    struct any_n
    {
        typedef zip_view<vector<Sequences...> > seq;
        typedef typename not_<
            typename boost::is_same<
                typename find_if<
                    seq,
                    unpack_args<Predicate> >::type,
                typename end<seq>::type>::type>::type type;
    };

    typedef not_equal_to<boost::is_same<_1, _2>,
                         boost::is_same<_2, _3> >pred1;

    typedef or_<equal_to<_1, _2>,
                equal_to<_2, _3> > pred2;

    typedef any_n<pred1,
                  range_c<int,0,10>,
                  vector_c<unsigned, 1, 4, 2, 5>,
                  vector_c<short, 0, 0, 2, 7, 4> >::type found1;

    typedef any_n<pred2,
                  range_c<int,0,10>,
                  vector_c<unsigned, 1, 4, 2, 5>,
                  vector_c<short, 0, 0, 2, 7, 4> >::type found2;

    int main()
    {
        std::cout << std::boolalpha << found1() << ' ' << found2() << std::endl;
    }

If you're unfamiliar with boost's approach to template metaprogramming (ie, the Boost.TemplateMetaprogrammingLibrary) then this can seem somewhat overwhelming (or even very overwhelming). The only book (so far at least) that I ever willingly bought on programming was "C++ Template Metaprogramming" and I highly recommend it if you're interested in this stuff.
I found this question which points to this book among others.

Thanks. This is indeed nice, although I was rather interested in what the language supports. I have developed my own metaprogramming library in the past that really looked like language ML (and could handle this problem as well). It was impressive what you could express in one line of code, but if you got carried away, you'd wait for minutes to compile... — iavr, Sep 13 '13 at 03:07
@iavr although the language does not support *double pack expansion* directly you can surely workaround it, like I've attempted to show on my answer. Like you said, to solve this kind of metaprogramming problems, the key is to think just like you would when working with functional languages, [S]ML for instance. — brunocodutra, Sep 13 '13 at 03:35

Variadic variadic template templates, again

2 Answers2