Iteratively filtering arguments matching a predicate at compile-time

Question

Context

Firstly, some context: I'm using an empty struct called nothing to emulate something similar to "regular void" in order to prettify some interfaces that rely on chaining multiple function objects together.

struct nothing { };

Example usage:

when_all([]{ return 0; }, []{ }, []{ return 'a'; })
    .then([](int, char){ }); // result of lambda in the middle ignored

In the above example, what's actually happening is that I'm packaging all the results of the function objects passed to when_all in an std::tuple, converting void to nothing (in this example: std::tuple<int, nothing, char>), then I'm using a helper function called apply_ignoring_nothing that invokes a function object by unpacking an std::tuple, ignoring the elements that are nothing.

auto f_then = [](int, char){ };
auto args = std::tuple{0, nothing{}, 'a'};
apply_ignoring_nothing(f_then, args); // compiles

apply_ignoring_nothing is implemented in terms of call_ignoring_nothing.

---

Question

I have a function call_ignoring_nothing with the following signature:

template <typename F, typename... Ts>
constexpr decltype(auto) call_ignoring_nothing(F&& f, Ts&&... xs);

This function will invoke f by perfectly-forwarding all xs... for which the compile-time is_nothing_v<T> returns false.

is_nothing_v is defined as follows:

template <typename T>
inline constexpr bool is_nothing_v = std::is_same_v<std::decay_t<T>, nothing>;

The way I implemented call_ignoring_nothing is recursively. The base case only takes f and simply invokes it:

#define FWD(x) ::std::forward<decltype(x)>(x)

template <typename F>
constexpr decltype(auto) call_ignoring_nothing(F&& f)
{
    return returning_nothing_instead_of_void(FWD(f));
}

The recursive case takes f, x, and xs..., and conditionally binds x as one of f's arguments if !is_nothing_v<decltype(f)> through a lambda. It then recurses over call_ignoring_nothing passing the newly-created lambda as f:

template <typename F, typename T, typename... Ts>
constexpr decltype(auto) call_ignoring_nothing(F&& f, T&& x, Ts&&... xs)
{
    return call_ignoring_nothing(
        [&](auto&&... ys) -> decltype(auto) {
            if constexpr(is_nothing_v<T>)
            {
                return FWD(f)(FWD(ys)...);
            }
            else
            {
                return FWD(f)(FWD(x), FWD(ys)...);
            }
        },
        FWD(xs)...);
}

I would like to implement call_ignoring_nothing in an iterative manner, possibly making use of pack expansion to filter out the arguments without recursion.

Is it possible to implement call_ignoring_nothing without recursion? I couldn't think of any technique that allows arguments to be filtered out during pack expansion.

Carnet

To reiterate what I proposed on Slack: turn the pack into a tuple. Generate an index sequence for the tuple. Filter the index sequence (possibly even with a type-level filter, by turning the sequence into integral_constant<std::size_t, Is>...). Pattern match on that. Expand get<FilteredIs>(tuple).... – Ragan

Also porting a comment of mine from Slack, as an answer to "isn't this shifting the problem to the concat level inside filter" - you can optimize join to avoid being always recursive; an example of that can be found in metal. – Ragan

As Desproges said: "To my own opinion, opinion I oftenly refers to..." I think that the answer could be posted here, by anybody. – Alliterate

Answer 1

Not so different from the Griwes suggestion but... I suppose you can use std::apply(), std::tuple_cat(), std::get() and tuples that are empty or with value according the value of is_nothing_v.

I mean... something like [edit: improved with a suggestion from T.C. and an example from the OP itself (Vittorio Romeo)]

template <bool B, typename ... Ts>
constexpr auto pick_if (Ts && ... xs)
 {
   if constexpr ( B ) 
      return std::forward_as_tuple(std::forward<Ts>(xs)...);
   else
      return std::tuple{};
 }

template <typename F, typename ... Ts>
constexpr decltype(auto) call_ignoring_nothing (F && f, Ts && ... xs)
 {
   return std::apply(f,
      std::tuple_cat(pick_if<!is_nothing_v<Ts>>(std::forward<Ts>(xs))...)
   );
 }

