rust 类型级编程的类型顺序

tf7tbtn2 于 2023-10-20 发布在其他

关注(0)|答案(1)|浏览(72)

我已经深入研究了Rust中的类型级编程，因为它对我的一个项目非常有帮助。然而，我仍然在努力一点什么是可能的或不可能的。
特别是，我想实现一个类型的顺序来排序元组。这将允许我使用元组，它是类型的“向量”，作为类型的“集合”。
到目前为止，我已经找到了如何在类型级编程中实现链表，我可以使用宏将元组转换为链表（并返回）：

trait LinkedList {}
// empty list
struct EmptyList;
// list: a head, (element in the list) and tail (rest of the list)
struct ListElem<Head, Tail: List>(PhantomData<(Head, Tail)>);
// empty list is a list
impl LinkedList for EmptyList {}
// list element is a list as well
impl<H, T: List> LinkedList for ListElem<H, T> {}

我的转换：（显示了2个元素，但我将使用宏来生成尽可能多的元素）

trait TupleToList {
    type List;
}
trait ListToTuple {
    type Tuple;
}
// this can easily be done with macros, for tuples up to a lot
impl<A, B> TupleToList for (A, B) {
    type List = ListElem<A, ListElem<B, EmptyList>>;
}
impl<A, B> ListToTuple for ListElem<A, ListElem<B, EmptyList>> {
    type Tuple = (A, B);
}

现在，This article显示了类型级别的buble排序，但为此我需要对类型进行排序，可以写为：

struct CompareEQ;
struct CompareLT;
struct CompareGT;
// order between types
trait CompareTypes<T> {
    type Result;
}
// handy shortcut
type TypeOrder<T, U> = <T as CompareTypes<U>>::Result;

