CODEWITHSUNDEEP
c++templatesc++11c++14template-meta-programming
Mats Kindahl
Mats Kindahl

Reputation: 2075

Functional programming using parameter packs in C++

This is a simplification of a different problem I have, but it stands well on its own. The idea is to implement functional primitives similar to map and apply in Scheme.

Just to recap: in Scheme, given a function f then (apply f '(1 2 3)) is equivalent to (f 1 2 3) and (map f '(1 2 3)) is equivalent to ((f 1) (f 2) (f 3)).

Implementing apply is the easy one, and there are plenty of other questions showing how this is done:

template <class Func, class... Args, std::size_t... Ixs>
auto apply_helper(Func&& func, const tuple<Args...>& args,
                  index_sequence<Ixs...>)
    -> decltype(func(get<Ixs>(args)...))
{
  return forward<Func>(func)(get<Ixs>(forward<const tuple<Args...>&>(args))...);
}

template <class Func, class... Args,
          class Ixs = make_index_sequence<sizeof...(Args)>>
auto apply(Func&& func, const tuple<Args...>& args)
    -> decltype(apply_helper(func, args, Ixs()))
{
  return apply_helper(forward<Func>(func),
                      forward<const tuple<Args...>&>(args), Ixs());
}

void print3(int x, const char* s, float f) {
  cout << x << "," << s << "," << f << endl;
}

int main() {
  auto args = make_tuple(2, "Hello", 3.5);
  apply(print3, args);
}

Now comes implementing map, which is a little more tricky. We want something like this to work, so this is the goal (here using mapcar to avoid conflict with std::map):

template <class Type>
bool print1(Type&& obj) {
  cout << obj;
  return true;
}

int main() {
  auto args = make_tuple(2, "Hello", 3.5);
  mapcar(print1, args);
}

Other alternatives for passing the print1 function are OK as well.

So, if we hard-code the function, the following code will work fine:

template <class... Args, std::size_t... Ixs>
auto mapcar_helper(const tuple<Args...>& args,
                   index_sequence<Ixs...>)
    -> decltype(make_tuple(print1(get<Ixs>(args))...))
{
  return make_tuple(print1(get<Ixs>(forward<const tuple<Args...>&>(args)))...);
}

template <class... Args,
          class Ixs = make_index_sequence<sizeof...(Args)>>
auto mapcar(const tuple<Args...>& args)
    -> decltype(mapcar_helper(args, Ixs()))
{
  return mapcar_helper(forward<const tuple<Args...>&>(args), Ixs());
}

The question is how we can generalize this code to accept an arbitrary name as input and have it resolve the name lookup inside the template? Just adding a template parameter does not work since it cannot resolve the function overload at that point.

We would like to make the call to mapcar above equivalent to the code:

make_tuple(print1(2), print1("Hello"), print1(3.5));

Update: One of the original challenges was to make it work with a C++11 compiler, partially because I am using GCC 4.8, but also because I want to investigate how to do it. Based on the comments, below is an example of how it can be done without the help of polymorphic lambdas (which require C++ 14 compiler support).

It is not as straightforward as I would like, C++ 14 features will make it so much easier, but at least it can be supported at a minor inconvenience to the user.

template <class Func, class... Args, std::size_t... Ixs>
auto mapcar_helper(Func&& func, const tuple<Args...>& args,
                   index_sequence<Ixs...>)
    -> decltype(make_tuple(func(get<Ixs>(args))...))
{
  return make_tuple(func(get<Ixs>(args))...);
}

template <class Func, class... Args,
          class Ixs = make_index_sequence<sizeof...(Args)>>
auto mapcar(Func&& func, const tuple<Args...>& args)
   -> decltype(mapcar_helper(func, args, Ixs())
{
  return mapcar_helper(forward<Func>(func), forward<decltype(args)>(args), Ixs());
}

To be able to pass a template "function", we need wrap it in an object:

struct print1 {
  template <class Type> const Type& operator()(Type&& obj) {
    std::cout << obj << " ";
    return obj;
  }
};

This can now be passed to the function and the type lookup will be done at the point of the parameter pack expansion:

   mapcar(print1(), make_tuple(2, "Hello", 3.5));

Upvotes: 3

Views: 335

Answers (2)

Simple
Simple

Reputation: 14390

template <typename F, class... Args, std::size_t... Ixs>
auto mapcar_helper(F f, const tuple<Args...>& args,
                   index_sequence<Ixs...>)
    -> decltype(make_tuple(f(get<Ixs>(args))...))
{
  return make_tuple(f(get<Ixs>(args))...);
}

template <typename F, class... Args,
          class Ixs = make_index_sequence<sizeof...(Args)>>
auto mapcar(F f, const tuple<Args...>& args)
    -> decltype(mapcar_helper(move(f), args, Ixs()))
{
  return mapcar_helper(move(f), args, Ixs());
}

Then you do:

mapcar([](auto&& obj) { return print1(std::forward<decltype(obj)>(obj)); }, args);

Maybe I didn't understand the question. You need to wrap print1 in a lambda because it is ambiguous otherwise; which instantiation of print1 did you want to pass it?

If you don't have macrophobia, you can make this more elegant using a macro:

#define LIFT(F) ([&](auto&&... args) -> decltype(auto) { \
    return F(::std::forward<decltype(args)>(args)...);  \
})

Then you can use mapcar(LIFT(print1), args).

This is how I would write my own map function:

template<typename F, class Tuple, std::size_t... Is>
auto map(Tuple&& tuple, F f, std::index_sequence<Is...>)
{
    using std::get;
    return std::tuple<decltype(f(get<Is>(std::forward<Tuple>(tuple))))...>{
        f(get<Is>(std::forward<Tuple>(tuple)))...
    };
}

template<typename F, class Tuple>
auto map(Tuple&& tuple, F f)
{
    using tuple_type = std::remove_reference_t<Tuple>;
    std::make_index_sequence<std::tuple_size<tuple_type>::value> seq;
    return (map)(std::forward<Tuple>(tuple), std::move(f), seq);
}

Upvotes: 3

Richard Hodges
Richard Hodges

Reputation: 69892

what did I miss?

#include <iostream>
#include <string>


template<class F, class...Args>
void map(F&& f, Args&&...args)
{
    using expander = int[];
    (void) expander { 0, ((void) f(args), 0)... };
}

auto main() -> int
{
    using namespace std;

    map([](const auto& x) { cout << x << endl; }, 1, "hello"s, 4.3);

    return 0;
}

expected output:

1
hello
4.3

Note that in c++17, the map() function becomes a more pleasing:

template<class F, class...Args>
void map(F&& f, Args&&...args)
{
    (f(args), ...);
}

If your next question is "why the brackets?". The answer is because fold expressions are only evaluated in the context of an expression. f(arg1), f(arg2); is a statement.

reference: http://en.cppreference.com/w/cpp/language/fold

Upvotes: 3

Related Questions