Higher-order functions with templates?

Question

I've been programming in Clojure (a functional language) for a while now, and I have to use C++ for a class. I've been trying to use some of the functionality I've enjoyed in Clojure (e.g., higher-order functions, lambdas, argument threading, dynamic typing, etc.) but I've been running into some brick walls.

Firstly, I've implemented a function get which takes two arguments:

a collection (vector, list, hash map, etc.), and
an index

and returns the element at that index.

I've also implemented a function conj which takes two arguments:

a collection (vector, list, queue, etc.), and
an element/object (of whatever type the collection is)

and returns the collection with the element added. In the case of vectors, this is largely the same as push_back.

Now, I want to be able to "forward" or "thread" the arguments using higher-order functions like so:

using std::vector;
vector<double> my_vec;

forward(my_vec,    // take "my_vec"
        conj(0.1), // "push" the value of 0.1 to the back of "my_vec"
        get(0),    // retrieve the first value
        inc);      // increment that value

It's the same as inc(get(conj(my_vec, 0.1), 0);, but a lot (!) more readable.

The return value of forward in this case should be 1.1.

In order to get the forward function to work, the arguments after the initial argument need to all be higher-order functions. That is, they need to work analogous to the following:

template<typename Func>
Func get(int i){
  return [i](vector<boost::any> coll)
           -> boost::optional<boost::any> {
             return get(coll, i);
           };
}

However, the compiler can't deduce the type of the lambda function to be returned. Also, my guess, based on my extremely limited experience with boost::any, is that it won't be able to convert a vector<double> to vector<boost::any>, despite the apparent claims of boost::any that it can act as a substitute for virtually any type.

I want the get function to be general, so I don't want to use boost::function<double (vector <double>, int)>, or any similarly specific typing.

Also, I'm using boost::optional instead of vector to return null_ptr if the index requested from get is out of bounds.

As it stands, here's how my forward function looks:

template <typename T1>
optional<T1> forward (T1 expr1){
  return expr1;
}
template <typename T1, typename T2>
optional<T1> forward (T1 expr1, T2 expr2){
  return forward(expr2(expr1));
}
template <typename T1, typename T2, typename T3>
optional<T1> forward (T1 expr1, T2 expr2, T3 expr3){
  return forward(expr2(expr1), expr3);
}

etc. ...

Any ideas on how to get this forward function to work?

I'm also pretty sure there's a more efficient way to implement it than doing the arity-overloading as I have.

Lookup monadic functions and continuators, a functional programming concept. [See how it is implemented in C++11.](http://stackoverflow.com/a/25342660/701092) — David G, Aug 29 '14 at 15:33

score 2 · Answer 1 · edited May 23 '17 at 11:49

That's what I can come up with:

http://coliru.stacked-crooked.com/a/039905c5deff8dcf

Instead of lambdas I used fully fledged functors in three different variants. It supports your example and does not require type erase or such (e.g. boost::any or std::function).

boost::optional<double> result = forward(my_vec, conj(0.1), get(0), inc);

Also, the forward function is implemented as variadic template, allowing any number of functions.

The code is unpolished, but maybe it can give some inspiration.

EDIT: Anton is absolutely right, my implementation of forward was unnecessarily complicated. The link above now points to his revised version of the code.

score 2 · Accepted Answer · answered Aug 29 '14 at 18:09

Just an addition to Horstling's answer, actually forward can be implemented much easier:

template <typename Value>
Value forward(Value v) {
    return v;
}

template <typename Value, typename Func, typename... Funcs>
auto forward(Value v, Func f, Funcs... fs) -> decltype(forward(f(v), fs...)) {
    return forward(f(v), fs...);
}

And C++14 sweetens things even a little bit more:

template <typename Value>
Value forward(Value v) {
    return v;
}

template <typename Value, typename Func, typename... Funcs>
decltype(auto) forward(Value v, Func f, Funcs... fs) {
    return forward(f(v), fs...);
}

Take a look at the full code here (Coliru appears to support boost)

Higher-order functions with templates?

2 Answers2