Functional programming using parameter packs in C++

Question

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

In C++14 you don't need to specify the return type of your functions anymore. You can simply specify auto as the return type, no -> decltype(...) needed anymore. — SirGuy
– SirGuy, Commented Dec 10, 2015 at 16:52
You have to pass Functor, you cannot pass generic function. — Jarod42
– Jarod42, Commented Dec 10, 2015 at 17:05
stackoverflow.com/users/2684539/jarod42 Yes, that is true. Investigating both what C++ 11 and C++ 14 can deal with here. — Mats Kindahl
– Mats Kindahl, Commented Dec 10, 2015 at 20:25

ildjarn · Accepted Answer · 2015-12-12 00:15:39Z

3

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);
}

edited Dec 12, 2015 at 0:15

ildjarn

63.2k9 gold badges135 silver badges219 bronze badges

answered Dec 10, 2015 at 16:44

Simple

14.5k2 gold badges51 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Mats Kindahl Over a year ago

Well... the question is essentially if it is possible to move the name resolution to inside the template function, at the point of the pack expansion, rather than before the call. The compile error you get if you try to pass the print1 directly above is that it cannot resolve the instantiation, but putting the name there directly works, so it is sort of a short-coming of the language that I wonder if it is possible to work around. The code above is for C++ 14 since it requires polymorphic lambdas. Is there a way to do it in C++ 11?

Jarod42 Over a year ago

@MatsKindahl: You can write your functor the old way: struct printer { template <typename T> void operator()(T&& obj) const {/*..*/} };

johnbakers Over a year ago

you could also just pass print1<sometype> instead of a lambda, i do that all the time. wouldn't that work here?

Simple Over a year ago

@johnbakers in general you shouldn't pass explicit template arguments that are meant to be deduced. You should let the compiler do the work.

Mats Kindahl Over a year ago

@johnbakers Well, you might not know the type, so it won't help you. The idea is to investigate how to get the compiler to actually do the deduction at the point of the pack expansion.

|

Richard Hodges · Accepted Answer · 2015-12-10 18:14:52Z

3

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

edited Dec 10, 2015 at 18:14

answered Dec 10, 2015 at 17:28

Richard Hodges

70.3k8 gold badges103 silver badges157 bronze badges

9 Comments

johnbakers Over a year ago

those two expander lines are interesting; i can't quite tell what they are doing

Richard Hodges Over a year ago

it's just creating an array of ints. each element is initialised to the result of the expression (f(args),0) which executed f(args), throws away the result and then returns 0 (this is just the comma operator at work). Then, having evaluated all the function calls in order, the temporary array is thrown away by the optimiser since none of the values are used.

Richard Hodges Over a year ago

the reason for the first 0 is in case Args... is empty. You're not allowed to have a 0-length array in c++ (you are in C)

johnbakers Over a year ago

as for why the comma operator throws away the result and returns zero, related question: stackoverflow.com/questions/54142/…

Richard Hodges Over a year ago

@MatsKindahl in that case substitute the lambda with a function object with a templatised operator()(T&)

|

Collectives™ on Stack Overflow

Functional programming using parameter packs in C++

2 Answers 2

9 Comments

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related