Возвращает различную реализацию типажа на основе условия времени компиляции

Это не работает, потому что fn foo() -> impl Trait — это сокращение от fn <T: Trait> foo() -> T. Таким образом, T будет конкретным типом в конце (например, (A, B)); make_sorter_pair будет компилироваться отдельно для каждого экземпляра T и, конечно же, T не может отличаться в зависимости от того, что происходит во время выполнения.

Чтобы ржавчина считала возвращаемое значение «чем-то типа Trait» без учета конкретного типа, вы можете использовать dyn Trait. Но ржавчина должна знать размер объекта во время компиляции, поэтому вы не можете вернуть dyn Trait сам по себе (который может быть реализован любым конкретным типом Trait и поэтому размер может отличаться).

Вместо этого вам придется использовать &dyn Trait, который не очень хорошо сочетается с семантикой владения, или Box<dyn Trait>, который переместит объект в кучу. Есть разные способы скрыть это многословие - например. обернув вещь в структуру - но я бы начал с Box<dyn Trait>.

Если вы хотите использовать свою черту в качестве dyn, вам необходимо следовать некоторым правилам при ее определении; например, у вас не может быть методов с параметрами типа. Попробуйте, если это соответствует вашему определению черты характера, иначе читайте больше о ключевом слове dynздесь.

Можно, но это будет более запутанно, чем в C++ (больше похоже на C++ до constexpr). Ключевым моментом является использование системы признаков (полностью по Тьюрингу!) в качестве функций.

Для этого с помощью const требуется нестабильная функция generic_const_exprs, но вы можете сделать это в стабильной версии с помощью typenum:

use typenum::{False, Integer, IsLess, True};

// Any method you need on the tuple members will need to be on this trait.
trait HasValue {
    type Value: Integer;
}

type Value<T> = <T as HasValue>::Value;
type ValueIsLess<A, B> = <Value<A> as IsLess<Value<B>>>::Output;
type SortedTuple<A, B> = (
    <ValueIsLess<A, B> as MakeSortedTuple<A, B>>::First,
    <ValueIsLess<A, B> as MakeSortedTuple<A, B>>::Second,
);

trait MakeSortedTuple<A, B> {
    type First: HasValue;
    type Second: HasValue;
    fn new(a: A, b: B) -> (Self::First, Self::Second);
}

impl<A: HasValue, B: HasValue> MakeSortedTuple<A, B> for True {
    type First = A;
    type Second = B;
    fn new(a: A, b: B) -> (Self::First, Self::Second) {
        (a, b)
    }
}

impl<A: HasValue, B: HasValue> MakeSortedTuple<A, B> for False {
    type First = B;
    type Second = A;
    fn new(a: A, b: B) -> (Self::First, Self::Second) {
        (b, a)
    }
}

fn make_sorted_tuple<A, B>(a: A, b: B) -> SortedTuple<A, B>
// Yep, this is a monster.
// It's because Rust, unlike C++, requires you to declare all trait bounds upfront.
where
    A: HasValue,
    B: HasValue,
    Value<A>: IsLess<Value<B>>,
    ValueIsLess<A, B>: MakeSortedTuple<A, B>,
{
    <ValueIsLess<A, B> as MakeSortedTuple<A, B>>::new(a, b)
}