types - 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)
    }
}

这当然会产生错误，“特征 TypeLevelMap<_, _> 与类型 TypeLevelMapCons<_, _, _, _, _> 的实现冲突”。我不知道如何告诉 Rust 更喜欢第一个；特化没有帮助，也没有 !=在什么范围内。

有没有办法消除它们的歧义，或者有其他方法可以实现这个，或者这不可能在(当前的)Rust 中实现？

Answer 1

如果我没理解错的话，你正试图拥有 TypeLevelMapCons<K, V, Tl, TlK, TlV>实现 TypeLevelMap两次使用泛型类型参数的不同组合。这是不可能的(从 Rust 1.23.0 开始)，因为有可能 K == TlK或者那个V == TlV .通过专门化，其中一个 impl 必须严格地比“默认”impl 更具体，即它必须适用于“默认”impl 适用的子集，仅此而已。然而，在这里，K和 TlK是不相关的(对于 V 和 TlV 也是如此)，因此两者都不比另一个更具体。有一个提议的功能称为 intersection impls据我所知，应该解决这个问题，因为它允许您编写涵盖交叉点的 impl 以修复冲突的实现错误。

但是， 有一个使用特化的解决方案!第一步是改变TypeLevelMap本身不是通用的；相反，我们将制作 convert通过将类型参数从那里的特征移动到泛型方法。通过这样做，我们可以删除 TlK和 TlV在 TypeLevelMapCons 上键入参数，它们没有用，因为它们仅代表 TypeLevelMap 的可能许多实现中的一个尾部可能有(事实上，我认为您当前的设计因此不可行)。

实现 TypeLevelMap对于 TypeLevelMapNil很简单:我们只需忽略类型参数。 (注意:我删除了 TypeLevelMapNil 上的类型参数，因为它是不必要的。) 实现 TypeLevelMap对于 TypeLevelMapCons有点棘手，因为这是我们需要根据 key 类型采取不同行为的地方。

特化不允许我们在泛型方法上特化特定类型参数集，只能在 impl 上特化，那么我们如何实现 TypeLevelMapCons ？通过引入辅助通用特征!我们可以有一个处理递归情况的特征的默认实现和一个处理“找到”情况的专门实现。 (注意:这与标准库用于专门化 <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>

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