The following is a working example

#include <tuple>
#include <iostream>
#include <type_traits>

struct nothing { };

template <typename T>
constexpr bool is_nothing_v = std::is_same<std::decay_t<T>, nothing>::value;

template <bool B, typename ... Ts>
constexpr auto pick_if (Ts && ... xs)
 {
   if constexpr ( B )
      return std::forward_as_tuple(std::forward<Ts>(xs)...);
   else
      return std::tuple{};
 }

template <typename F, typename ... Ts>
constexpr decltype(auto) call_ignoring_nothing (F && f, Ts && ... xs)
 {
   return std::apply(f,
      std::tuple_cat(pick_if<!is_nothing_v<Ts>>(std::forward<Ts>(xs))...)
   );
 }

float foo (int a, float b) { return a + b; }

int main ()
 {
   std::cout << call_ignoring_nothing(foo, nothing{}, 12, nothing{},
      2.3f, nothing{}); // print 14.3    
 }

live example on wandbox

Cymene

Ooooh, this is neat. The one problem I have with this is that it depends on tuple_cat not having a QoI bugs in your implementation (i.e. mileage may vary across stdlib implementations). – Ragan

@Ragan - ehmmm... sorry but I don't know what "Qol bugs" are; can you suggest me a reference? – Cymene

"QoI" is "Quality of Implementation". Presumably a "QoI bug" is a suboptimal implementation strategy. (E.g. if the library's tuple_cat is implemented as plain old recursion, then you haven't bought anything perf-wise; you've just shoved your perf bottleneck down into the library code.) – Extraneous

@Extraneous - I see... interesting and... yes: maybe I've only moved the problem; not solved it; thanks. A doubt: working with variadic templates, doesn't imply (down in compiler implementation) the same recursion problem? – Cymene

s/make_tuple/forward_as_tuple/ – Wrongly

@Wrongly - advantages? avoid unnecessary copies? – Cymene

This is really cool. Here's a slightly more abstracted version: wandbox.org/permlink/T4L36cT6sqMKI1Nf – Carnet

@VittorioRomeo - Thanks. En passant, seeing your version, I feel the need of a constexpr ternary operator. Anyway, I like your version; do you permit me to integrate it in my answer? – Cymene

@max66: sure thing. – Carnet

Answer 2

Here's another take that doesn't depend on tuple_cat. First calculate the positions at which a pack of bools is true via a "normal" constexpr function template:

template<class... Bools>
constexpr int count(Bools... bs) 
{
    return (bool(bs) + ...);
}

template<bool... bs>
constexpr std::array<std::size_t, count(bs...)> indices() 
{
    std::array<std::size_t, count(bs...)> ret = {};
    std::size_t i = 0, j = 0;
    for(bool b : {bs...}) {
        if(b) {
            ret[j] = i;
            ++j;
        }
        ++i;
    }
    return ret;
}

Then convert the result to a index_sequence:

template<bool...bs, std::size_t...Is>
constexpr auto indices_as_sequence_helper(std::index_sequence<Is...>) 
{ 
    return std::index_sequence<indices<bs...>()[Is]...>{}; 
}

template<bool...bs>
constexpr auto indices_as_sequence() 
{ 
    return indices_as_sequence_helper<bs...>(std::make_index_sequence<count(bs...)>()); 
}

Then it's a simple matter of forward_as_tuple + get with the index_sequence:

template <typename F, typename... Ts, std::size_t... Is>
constexpr decltype(auto) call_some(std::index_sequence<Is...>, F&& f, Ts&&... xs)
{
    return std::forward<F>(f)(
               std::get<Is>(std::forward_as_tuple(std::forward<Ts>(xs)...))...);
}

template <typename F, typename... Ts>
constexpr decltype(auto) call_ignoring_nothing(F&& f, Ts&&... xs)
{
    return call_some(indices_as_sequence<!is_nothing_v<Ts>...>(), 
                     std::forward<F>(f), std::forward<Ts>(xs)...);
}

Wrongly

Neat! I am just realizing that if constexpr I normally use within constexpr functions or constexpr function-templates is superfluous... Even the other answer falls victim of this :-). – Untinged