Polymer - 6 months ago 46

C++ Question

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})`

`double_everything([](int x){ return x + 1; })`

`fmap`

Edit 3:

`fmap`

`C`

`A`

`B`

`C<A>`

`C<B>`

`fmap( compose(f, g) , c ) = fmap( f, fmap( g, c ))`

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

`fmap`

`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`

`fmap`

I'm trying to define

`fmap`

`operator *`

`fmap`

`boost::transform_iterator`

`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`

`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.