Polymer Polymer - 1 month ago 17
C++ Question

overloading over function types with templates

There is a common abstraction for both containers and functions. I learned it in Haskell, and I'm trying to implement it in C++.

Most C++ programmers are familiar with std::transform, roughly speaking given a function from type A to B, you can convert a container of type A to a container of type B.

You can transform functions in a similar way, given a function foo from A to B, you can convert a function bar taking Z to A to a function foo . bar taking Z to B. The implementation is simple, it's just composition.

I wanted to define a function fmap, on containers and functions, to reflect this abstraction for generic programming.

The container was easy (I know this isn't fully general)

template <typename A, typename Func>
auto fmap(Func f, vector<A> in) {
vector<decltype(f(in[0]))> out_terms{};
for(auto vec : in)
out_terms.push_back(f(vec));
return out_terms;
}


However, the analogous function for functions makes me much more nervous.

template <typename FuncT, typename Func>
auto fmap(FuncT f, Func in) {
return [f, in](auto x){
return f(in(x));
};
}


Although the template won't specialize for anything except callable things, I'm worried this will confuse overload resolution. I would like to introduce type constraints on the template parameters to restrict their resolution to function types to keep the name space clean. And I was going to ask how to do that.

This abstraction is extremely general, there are corresponding fmaps for pointers to values, which I suspect might conflict as well.

So I think my question is, can I have two different template implementations with the same template level signature? I'm almost certain the answer is no but maybe something similar can be faked. And if not, what tools are available today to distinguish between the overloads? Especially for function types.

This seems, to me, to be a textbook case for concepts, though I'm not sure.

Edit: Boost would be acceptable to use, and SFINAE in particular. I'm trying to find a solution that would be familiar to most programmers, and as convenient, and canonical as possible. I could rename fmap to compose, but then the programmer would have to know to pass compose to a template function accepting fmap. That would be unfortunate, because fmap is semantically unique.

Edit 2: A trivial example of how this is used.

template <typename T>
auto double_everything(T in){
auto doublef = [](auto x){return 2*x;};
return fmap(doublef, in);
}


It generalizes maps over containers to maps over "container like" things. So
double_everything(vector<int> {1, 2, 3})
returns a vector with its elements doubled. But
double_everything([](int x){ return x + 1; })
returns a function whose outputs are twice the outputs of the increment function. Which is like doubling a kind of list. The abstraction has some nice properties, I'm not just making it up. At any rate, renaming the function
fmap
to compose doesn't answer the question.

Edit 3:
fmap
for a template
C
takes functions from
A
to
B
to functions from
C<A>
to
C<B>
and satisfies
fmap( compose(f, g) , c ) = fmap( f, fmap( g, c ))
. This is a nice structure preserving property.

Functions which do this for ranges already exist by different names. But ranges aren't the only templates on types. Here is
fmap
for
std::optional
:

template<typename T, typename Func>
auto fmap(Func f, optional<T> o) -> optional<f(*o)>{
if(o)
return f(*o);
else
{};
}


This implementation doesn't involve any range concepts at all, like the
fmap
for functions presented earlier. But it satisfies the semantic requirements for
fmap
.

I'm trying to define
fmap
for different overloads in the same way I would define a new
operator *
for a custom matrix type. So I would happily define
fmap
in terms of
boost::transform_iterator
. Then these algorithms would work with a function generic in terms of
fmap
.

Here is an example of such a function:

template <
template<typename, typename> class Cont,
typename Fmappable,
typename Alloc,
typename Func>
auto map_one_deep(Func f, Cont<Fmappable, Alloc> c){
auto g = [f](Fmappable x){ return fmap(f, x); };
return fmap(g, c);
}


now if we write

auto lists = vector<vector<int> > { {1, 2, 3}, {4, 5, 6} };
auto lists_squared = map_one_deep( [](int x){return x*x;} , lists);


lists_squared
printed gives

1 4 9
16 25 36


If we instead had a vector of optionals, the optionals would be squared provided they contained elements.

I'm trying to understand how one should work with higher order functions in c++.

Answer

Here's the simplest compromise I found

template <typename FuncT, typename O, typename T>
auto fmap(FuncT f, function<O(T)> in){
  return [f, in](T x){
    return f(in(x));
  };
}

Unfortunately this requires that function<Output(Input)> decorate the call site, and it litters indirections. I'm pretty sure this is the best one can do if constraining fmap is required.

Edit: You can do better. The link gives a way to restrict to callables, that also in-lines.

The function could be written like this:

template <typename FuncT, typename T>
auto fmap(FuncT f, tagged_lambda<T> in){
  return tag_lambda([f, in](T x){
    return f(in(x));
  });
}

You could choose the version you want at the call site, by calling

fmap(g, tag_lambda({}(int x){return x + 1;}) );

or

fmap(g, function<int(int)>({}(int x){return x + 1;}) );

Given how templates work, I'm pretty sure tagging the function is required.