7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm grateful for your insight. Your code is very understandable, even to a 3-day novice of the technique. I'm surprised that the idea to factor the tests out into helpers didn't occur to me. It certainly would have for any other code I was writing. I'm curious why mutable_in_place isn't in the details namespace. \$\endgroup\$ – Timtro Jun 28 '17 at 16:42
  • \$\begingroup\$ Also, I was avoiding result_of, because it apparently fails in some cases where std::bind is used. Since I'm doing functional programming, I can reliably expect to get passed partially applied functions. I don't know any details of the result_of issues, but I heard Walter E. Brown say something about it, and then saw Stephan T. Lavavej admonish against it in this talk ( youtu.be/zt7ThwVfap0?t=16m ). That is why I cobbled together that solution using decltype, declval and invoke until clang implements std::invoke_result from C++17. \$\endgroup\$ – Timtro Jun 28 '17 at 17:59
  • 1
    \$\begingroup\$ @Timtro, I've addressed all the points you've given. It seems like I made decisions subconsciously though. \$\endgroup\$ – Incomputable Jun 29 '17 at 2:38
  • \$\begingroup\$ I know we should avoid expressing thanks in the comments, but your guidance has been far more than merely helpful. I really appreciate it. \$\endgroup\$ – Timtro Jun 29 '17 at 2:46
2
\$\begingroup\$
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() 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(). It also has a helper type of std::result_of_t(). Note - std::result_of was deprecated in March's Kona meeting, so you'll need to use the less fragile version std::invoke_result() 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<>(), 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>.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your insightful reply. I'm aware of the _v helper aliases, but alas, they are not in clang 4.0 yet, and neither is invoke_result. That is why I temporarily pieced the return type together with decltype, declval and invoke, rather than using the deprecated result_of. Spot-on, pointing out the std::allocator issue. It wasn't intentional, but I didn't know how to do otherwise. I love your test for reserve. That was what I tried first, but failed. But the solution is obvious now that I've seen it. The printrage fn was ad-hoc. Not production code. I just forgot the &. \$\endgroup\$ – Timtro Jun 28 '17 at 16:55
  • \$\begingroup\$ Actually, I'm fond of your consttexpr has_reserve_memfun predicate. It's much cleaner than the template struct based idioms I've seen. I'll have to spend some time playing with it to see how general it can be. In particular, I want to see how it relates to W. E. Browne's void_t idiom, since they both predicate the instantiation of a result based on the validity of an expression. But because I'm about 3-days new to all of this, it isn't obvious to me what the differences are. \$\endgroup\$ – Timtro Jun 28 '17 at 19:28
  • 1
    \$\begingroup\$ Brown's detection idiom is a generalized approach. Would definitely recommend using it if you know about it. Marshall Clow gave a talk at CPPNow on the Detection Idiom. \$\endgroup\$ – Snowhawk Jul 8 '17 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.