Selecting function overload based on a type match with return value of passed callable

Question

On an std::list<A> or std::vector<A> or other collection container, the functor map (fmap) operation takes a function/callable of type B(A) and applies it elementwise to a list of As to get a list of Bs:

// Pseudo-code
container<B> fmap( B(A) f, container<A> xs)
{
  // Apply f elementwise to xs, and collect the results and...
  return result;
}

If A and B are the same, then fmap can take the list by copy, and mutate its copy and return it. Otherwise, I want to take the input container by const reference, and create a new container for the results. The following code works (using clang++4.0 -std=c++1z) but it's just so unspeakably ugly for such a simple thing.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <type_traits>
#include <vector>

// clang-format off
template <template <typename, typename> class Container, typename A, typename F,
  // Enables this overload if the container's element type matches the output
  //   type of the callable:
  typename = std::enable_if_t<std::is_same< A,
    decltype(std::invoke(std::declval<F>(), std::declval<A>()))>::value>>
auto fmap(F f, Container<A, std::allocator<A>> xs) {
  std::cout << "I/O type SYMMETRY DETECTED!!\n";
  std::transform(std::begin(xs), std::end(xs), std::begin(xs), f);
  return xs;
}
// clang-format on

// clang-format off
template <template <typename, typename> class Container, typename A, typename F,
typename = std::enable_if_t< ! std::is_same< A,
  decltype(std::invoke(std::declval<F>(), std::declval<A>()))>::value>>
auto fmap(F f, const Container<A, std::allocator<A>>& xs) {
  std::cout << "I/O type MISMATCH DETECTED!!\n";
  using B = decltype(f(std::declval<A>()));
  using ContainerOfB = Container<B, std::allocator<B>>;

  ContainerOfB result;

  if constexpr(std::is_same<ContainerOfB, std::vector<B>>::value) {
    result.reserve(xs.size());
  }
  std::transform(std::begin(xs), std::end(xs), std::back_inserter(result), f);

  return result;
}

template <typename T>
void printrange(const T r) {
  std::copy(std::cbegin(r), std::cend(r),
            std::ostream_iterator<decltype(*std::begin(r))>(std::cout, ", "));
}

int main() {
  std::vector<int> v(20);
  std::iota(v.begin(), v.end(), 0);

  // clang-format off
  printrange(
      fmap([](int i) { return '\'' + std::to_string(i) + '\''; },
      fmap([](int x) { return x * x; },
      fmap([](int x) { return x + 1; }, v) ))
  );
  // clang-format on

  return 0;
}

Forgive me, I'm new to to template metaprogramming, and I'm aware that I'm not doing anything difficult. In fact, everything I'm using is in <type_traits>, so I'm not really doing any metafunction programming, I'm just using metafunctions! But the code I just wrote is so heinously ugly that I'm sure it can be polished and prettied. I seek the greater wisdom of the community to help me clean up this mess.

Answer 1

Higher level overview:

Personally I think the architecture has limited use cases. It was quite hard to implement, and even then doesn't match the specification.

From what I understood, this is the problem definition:

Given a container with element type T, and a callable which has return type U, create a new container with element type U and populate it by calling callable on each element of the first container. If T and U are the same, take the container by copy and transform it, otherwise use back inserter to populate it.

Although it is already good, in realm of template metaprogramming this is insufficient.

Implementation overview:

The solution places superficial limits (as per the problem definition). There are two problems in C++ template metaprogramming: assuming too much and assuming too little. Both of those happened in this case. Most of the time it is hard to tell if too little is assumed or too much, so they are mostly interchangeable.

The most obvious superficial assumptions are made here:

Container<A, std::allocator<A>>

Very few hand-rolled containers will have allocator type, or even any types at all. Remapping from one type to another is quite hard, and is the most significant problem in this case.

Somewhere the other stuff except the element type is left out:

if constexpr(std::is_same<ContainerOfB, std::vector<B>>::value) {
   result.reserve(xs.size());
}

A vector which has non-standard allocator will probably benefit from reserving too.

I don't think the code itself is unreadable. After some time on codereview and around a year of template metaprogramming this code is still readable. Although I would note that the comments in the center of the template parameter declaration got me really confused. I would put that above or below parameter declaration part.

Another solution:

I gave it a shot. I believe I covered more cases, at the expense of code size, although I think readability increased a bit:

namespace detail
{
    template <typename Container>
    using value_type = typename Container::value_type;

    template <typename Callable, typename Container>
    using invoke_result = std::result_of_t<Callable(value_type<Container>)>;
}

template <typename Container, typename Callable>
struct mutable_in_place :
        public std::bool_constant<std::is_same_v<detail::value_type<Container>,
                                  detail::invoke_result<Callable, Container>>>
{};

namespace detail
{
    template <template <typename ...> typename Container, typename T, typename ... TArgs, typename Callable>
    auto realfmap(Container<T, TArgs...> container, Callable&& callable, std::true_type)
    {
        std::transform(container.begin(), container.end(),
                       container.begin(), std::forward<Callable>(callable));
        return container;
    }

