How to implement the generalized form of std::same_as (i.e. for more than two type parameters) that is agnostic to parameter order?

Question

Background

We know that the concept std::same_as is agnostic to order (in other words, symmetric): std::same_as<T, U> is equivalent to std::same_as<U, T> (related question). In this question, I would like to implement something more general: template <typename ... Types> concept same_are = ... that checks whether types in the pack Types are equal to each other.

My attempt

#include <type_traits>
#include <iostream>
#include <concepts>

template <typename T, typename... Others>
concept same_with_others = (... && std::same_as<T, Others>);

template <typename... Types>
concept are_same = (... && same_with_others<Types, Types...>);

template< class T, class U> requires are_same<T, U>
void foo(T a, U b) {
    std::cout << "Not integral" << std::endl;
}

// Note the order <U, T> is intentional
template< class T, class U> requires (are_same<U, T> && std::integral<T>)
void foo(T a, U b) {
    std::cout << "Integral" << std::endl;
}

int main() {
    foo(1, 2);
    return 0;
}

(My intention here is to enumerate over every possible ordered pair of types in the pack)

Unfortunately, this code would not compile, with the compiler complaining that the call to foo(int, int) is ambiguous. I believe that it considers are_same<U, T> and are_same<T, U> as not equivalent. I would like to know why the code fails how I can fix it (so that the compiler treats them as equivalent)?

Answer 1

From cppreference.com Constraint_normalization

The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping. This includes all fold expressions, even those folding over the && or || operators.

So

template <typename... Types>
concept are_same = (... && same_with_others<Types, Types...>);

is "atomic".

So indeed are_same<U, T> and are_same<T, U> are not equivalent.

I don't see how to implement it :-(

Answer 2

The problem is, with this concept:

template <typename T, typename... Others>
concept are_same = (... && std::same_as<T, Others>);

Is that the normalized form of this concept is... exactly that. We can't "unfold" this (there's nothing to do), and the current rules don't normalize through "parts" of a concept.

In other words, what you need for this to work is for your concept to normalize into:

... && (same-as-impl<T, U> && same-as-impl<U, T>)

into:

... && (is_same_v<T, U> && is_same_v<U, T>)

And consider one fold-expression && constraint to subsume another fold-expression constraint && if its underlying constraint subsumes the other's underlying constraint. If we had that rule, that would make your example work.

It may be possible to add this in the future - but the concern around the subsumption rules is that we do not want to require compilers to go all out and implement a full SAT solver to check constraint subsumption. This one doesn't seem like it makes it that much more complicated (we'd really just add the && and || rules through fold-expressions), but I really have no idea.

Note however that even if we had this kind of fold-expression subsumption, are_same<T, U> would still not subsume std::same_as<T, U>. It would only subsume are_same<U, T>. I am not sure if this would even be possible.