2

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));
Mats Kindahl
  • 1,863
  • 14
  • 25

2 Answers2

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);
}
ildjarn
  • 62,044
  • 9
  • 127
  • 211
Simple
  • 13,992
  • 2
  • 47
  • 47
  • 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? – Mats Kindahl Dec 10 '15 at 17:04
  • 1
    @MatsKindahl: You can write your functor the old way: `struct printer { template void operator()(T&& obj) const {/*..*/} };` – Jarod42 Dec 10 '15 at 17:07
  • you could also just pass print1 instead of a lambda, i do that all the time. wouldn't that work here? – johnbakers Dec 10 '15 at 17:40
  • 1
    @johnbakers in general you shouldn't pass explicit template arguments that are meant to be deduced. You should let the compiler do the work. – Simple Dec 10 '15 at 18:00
  • except when the compiler can't do the work, for the reason you described, in which case, passing a template parameter seems a lot more elegant than wrapping it in a lambda – johnbakers Dec 10 '15 at 18:01
  • 1
    @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. – Mats Kindahl Dec 10 '15 at 20:28
  • @Simple You have great examples above, so I ticked this one. I would like to avoid using macros, but right now it seems the best approach is C++ 14 and polymorphic lambdas. – Mats Kindahl Dec 10 '15 at 20:35
  • @johnbakers More than not knowing the type, if you have a tuple that you want to map whose types are not the same, there is no template parameter you could specify to make it work. – SirGuy Dec 12 '15 at 00:29
  • @MatsKindahl this exercise feels a bit like trying to get the benefits of a dynamically typed language in a language that is very much strictly statically typed. Not sure the idiom is the best approach, personally. – johnbakers Dec 12 '15 at 18:35
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

Richard Hodges
  • 68,278
  • 7
  • 90
  • 142
  • those two `expander` lines are interesting; i can't quite tell what they are doing – johnbakers Dec 10 '15 at 17:36
  • 1
    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 Dec 10 '15 at 17:50
  • 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) – Richard Hodges Dec 10 '15 at 17:52
  • as for why the comma operator throws away the result and returns zero, related question: http://stackoverflow.com/questions/54142/how-does-the-comma-operator-work – johnbakers Dec 10 '15 at 17:57
  • It's a neat way to solve it if the function return void, but what if there are several overloads of the function all returning different types? That is why I wanted to make it into a tuple instead of an array. – Mats Kindahl Dec 10 '15 at 20:24
  • that'll work with a minor mod. but what should `map` return? another tuple? – Richard Hodges Dec 10 '15 at 20:27
  • @Richard Yes, another tuple. – Mats Kindahl Dec 11 '15 at 09:59
  • @RichardHodges Also. I don't think you missed anything. I am trying to do it without polymorphic lambdas since I am using GCC 4.8. – Mats Kindahl Dec 11 '15 at 10:39
  • 1
    @MatsKindahl in that case substitute the lambda with a function object with a templatised operator()(T&) – Richard Hodges Dec 11 '15 at 10:41