Polymorphic (Generic) Functions as Arguments in C++

Question

I am developing a relatively simple program (a calculator actually). However, I have decided to make all components of my program as generic as possible because:

It's good practice.
It keeps things interesting.

As part of this program I am using a Tuple class that I am writing. I know that a class already exists, but I like having complete control over my code and this is only an exercise.

One thing I need to do is transform a tuple of expressions (where expressions themselves are generic) into a tuple containing the result of the expressions' evaluations. In short, I have (with trivial parts left out):

template <class T>
class Expression {

    public:
        virtual T Eval() = 0;

    // ...
};

template <class First, class ... Rest>
class Tuple {

    // ...

    private:
        First first;
        Tuple<Rest ...> rest;
};

And I would like to specialize over a tuple of a generic type like this:

template <template <class> class R, class First, class ... Rest>
class Tuple<R<First>, R<Rest> ...> {

    // and here is the problem:
    Tuple<First, Rest ...> Transform(function<template<class T> T(R<T>)>);
};

After which I could do this:

template <class T> // There has to be a better way to do this
T Eval(Expression<T>& expr){
    return expr.Eval();
}

// ...
Tuple<First, Rest ...> tuple = exprs.Transform(Eval);

There are a few places here where I am not sure how to go about things and a real expert who could help me out here would be appreciated. I expect this code will not compile because of minor flaws but that isn't the point - My primary worry is the line I marked. If I recall correctly from the brief period I learned Haskell this function should be of Rank-2 (If not please comment and I will remove the tag). It just doesn't look right. Is there any way to do this?

Update:

I was advised to try pass a functor with a generic operator () as a template argument but that didn't work either.

@n.m. - That doesn't provide the functionality I am looking for. — user2008934, Nov 26 '14 at 13:37
@dyp - Yes, I do, That's a pure virtual function. But that's not the point. The point is - How do I pass a generic function as an argument? — user2008934, Dec 08 '14 at 18:26

score 3 · Answer 1 · edited May 23 '17 at 10:24

3

The usual trick in C++14 is to use some index_sequence (see here) and then something like:

template<typename ... Args, size_t ... I>
auto evaluate(Tuple<Args ...> const& t, index_sequence<I...>)
{
    return make_tuple(evaluate(get<I>(t))...);
}

See, e.g., this answer for an example of this approach (the only difference is that here additionally a function call is invoked).

Thus, what you need here in your Tuple class for this is:

An implementation of a custom get function which behaves similarly to std::get, i.e. accepts variadic index arguments.
An implementation of a custom make_tuple function which behaves similarly to std::make_tuple and constructs a tuple from a comma-separated list.

Further, you require a function template evaluate which is able to evaluate a single expression, but I guess you have this already.

EDIT: I just realized that the above might not be very helpful for you. Rather it should be noted that you can do that also recursively:

template<typename ... Args>
auto evaluate(Tuple<Args ...> const& t)
{
    return tuple_cat(make_tuple(evaluate(t.first)), evaluate(t.rest));
}

template<typename T> auto evaluate(Tuple<T> const& t) { return evaluate(t.first); }

Again, you require a make_tuple function, a tuple concatenator tuple_cat and a single-expression evaluator evaluate.

edited May 23 '17 at 10:24

Community

1
1

answered Nov 24 '14 at 16:40

davidhigh

14,652
2
44
75

An equivalent for std::get and std::make_tuple are easy and I have already implemented them in a somewhat different scenario elseware. I still don't see how to write the Transform function, which is the important part. – user2008934 Nov 24 '14 at 17:08
@user2008934: [Here](http://coliru.stacked-crooked.com/a/1383d7fbf9846ccb) is a basic implementation which should get you close to what you want to do (for an exact match you'd need `tuple_cat`, which I was too lazy to implement). Hope it helps. – davidhigh Nov 24 '14 at 17:44
How is this generic? I'm not seeing how to extend this in a similar case (say a tuple of lists of different types -> a tuple of the sum of each list) - It would seem you have to repeat this code for every such case. – user2008934 Nov 24 '14 at 18:16
@user2008934: you give a tuple to the evaluate function and get returned a tuple which contains the transformed types. In the example, I've passed a `Tuple`, applied a function `double evaluate(int)`, and would have got back a `Tuple` (if a `tuple_cat` were available -- actually it is a `Tuple >`). The generic thing here is: *that code works like this for any type and any evaluation function*. – davidhigh Nov 24 '14 at 18:22
But you have to write a new evaluate function every time. What if I wanted to turn a tuple of lists of different types and transform it into a tuple of their sums? You would have to write everything again but replace evaluate with sum! I want to be able to pass sum as an argument and be done with it. – user2008934 Nov 24 '14 at 18:36
@user2008934: No, just use a function template `template auto evaluate(ExpressionType)` which evaluates arbitrary expressions. You called this `Eval(Expression)` in your OP. – davidhigh Nov 24 '14 at 18:42
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/65541/discussion-between-user2008934-and-davidhigh). – user2008934 Nov 24 '14 at 18:44
I actually curry out the function and then partially apply it recursively. – user2008934 Dec 08 '14 at 18:36

Barry · Accepted Answer · 2014-12-14T00:18:44.383

I think you can do this pretty simply without C++14 at all. I'm going to assume a few things about how your Tuple is constructed, namely that these two ctors exist:

Tuple(First, Rest... );                // (1)
Tuple(First, const Tuple<Rest...>& );  // (2)

We need one type trait: given a function that we're transforming with, we need to know what types it produces:

template <typename T, typename F>
using apply_t = decltype(std::declval<F>()(std::declval<T>()));

(God I love C++11)

With that, we can determine the return type easily, and it's just a matter of calling the function recursively:

template <typename First, typename... Rest>
struct Tuple
{
    template <typename F>
    Tuple<apply_t<First, F>, apply_t<Rest, F>...>
    Transform(F func)
    {
        return {func(first), rest.Transform(func)}; // hence the need
                                                    // for ctor (2)
    };
};

(Depending on how you wrote your Tuple you may or may not need a base case for a trivial transform that just returns a Tuple<>, or a base case that just returns a Tuple<apply_t<First, F>>. Either way, not a big deal).

And you don't even need to specialize Tuple at all. You just need to pass in the right functors. For instance:

struct Zero
{
    template <typename T>
    int operator()(T ) { return 0; }
};

struct Incr
{
    template <typename T>
    T operator()(T x) { return x + 1; }
};

Tuple<int, double, char> tup(1, 2.0, 'c');
auto z = tup.Transform(Zero{}); // z is Tuple<int, int, int>{0, 0, 0}
auto i = tup.Transform(Incr{}); // i is Tuple<int, double, char>{2, 3.0, 'd'}

Here's a full code example, logging all the types too. Of course, with C++14, we can do those inline:

auto i2 = tup.Transfom([](auto x) -> decltype(x) {return x+1; });
// i2 is a Tuple<int, double, char>{2, 3.0, 'd'};
// without the trailing decltype, it gets deduced as Tuple<int, double, int>.

Polymorphic (Generic) Functions as Arguments in C++

2 Answers2