Rust 中的类型级映射

Question

我正在尝试在两种类型之间创建一个类型级别的映射，实现为关联列表，以便有效的映射实现特征：

trait Key {
    const KEY: usize;
}

trait TypeLevelMap<K: Key, V> {
    fn convert(K) -> V;
}

nil 的情况很简单：

struct TypeLevelMapNil<T>(PhantomData<T>);

impl<K: Key, V> TypeLevelMap<K, V> for TypeLevelMapNil<V> {
    fn convert(k: K) -> V {
        panic!("Unhandled case: {}", K::KEY);
    }
}

但是，我无法弄清楚缺点：

struct TypeLevelMapCons<K, V, Tl, TlK, TlV>(PhantomData<(K, V, Tl, TlK, TlV)>);

impl<K, V, Tl, TlK, TlV> TypeLevelMap<K,V> for TypeLevelMapCons<K, V, Tl, TlK, TlV>
where
    K: Key,
    Tl: TypeLevelMap<TlK, TlV>,
    TlK: Key,
{
    fn convert(_k: K) -> V {
        unimplemented!()
    }
}

impl<K, V, Tl, TlK, TlV> TypeLevelMap<TlK, TlV> for TypeLevelMapCons<K, V, Tl, TlK, TlV>
where
    K: Key,
    Tl: TypeLevelMap<TlK, TlV>,
    TlK: Key,
{
    fn convert(k: TlK) -> TlV {
        Tl::convert(k)
    }
}

这当然会报错，"conflicting implementations of trait TypeLevelMap<_, _> for type TypeLevelMapCons<_, _, _, _, _>"。我不知道如何告诉 Rust 更喜欢第一个；专业化没有帮助，而且没有 != 的界限。

有没有办法消除它们的歧义，或者有另一种方法来实现这个，或者这不可能在（当前的）Rust 中实现？

Answer 1

如果我没理解错的话，您是想 TypeLevelMapCons<K, V, Tl, TlK, TlV> 使用泛型类型参数的不同组合实现 TypeLevelMap 两次。这是不可能的（从 Rust 1.23.0 开始），因为有可能 K == TlK 或 V == TlV。通过专业化，其中一个 impl 必须严格地比 "default" impl 更具体，即它必须适用于 "default" impl 适用的子集，并且 仅此而已。然而，在这里，K 和 TlK 是不相关的（V 和 TlV 也是如此），因此两者都不比另一个更具体。有一个名为 intersection impls 的提议功能，据我所知，它应该解决这个问题，因为它允许您编写覆盖交集的 impl 以修复冲突的实现错误。

但是，是一种使用专业化的解决方案！第一步是将 TypeLevelMap 更改为非泛型本身；相反，我们将通过将类型参数从那里的特征移动来使 convert 方法通用。通过这样做，我们可以删除 TypeLevelMapCons 上的 TlK 和 TlV 类型参数，它们没有用，因为它们只代表一个尾部可能有许多 TypeLevelMap 的实现（事实上，我认为您当前的设计因此不可行）。

为 TypeLevelMapNil 实现 TypeLevelMap 很容易：我们只需忽略类型参数即可。 （注意：我删除了 TypeLevelMapNil 上的类型参数，因为它是不必要的。） 为 TypeLevelMapCons 实现 TypeLevelMap 有点棘手，因为这是我们需要根据密钥类型采取不同行为的地方。

专门化不允许我们在泛型方法上专门化特定类型参数集，只能在 impl 上进行专门化，那么我们如何实现 TypeLevelMapCons？通过引入辅助通用特征！我们可以有一个处理递归情况的特征的默认实现和一个处理 "found" 情况的专门实现。 （注意：这与标准库用于特化 <Vec<T> as Extend<T>>::extend<I> 的技术相同。）

#![feature(specialization)]

use std::marker::PhantomData;

trait Key {
    const KEY: usize;
}

trait TypeLevelMap {
    fn convert<K: Key, V>(K) -> V;
}

trait TypeLevelMapConvert<LK, LV> {
    fn convert_impl(LK) -> LV;
}

struct TypeLevelMapNil;

impl TypeLevelMap for TypeLevelMapNil {
    fn convert<K: Key, V>(_k: K) -> V {
        panic!("Unhandled case: {}", K::KEY);
    }
}

struct TypeLevelMapCons<K, V, Tl>(PhantomData<(K, V, Tl)>);

impl<K, V, Tl> TypeLevelMap for TypeLevelMapCons<K, V, Tl>
where
    K: Key,
    Tl: TypeLevelMap,
{
    fn convert<LK: Key, LV>(k: LK) -> LV {
        <Self as TypeLevelMapConvert<LK, LV>>::convert_impl(k)
    }
}

impl<K, V, Tl, LK, LV> TypeLevelMapConvert<LK, LV> for TypeLevelMapCons<K, V, Tl>
where
    K: Key,
    Tl: TypeLevelMap,
    LK: Key,
{
    default fn convert_impl(k: LK) -> LV {
        Tl::convert(k)
    }
}

impl<K, V, Tl> TypeLevelMapConvert<K, V> for TypeLevelMapCons<K, V, Tl>
where
    K: Key,
    Tl: TypeLevelMap,
{
    fn convert_impl(_k: K) -> V {
        unimplemented!()
    }
}

// Sample usage

impl Key for i16 {
    const KEY: usize = 16;
}

impl Key for i32 {
    const KEY: usize = 32;
}

impl Key for i64 {
    const KEY: usize = 64;
}

fn main() {
    TypeLevelMapCons::<i16, i16, TypeLevelMapCons<i32, i32, TypeLevelMapCons<i64, i64, TypeLevelMapNil>>>::convert::<i64, i64>(0);
}

为什么这次专业化有效？首先，让我们看一下默认的实现：

impl<K, V, Tl, LK, LV> TypeLevelMapConvert<LK, LV> for TypeLevelMapCons<K, V, Tl>

这里，LK和LV分别独立于K和V。这意味着这个 impl 将为特定 TypeLevelMapCons<K, V, Tl> 类型生成无限数量的具体特征实现。

现在，让我们看一下专门的实现：

impl<K, V, Tl> TypeLevelMapConvert<K, V> for TypeLevelMapCons<K, V, Tl>

这是我们在 trait 和实现者类型上使用 K 和 V。通过这样做，我们在 K 和 V 上引入了等式约束。这意味着此 impl 只会为特定 TypeLevelMapCons<K, V, Tl> 类型生成单个特征实现。这显然比默认的 impl!

更具体

Rust 中的类型级映射

Type-level Map in Rust

types

rust

hlist

type-level-computation