fmap for containers in c++

Question

I implemented a simple fmap for containers. However containers don't have a unified function to add elements. So I wrote different concepts for different containers. Is there a better way to implement this?

#include <concepts>
#include <iterator>
#include <type_traits>

// for tests
#include <queue>
#include <print>
#include <vector>
#include <set>


template <class c_t>
concept pushback_c_t = requires(c_t c, typename c_t::value_type v) {
    { c.begin() } -> std::input_or_output_iterator;
    { c.end() } -> std::input_or_output_iterator;
    c.push_back(v);
};

template <class c_t>
concept insert_c_t = requires(c_t c, typename c_t::value_type v) {
    { c.begin() } -> std::input_or_output_iterator;
    { c.end() } -> std::input_or_output_iterator;
    c.insert(v);
};

template <class c_t>
concept push_c_t = requires(c_t c, typename c_t::value_type v) {
    { c.begin() } -> std::input_or_output_iterator;
    { c.end() } -> std::input_or_output_iterator;
    c.push(v);
};

template <class f_t,pushback_c_t c_t>
auto fmap(f_t f, c_t c)
{
    using value_type = std::invoke_result_t<f_t,typename c_t::value_type>;
    c_t result;
    for (auto it = c.begin(); it != c.end(); ++it)
    {
        result.push_back(f(*it));
    }
    return result;  
}

template <class f_t,insert_c_t c_t>
auto fmap(f_t f, c_t c)
{
    using value_type = std::invoke_result_t<f_t,typename c_t::value_type>;
    c_t result;
    for (auto it = c.begin(); it != c.end(); ++it)
    {
        result.insert(f(*it));
    }
    return result;  
}

template <class f_t,push_c_t c_t>
auto fmap(f_t f, c_t c)
{
    using value_type = std::invoke_result_t<f_t,typename c_t::value_type>;
    c_t result;
    for (auto it = c.begin(); it != c.end(); ++it)
    {
        result.push(f(*it));
    }
    return result;  
}


int main()
{
    std::vector<int> vec{1,2,3,4,5};
    auto f = [](int x) { return x+3; };
    auto res = fmap(f,vec);
    for(auto e:res) std::print("{} ", e);
    std::println("");
    std::set<int> st{10,12,13,14};
    auto resst = fmap(f,st);
    for(auto e:resst) std::print("{} ", e);
    std::println("");
    std::deque<int> q{101,102,103};
    auto resq = fmap(f,q);
    for(auto e:resq) std::print("{} ", e);
    std::println("");
}

Answer 1

Naming things

Your way of naming things, in particular the concepts, is a bit unfortunate. First, for compatibility reasons, I recommend that you avoid the use of the _t suffix, as C reserves any identifiers that begin with int and uint and end with _t, and POSIX reserves all identifiers ending with _t.

Consider following the naming practices of the C++ standard library: snake_case for concepts, PascalCase for template parameters.

Also avoid unnecessary abbreviations. Instead of c and v, write container and value. There is a small amount of extra typing, but it greatly improves readabilty of your code.

Finally, the name fmap comes from Haskell, but someone not used to that language will not understand what it means. It would be better to give it a name that follows the naming conventions of the C++ standard library. Something with transform in the name would be great, as part of your code is just doing a std::transform(), and there are already monadic operations in C++ like std::optional::transform().

There actually is a unified way to add elements

Indeed, different containers have different ways to push elements to them. However, there is a way to add elements to almost any container without having to create specialized functions, and that is by explicitly insert()ing at the end(). Your code can be simplified to:

template <class Function, class Container>
auto fmap(Function function, Container container)
{
    Container result;
    std::ranges::transform(container, std::inserter(result, result.end()), function);
    return result;  
}

And your example main() will still work unchanged.

Add the right constraints

You used concepts to select the right variant of fmap(), but little consideration was given to the other constraints your function actually has. For example, you didn't constrain f_t at all, but you require it to be a function that can work on a c_t::value_type. You could use std::invocable or one of its variants for this.

Furthermore, consider your constraints on c.begin() and c.end(). Checking for std::input_or_output_iterator is not good enough, because that would match pure output containers from which you cannot read. And instead of checking for the individual member functions, just use std::ranges::input_range if you can iterate over the container for reading.

Consider copying the interface of std::ranges::transform()

To make your function look and feel like other algorithms from the C++ standard library, copy as much as possible from std::ranges::transform(). In particular, look at the order of the arguments, the contraints it uses, and you could even support a projection operator. In fact, your fmap() is just a std::ranges::transform() that doesn't have an output parameter, and instead returns a new container.

Answer 2

Pass the container by reference instead:

Currently, these functions copy the container when it is passed in. You probably want to take the argument as c_t const& instead to avoid this.

Answer 3

It's unclear why the three functions define this type alias:

using value_type = std::invoke_result_t<f_t,typename c_t::value_type>;

If it's there to ensure that f_t is an invocable type, then I think that it's better to use a constraint:

template <pushback_c_t c_t, std::invocable f_t<c_t::value_type>>
auto fmap(f_t&& f, c_t&& c)

I've also used universal references there, which may help reduce copying.

BTW, those names are uninformative, hard to read and risk collision with POSIX type names.

---

Consider using C++23 if you can, or otherwise implement the functionality of std::ranges::to<>() to create a new container from a transform view:

#include <algorithm>
#include <concepts>
#include <ranges>
#include <type_traits>

template<std::ranges::input_range Range>
auto fmap(std::invocable<std::ranges::range_value_t<Range>> auto&& func, Range&& r)
{
    return r
        | std::views::transform(func)
        | std::ranges::to<std::remove_reference_t<Range>>();
}

As well as unifying the three different templates, this has the advantage that std::ranges::to<>() will call the container's reserve() it has one, eliminating unnecessary allocations.