    template <template <typename ...> typename Container, typename T, typename ... TArgs, typename Callable>
    auto realfmap(Container<T, TArgs...>&& container, Callable&& callable, std::false_type)
    {
        using parameter_type = decltype(*container.begin());
        using invoke_result = std::result_of_t<Callable(parameter_type)>;
        Container<invoke_result> mapped_container;

        if constexpr(std::is_same_v<decltype(mapped_container), std::vector<invoke_result>>)
        {
            mapped_container.reserve(container.size());
        }

        std::transform(container.begin(), container.end(), std::back_inserter(mapped_container),
                       std::forward<Callable>(callable));
        return mapped_container;
    }
}

template <typename Container, typename Callable>
auto realfmap(Callable&& callable, Container&& container)
{
    return detail::realfmap(std::forward<Container>(container),
                            std::forward<Callable>(callable),
                            mutable_in_place<std::decay_t<Container>, Callable>{});
}

Although it grabs the other template arguments, it cannot use them. For example, consider the case when container=std::vector<int> and callable=std::string(int). The allocator which should get instantiated for the returning vector is std::allocator<std::string>, but the grabbed one is std::allocator<int>, so static assert will fire or some other library error notification facility, since std::vector<T>::value_type and std::vector<T>::allocator::value_type must match.

The reasoning behind not putting mutable_in_place is to expose this to the user. Some people could do template metaprogramming on top of this, and sometimes people might run into template bugs, and exposing the variable template should aid them.

About using std::result_of_t<>, the reason is that it is much easier to convert the type trait compared to hand rolled version with decltype() and stuff. It might even be possible to write a python script or something similar to convert throughout the code base, since the syntax is trivial.

Don't get me wrong, but plain transform has clear advantage here, both semantics and implementation wise.

Change the problem:

It seems like solving the current problem will have a very big engineering cost, thus I propose the following problem definition:

An StdContainer: type which exactly matches declaration template <typename ElemType, typename Allocator = std::allocator<ElemType>> class container except identifier names (type parameters and class name itself) and is allocator-aware. Given an StdContainer and Callable, create and populate another StdContainer with return type of the Callable as element type. Creating and populating depends on the equality of element type of the original container and return type of the callable. If they match, a copy is taken and std::transform() is called. Otherwise, the original container is taken by reference, new one is default constructed and it is populated though calling std::transform() with std::back_inserter() as output iterator.

Your solution will solve the new problem and won't have any bugs. Also, for me it would be sufficient to pass into code base, with some cosmetic tweaking.

Answer 2

template <template <typename, typename> class Container, typename A, typename F,
  typename = std::enable_if_t<std::is_same< A,
    decltype(std::invoke(std::declval<F>(), std::declval<A>()))>::value>>

The SFINAE maybe be cleaned up by using some existing traits. std::is_same_v(c++17) is a shorthand helper variable template. For the invoke-able return type, rather than working through values and expressions, you can use only the types through std::result_of(c++11). It also has a helper type of std::result_of_t(c++14). Note - std::result_of was deprecated in March's Kona meeting, so you'll need to use the less fragile version std::invoke_result(c++17) once P0604R0 is implemented into Clang.

template <template <typename, typename> class Container, typename A, typename F,
          typename B = std::result_of_t<F&&(A&&)>,
          typename = std::enable_if_t<std::is_same_v<A, B>>>

---

auto fmap(F f, Container<A, std::allocator<A>> xs) {

You have limited the possible Container types to those that utilize std::allocator. Intentional?

---

std::transform(std::begin(xs), std::end(xs), std::begin(xs), f);

Prefer to use the non-member free functions begin() and end() in an ADL-context if you plan to support any container that doesn't have a member begin() and end().

using std::begin;
using std::end;
std::transform(begin(xs), end(xs), begin(xs), std::forward<F>(f));

---

#include <iostream>
// ...
    std::cout << "I/O type SYMMETRY DETECTED!!\n";

Be aware that including <iostream> in your headers may transparently inject a static constructor into every translation unit that includes it. This is very common in C++ implementations.

---

  if constexpr(std::is_same<ContainerOfB, std::vector<B>>::value) {

Instead of type-matching, consider checking if the container has a member reserve().

// SFINAE if reserve exists
template <typename C>
constexpr auto has_reserve_memfun(C& c) -> decltype(c.reserve(1), bool{}) {
  return true;
}

// Fallback if above is culled because it does not exist or inaccessible
constexpr bool has_reserve_memfun(...) { return false; }

// Now use it in your conditional compilation context
  if constexpr (has_reserve_memfun(result)) {

---

template <typename T>
void printrange(const T r) {
  std::copy(std::cbegin(r), std::cend(r),
            std::ostream_iterator<decltype(*std::begin(r))>(std::cout, ", "));
}

The range you are passing in is passed-by-value to const. Consider passing-by-reference to const or by forwarding reference.

Rather than using std::ostream_iterator<>, use std::ostream_joiner<>(c++17), assuming it's been implemented by your compiler vendor. Otherwise, roll your own.

---

  printrange(
      fmap([](int i) { return '\'' + std::to_string(i) + '\''; },

Don't forget to #include <string>.