Return different trait implementation based on compile-time condition

I would like to implement a HList which stores its elements in sorted order. The comparison key is a static const value in the structs.

I have a problem with implementing an insert function. Depending on where the new value should be inserted in the list, the return type will be different.

For demonstration purposes, here's the core of the problem using sorted tuples:

trait HasValue {
  const VALUE: i32;
}

trait SortedTuple {...}

fn make_sorted_tuple<A: HasValue, B: HasValue>(a: A, b: B) -> impl SortedTuple {
  // ILLEGAL:
  if A::VALUE < B:VALUE {
     (a, b)
  } else {
     (b, a)
  }
}

The above code is illegal in Rust because every branch must return the same type.

However, in C++ it is completely fine to return different types from different branches if the if condition can be evaluated at compile time like in my case, eg.:

struct Foo {
    static constexpr int value = 31;
};

struct Bar {
    static constexpr int value = 78;
};

template <class A, class B>
consteval auto make_sorted_pair(A a, B b) {
    if constexpr (A::value < B::value) {
        return std::make_pair(a, b);
    } else {
        return std::make_pair(b, a);
    }
}

int main() {
    auto a = make_sorted_pair(Bar{}, Foo{}); // a is std::pair<Foo, Bar>
}

Can I achieve something similar in Rust?

You can, but it will be more convoluted than in C++ (more like pre-constexpr C++). The key is to use the the trait system (turing complete!) as functions.

Doing this with consts require the unstable generic_const_exprs feature, but you can do it on stable with 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)
}