C++ Reflection: Another Monad

“Discovery consists of seeing what everybody has seen, and thinking what nobody has thought.”

— Albert Szent-Györgi, 1937 Nobel Laureate for Medicine

I’m sure others have thought this, but they’re certainly not saying much about it. Barry’s recent blog post “Behold the power of meta::substitute” got so close to saying the words… in fact he even said, “the substitute/extract/invoke dance is remarkably powerful.”

So I’m going to say it plainly: yes! Because substitute is basically fmap, and extract can implement join. Among other things, reflection gives us the monad for type function composition.

To be a monad, we need three things: pure (/ return), fmap and bind or join.

pure :: a -> m a
This is just the reflection operator ^^. It takes a type from “type-land” into “reflection-land”. As a type function:

template <typename T>
constexpr auto pure = ^^T;

fmap :: (a -> b) -> f a -> f b
This is basically substitute:

template <template <typename...> typename F>
consteval auto fmap(std::same_as<std::meta::info> auto... as) {
  return substitute(^^F, {as...});
}

In fact, substitute is a little more than unary fmap, it’s n-ary fmap, which is equivalent to <*> (“ap”). So substitute gives us not only the functor, but the applicative functor.

join :: m (m a) -> m a
bind :: (a -> m b) -> m a -> m b

We have join pretty directly:

consteval auto join(std::meta::info a) {
  return extract<std::meta::info>(a);
}

And given P2841 — which is also in C++26 — we can write bind:

template <template <typename> auto F>
consteval auto bind(std::meta::info a) {
  return join(substitute(^^F, {a}));
}

All good. But hold on a minute — we also need to satisfy a few laws. To do that we need a useful definition of equality, which I’m going to take as:

consteval auto equal(std::meta::info a, std::meta::info b) {
  return dealias(a) == dealias(b);
}

For some reason, reflection deviates from the existing language behaviour with respect to aliases. Perhaps the authors of reflection were concerned with not losing information, or perhaps there is some warty technical reason buried in C++. But at any rate, the language surface up until now does not give us alias differences, so I’m going with alias equality.

Back to the laws — left identity:

// return a >>= h <=> h a

template <template <typename> auto F, typename T>
consteval auto left_id() {
  return equal(bind<F>(pure<T>), F<T>);
}

And right identity:

// m >>= return <=> m

template <std::meta::info M>
consteval auto right_id() {
  return equal(bind<pure>(M), M);
}

The fmap law, for which proof we need an “old-style” composition helper:

// xs >>= return . f <=> fmap f xs

template <template <typename...> typename F>
struct pure_dot_f {
  template <typename... Ts>
  constexpr static auto fn = pure<F<Ts...>>;
};

template <template <typename...> typename F, typename... Ts>
consteval auto fmap_law() {
  return equal(bind<pure_dot_f<F>::template fn>(^^Ts...), fmap<F>(^^Ts...));
}

Of course the composition helper is just to show that this is correct according to “the old ways”, which are clunky. Where we’re going, we won’t need it any more.

And finally the associativity law — once again, with an old-style helper:

// (m >>= g) >>= h <=> m >>= (\x -> g x >>= h)

template <template <typename> auto G, template <typename> auto H>
struct assoc_rhs_part {
  template <typename X>
  constexpr static auto fn = bind<H>(G<X>);
};

template <template <typename> auto G, template <typename> auto H>
consteval auto assoc_law(std::meta::info m) {
  auto lhs = bind<H>(bind<G>(m));
  auto rhs = bind<assoc_rhs_part<G, H>::template fn>(m);
  return equal(lhs, rhs);
}

And Robert is your mother’s brother. https://compiler-explorer.com/z/o4fG3P5K3

So this is (one reason) why reflection is powerful: among other things, it implements the type function composition monad. With ^^, substitute and extract<std::meta::info> we have everything we need. And once you grok this, you’re off to the races. Makes sense, right? One intuition for monads is that they lift values and computations into a new world — in this case, the reflected world.

C++26 gives us type function composition machinery in the language, and TMP libraries everywhere will be able to take advantage.