(As我想要一组类型，我可以删除EQ运算符，因为任何具有重复类型的元组都将被拒绝）
我的问题是我不知道如何订购我的类型。对于不稳定的特性，比如const traits，const type id我可以写一个const函数来排序类型，但它不是类型级别的：

const fn bigger_type_id<T: 'static, U: 'static>() -> bool {
    let t = unsafe {std::mem::transmute::<_, u128>(TypeId::of::<T>()) };
    let u = unsafe {std::mem::transmute::<_, u128>(TypeId::of::<U>()) };
    t < u
}

如果我想使用它，我需要以某种方式从值级别转换回类型级别，看起来像这样：

impl<T, U> CompareTypes<U> for T {
    type Result = if bigger_type_id<T, U>() { GT } else { LT };
}

(This语法无效）
另外，我可以把所有类型我想排序，并编写另一个宏，写他们的顺序，但这个应用程序是一个库，在那里用户可以定义自己的类型。这意味着我需要他调用这个宏，我不喜欢这个宏。
在类型上实现类型级顺序的替代方案是什么？

编辑：

我已经尝试过了，我使用const泛型并用我的函数计算它们：

#![feature(generic_const_exprs)]

trait BiggerThan<T, const IS_IT: bool> {}

impl<T: 'static, U: 'static> BiggerThan<U, { bigger_type_id::<T, U>() }> for T {}

trait ActuallyBiggerThan<T> {
    type SomeType;
}

impl<T, U: BiggerThan<T, true>> ActuallyBiggerThan<T> for U {
    // Only for some tests
    type SomeType = &'static str;
}

type DoesItWorkOnce = <u8 as ActuallyBiggerThan<bool>>::SomeType;
type DoesItWorkTwice = <bool as ActuallyBiggerThan<u8>>::SomeType;

我试着用这个：

pub fn func() {
    let v1: DoesItWorkOnce = "Hello";
    let v2: DoesItWorkTwice = "World";
}

不幸的是，这两种类型都抛出了错误：
“不匹配的类型期望的常量true找到常量false“
我相信，这意味着这是不工作的一些原因？
我还收到一个功能警告：“特性generic_const_exprs是不完整的，可能不安全使用和/或导致编译器崩溃”，所以可能该特性不能正常工作？

编辑2：

我在第一次编辑时打错了，我要求U实现BiggerThan而不是BiggerThan。
事实证明，我的解决方案确实有效！（我在第一次编辑时修复了错字）

rust

来源：https://stackoverflow.com/questions/77315842/order-on-types-for-type-level-programming

1条答案

按热度按时间

mwecs4sa1#

我已经成功地对元组进行了排序，我将在这里发布我的解决方案：
核心问题是如何使用const fn来实现trait，我发现的技巧是使用#![feature(generic_const_exprs)]：

const fn t_greater_than_u<T: 'static, U: 'static>() -> bool {
    let t = unsafe {std::mem::transmute::<_, u128>(std::any::TypeId::of::<T>()) };
    let u = unsafe {std::mem::transmute::<_, u128>(std::any::TypeId::of::<U>()) };
    t > u
}

/// Defines an order on types.
trait TypeComparaison<T> {
    const GREATER: bool;
}

impl<T: 'static, U: 'static> TypeComparaison<U> for T {
    const GREATER: bool = { t_greater_than_u::<T, U>() };
}

现在，我将把剩下的代码作为资源发布给任何想要在类型级编程中实现排序的人：
首先定义一个列表结构：

pub(crate)  trait List {}
pub(crate)  struct Nil;
pub(crate)  struct Cons<Head, Tail: List>(std::marker::PhantomData<(Head, Tail)>);
impl List for Nil {}
impl<H, T: List> List for Cons<H, T> {}

然后，我们将扩展我们的comparaison来比较一个值与一个列表（与列表的头部）：

trait CompareTypeList<L: List> {
    const GREATER: bool;
}
impl<T> CompareTypeList<Nil> for T {
    const GREATER: bool = false;
}
impl<T: 'static, Head: 'static, L: List> CompareTypeList<Cons<Head, L>> for T {
    const GREATER: bool = <T as TypeComparaison<Head>>::GREATER;
}

然后我们将定义有用的traits（类型级编程中的函数）：
Insertion将允许在我们的列表中插入一个类型，保持任何顺序：

pub(crate) trait Insert<T, const TYPE_GT: bool> { type Output: List; }
impl<T> Insert<T, true> for Nil { type Output = Cons<T, Nil>; }
impl<T> Insert<T, false> for Nil { type Output = Cons<T, Nil>; }
impl<T, Head, L: List> Insert<T, false> for Cons<Head, L> {
    type Output = Cons<T, Cons<Head, L>>;
}
// I'm going to write comments about this : 
// T is the type we want to insert in the list. We implement insert for T on Cons<Head, L>, where T > Head.
// So, we need to create a list where Head is first element, and recursively insert T in the tail of the list.
// for this, T must me comparable with the list L, and L must be insertable with T.
// there we have all our trait bound explained !
impl<T: CompareTypeList<L>, Head, L: List + Insert<T, {<T as CompareTypeList<L>>::GREATER}>> Insert<T, true> for Cons<Head, L> {
    type Output = Cons<Head, <L as Insert<T, {<T as CompareTypeList<L>>::GREATER}>>::Output>;
}

我们现在可以通过递归插入所有元素来对List进行排序：

pub(crate) trait SortList { type SortedList: List; }
// how easy it is to sort an empty list !
impl SortList for Nil { type SortedList = Nil; }
impl<Head, L: List + SortList> SortList for Cons<Head, L>
    where
        Head: CompareTypeList<<L as SortList>::SortedList>, 
        <L as SortList>::SortedList: Insert<Head, {<Head as CompareTypeList<<L as SortList>::SortedList>>::GREATER}>
{
    type SortedList = <<L as SortList>::SortedList as Insert<Head, {<Head as CompareTypeList<<L as SortList>::SortedList>>::GREATER}>>::Output;
}

最后，我们需要一些转换元组<=> List。我们将简单地用宏来实现，它将实现一个看起来像这样的trait：

pub(crate) trait TupleToList { type List; }
pub(crate) trait ListToTuple { type Tuple; }

impl<A, B> TupleToList for (A, B) { type List = Cons<A, Cons<B, Nil>>; }
impl<A, B> ListToTuple for Cons<A, Cons<B, Nil>> { type Tuple = (A, B); }

（我已经展示了2个元素的impl，所以很清楚，但是宏可以为所有元组实现这一点，直到某个长度）
最后，我们可以写我们的排序泛型：

pub(crate) trait TupleSortTrait {
    type Sorted;
}

impl<T> TupleSortTrait for T
where T: TupleToList,
      <T as TupleToList>::List: SortList,
      <<T as TupleToList>::List as SortList>::SortedList: ListToTuple, 
{
    type Sorted = <<<T as TupleToList>::List as SortList>::SortedList as ListToTuple>::Tuple;
}

pub(crate) type TupleSort<T> = <T as TupleSortTrait>::Sorted;

这整件事肯定需要一些清理，正如在评论中提到的，我将尝试找到一个比TypeId更好的类型排序解决方案。
但这是可行的，我们可以写这样的东西：

let v = vec![
    <(u8, String, bool) as Default>::default(),
    <TupleSort<(String, bool, u8)> as Default>::default(),
    <TupleSort<(bool, String, u8)> as Default>::default(),
];

赞(0）回复(0）举报 2023-10-20

我来回答

rust 类型级编程的类型顺序

编辑：

编辑2：

1条答案

相关问题

热门标签

最新问答