Type-level Map in Rust

Question

I'm trying to make a type-level map between two types, implemented as an association list, such that a valid map implements the trait:

trait Key {
    const KEY: usize;
}

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

The nil case is easy:

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

However, I can't figure out the cons case:

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

This of course gives an error, "conflicting implementations of trait TypeLevelMap<_, _> for type TypeLevelMapCons<_, _, _, _, _>". I can't figure out how to tell Rust to prefer the first one; specialization didn't help, and there's no != in where bounds.

Is there a way to disambiguate them, or is there another way to implement this, or is this impossible to implement in (current) Rust?

Answer 1

If I understand correctly, you are trying to have TypeLevelMapCons<K, V, Tl, TlK, TlV> implement TypeLevelMap twice with different combinations of generic type parameters. This is not possible (as of Rust 1.23.0), because there is the possibility that K == TlK or that V == TlV. With specialization, one of the impls must be strictly more specific than the "default" impl, i.e. it must apply to a subset of what the "default" impl applies to, and nothing more. However, here, K and TlK are unrelated (and likewise for V and TlV), so neither is more specific than the other. There is a proposed feature called intersection impls that, as I understand it, should address this as it would allow you to write the impl that covers the intersection in order to fix the conflicting implementations error.

However, there is a solution using specialization! The first step is to change TypeLevelMap to not be generic itself; instead, we'll make the convert method generic by moving the type parameters from the trait there. By doing this, we can remove the TlK and TlV type parameters on TypeLevelMapCons, which are of no use because they only represent one of the possibly many implementations of TypeLevelMap that the tail may have (in fact, I believe your current design is unworkable because of this).

Implementing TypeLevelMap for TypeLevelMapNil is easy: we simply disregard the type parameters. (Note: I've removed the type parameter on TypeLevelMapNil because it was unnecessary.) Implementing TypeLevelMap for TypeLevelMapCons is a bit trickier because this is where we need to behave differently depending on the type of the key.

Specialization doesn't let us specialize particular sets of type parameters on generic methods, only on impls, so how can we implement TypeLevelMapCons? By introducing an auxiliary generic trait! We can have a default implementation of that trait that handles the recursive case and a specialized implementation that handles the "found" case. (Note: this is the same technique that the standard library uses to specialize <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);
}

Why does the specialization work this time? First, let's look at the default impl:

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

Here, LK and LV are independent from K and V, respectively. This means that this impl will generate an infinite number of concrete trait implementations for a particular TypeLevelMapCons<K, V, Tl> type.

Now, let's look at the specialized impl:

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

Here is that we're using K and V on both the trait and the implementer type. By doing this, we've introduced equality constraints on K and V. This means that this impl will only generate a single trait implementation for a particular TypeLevelMapCons<K, V, Tl> type. This is clearly more specific that the default impl!