Overloading by function type using templates

Question

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

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

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

I would like to define the fmap function, on containers and functions, to reflect this abstraction for general programming.

The container was light (I know this is not completely common)

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, a similar 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)); }; } 

Despite the fact that the template will not specialize in anything other than called things, I worry that this confuses the resolution of overloading. I would like to introduce type restrictions for template parameters in order to limit their permission to function types in order to keep the namespace clean. And I was going to ask how to do it.

This abstraction is extremely general, there are appropriate fmaps for pointers to values, which, I suspect, may also conflict.

So, I think my question is: can I have two different template implementations with the same template level signature? I am pretty sure that the answer is no, but maybe something like that can be faked. And if not, what tools are available today to distinguish between overloads? Especially for function types.

It seems to me that this is a textbook for concepts, although I'm not sure.

Edit: Boost will be acceptable to use, and SFINAE in particular. I am trying to find a solution that would be familiar to most programmers, and would be as convenient and canonical as possible. I could rename fmap for layout, but then the programmer would need to know in order to pass composition to the template function that accepts fmap. This would be unsuccessful 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 summarizes cards over containers into cards by container. Therefore, 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 output outputs are two times the outputs of the increment function. This is like doubling a sort of list. An abstraction has some nice properties, I don't just do it. In any case, renaming the fmap function for compilation does not answer the question.

Edit 3: fmap for pattern C performs 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 property of maintaining a good structure.

Functions that do this for ranges already have different names. But ranges are not the only patterns for types. Here's the 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 does not imply any range concepts at all, for example, fmap for the functions presented earlier. But it satisfies the semantic requirements for fmap .

I am trying to define fmap for different overloads in the same way, I would define a new operator * for a custom matrix type. Therefore, I happily define fmap in terms of boost::transform_iterator . Then these algorithms will work with a function common 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 prints gives

 1 4 9 16 25 36 

If there were an options vector instead, the options would be square if they contained elements.

I am trying to understand how to work with higher order functions in C ++.

Answer 1

Here's the easiest compromise I've 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)> beautify the call site, and it limits the indirect actions. I am sure this is the best thing to do if fmap restriction is required.

Edit: You can do better. The link makes it possible to limit calls that are also in lines.

A function can be written as follows:

 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 can select the desired version on 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 sure function tagging is required.

Here is a blog post that also talks about the issue and discusses other options. http://yapb-soc.blogspot.com/2012/10/fmap-in-c.html

Answer 2

You can fake it with SFINAE, but you shouldn't. This is a matter of style and idiom.

Haskell is all type classes, and the programmer expects to have to type each type with all the clubs to which it belongs. C ++, by contrast, wants to be more implicit when specifying type capabilities. You showed " vector " and "arbitrary called", but why just vector ? Why not an arbitrary type of container? And this arbitrary type of container that I just wrote has operator() , because of the reasons. So which one to choose?

On the bottom line, while you can use SFINAE tricks to solve technical ambiguities, you should not use them to remove significant ambiguities. Just use two different names.