Is it possible to use existential types in associated types?

I'm attempting to use existential types in the definition of a trait implementation's associated type. I've minimized what I'm trying to do to the following example:

#![feature(type_alias_impl_trait)]
#![feature(impl_trait_in_assoc_type)]

use std::marker::PhantomData;

trait A<T> {
    type Id;
    
    fn check(&self) -> bool;
}

trait B {
}

struct Test<S: A<T>, T: B> {
    s: S,
    phantom: PhantomData<T>,
}

trait C {
    type State;
    
    fn bar(id: &Self::State, a: Self, b: Self) -> Self;
}

struct X();

mod existential {
  use super::*;
  pub type T = impl B;
  pub type S = impl A<T>;
}

impl C for X {
    type State = Test<existential::S, existential::T>;
    
    fn bar(id: &Self::State, a: Self, b: Self) -> Self {
        if id.s.check() {
            a
        } else {
            b
        }
    }
}

This fails with:

error: unconstrained opaque type
  --> src/lib.rs:30:16
   |
30 |   pub type T = impl B;
   |                ^^^^^^
   |
   = note: `T` must be used in combination with a concrete type within the same module

error: unconstrained opaque type
  --> src/lib.rs:31:16
   |
31 |   pub type S = impl A<T>;
   |                ^^^^^^^^^
   |
   = note: `S` must be used in combination with a concrete type within the same module

Is it currently possible to use existential types in this way?

Existential types exist by being an opaque alias to some concrete type. You have to provide a defining use so the compiler knows what the concrete type is.

mod existential {
    use super::*;
    pub type T = impl B;

    struct Something;
    impl B for Something {}
    fn define_the_t_existential() -> T {
        Something
    }
}

With the current nightly feature, ~every mention of the TAITs in the same module has to define it, which is somewhat annoying. Like mentioning T without defining it made me move S somewhere else here:

mod annoyingly_have_to_use_submodules_a_lot_so_far {
    use super::existential::T;
    use super::A;
    pub type S = impl A<T>;
    struct SomethingElse;
    impl super::A<T> for SomethingElse {
        type Id = ();
        fn check(&self) -> bool {
            true
        }
    }
    fn define_the_s_extential() -> S {
        SomethingElse
    }
}

Thanks for the reply!

How would you call bar with your example? I tried the following but it errors that t's arguments are not the opaque types S and T.

fn main() {
    let a = X();
    let b = X();
    let t = Test {
        s: existential2::SomethingElse,
        phantom: PhantomData::<existential::Something>,
    };
    let _ = X::bar(&t, a, b);
}

Does this also mean that bar can only be called when Test's type arguments are existential2::SomethingElse and existential::Something? I'd like to be able to call bar with any type that implement instances of A and B.

It seems like this should be possible. Behind the scenes, I would expect this would likely be implemented by passing the vtables of the caller's A and B in a tuple with the Test argument.

As an aside, it seems like something closer to Haskell's syntax would be more concise and understandable:

impl C for X {
    type State = for<T: B, S: A<T>> Test<S, T>;

    ...
}

I'd like to be able to call bar with any type that implement instances of A and B.

That sounds like you don't want existential types at all, but generics …

It seems like this should be possible. Behind the scenes, I would expect this would likely be implemented by passing the vtables of the caller's A and B in a tuple with the Test argument.

… or dyn types. If you want the kinds of things that can be done with vtables, you're looking for either dyn or a hand-written enum β€” Rust does not ever create vtables except via dyn. But you can't simply use dyn here to call bar, because in order to call bar the caller has to supply 3 separate values (id, a, b) of matching types, and there is no dynamic type-checking in Rust that could enforce that.

But maybe you just want to be generic over A and B while calling X::bar()? In that case, consider something like this:

use std::marker::PhantomData;

trait A<T> {
    type Id;

    fn check(&self) -> bool;
}
trait B {}

struct Test<S: A<T>, T: B> {
    s: S,
    phantom: PhantomData<T>,
}

trait C<St> {
    fn bar(id: &St, a: Self, b: Self) -> Self;
}

struct X();

impl<S, T> C<Test<S, T>> for X
where
    S: A<T>,
    T: B,
{
    fn bar(id: &Test<S, T>, a: Self, b: Self) -> Self {
        if id.s.check() {
            a
        } else {
            b
        }
    }
}

(By the way, I highly recommend not using single-letter names for your types, to avoid confusion. Haskell has the mandatory rule that all type variables are lowercase, but in Rust, the convention is that type variables have single-character (or sometimes abbreviated) names, and concrete types have longer names.)

2 Likes

I do want existentials, but just for X's trait implementation of C. Here's a somewhat representative example in Haskell:

{-# LANGUAGE TypeFamilies #-}

class A a where
    type Id a

    check :: a -> Bool

class B a where

data PhantomData a = PhantomData

data Test s t = Test {
    s :: s,
    phantom :: PhantomData t
}

class C a where
    data State a
    bar :: State a -> a -> a -> a

data X = X1 | X2
    deriving Show

instance C X where
    data State X = forall s t . (A s, B t) => XState (Test s t)
    bar (XState st) a b = if check (s st) then a else b

instance A Int where
    type Id Int = ()

    check 0 = True
    check _ = False

instance A String where
    type Id String = ()

    check "" = True
    check _ = False

instance B ()

data Y = Y1 | Y2
    deriving Show

instance C Y where
    data State Y = YState
    bar YState a b = a

main = do
    let t1 = Test (0 :: Int) (PhantomData :: PhantomData ())
    print $ bar (XState t1) X1 X2

    let t2 = Test ("Hi" :: String) (PhantomData :: PhantomData ())
    print $ bar (XState t2) X1 X2

    print $ bar YState Y1 Y2

This prints:

X1
X2
Y1

The first call to bar passes a Test Int () while the second passes a Test String (). The final call passes the empty YState to bar since Y does not need any state in its implementation of C. Under the hood, XState is holding Test s t and the vtables of A s and B t.

In Rust, maybe it is possible to explicitly define XState as a separate struct and declare that as X's State for C?

It is certainly the case that all structs must be declared as their own items β€” there is no such thing as an associated struct. However, it might be that you do not need an additional struct XState separate from Test.


I don't fully understand your Haskell code, but here's my new best guess at what you need. Note I've renamed your traits, because it was confusing to read otherwise β€” please do not name traits or concrete types with single letters.

use std::marker::PhantomData;

trait ATrait<T> {
    type Id;

    fn check(&self) -> bool;
}

trait BTrait {}

struct Test<S, T> {
    s: S,
    phantom: PhantomData<T>,
}

/// This trait is implemented for all β€œState” types
trait CState {
    /// This is the β€œC” type that this is a state for.
    /// Please give it a name that actually describes its relationship!
    type CTy;
    fn bar(&self, a: Self::CTy, b: Self::CTy) -> Self::CTy;
}

struct X();
struct XState<S, T>(Test<S, T>);

impl<S, T> CState for XState<S, T>
where
    S: ATrait<T>,
    T: BTrait,
{
    type CTy = X;
    fn bar(&self, a: Self::CTy, b: Self::CTy) -> Self::CTy {
        if self.0.s.check() {
            a
        } else {
            b
        }
    }
}

The key thing is that instead of a trait implemented for X, we now have a trait implemented for XState β€” in Rust, this is a more natural way of expressing the many-to-one relationship that XState has to X, since traits act as type-level functions.

Thanks for suggesting dyn! I managed to get the following compiling:

#![feature(type_alias_impl_trait)]
#![feature(impl_trait_in_assoc_type)]

use std::marker::PhantomData;

trait A<T: ?Sized> {
    // type Id;
    
    fn check(&self) -> bool;
}

impl<T: ?Sized> A<T> for u32 {
    fn check(&self) -> bool {
        self == &0
    }
}

impl<T: ?Sized> A<T> for String {
    fn check(&self) -> bool {
        self == &""
    }
}

trait B {
}

impl B for () {
}

struct Test<S: A<T> + ?Sized, T: B + ?Sized> {
    phantom: PhantomData<T>,
    s: S,
}

trait C {
    type State;
    
    fn bar(id: &Self::State, a: Self, b: Self) -> Self;
}

#[derive(Debug)]
enum X { X1(), X2(), }
struct XState (Box<Test<S, T>>);

type T = dyn B;
type S = dyn A<T>;

impl C for X {
    type State = XState;
    
    fn bar(id: &Self::State, a: Self, b: Self) -> Self {
        if id.0.s.check() {
            a
        } else {
            b
        }
    }
}

#[derive(Debug)]
enum Y { Y1(), Y2(), }

impl C for Y {
    type State = ();
    
    fn bar(_: &Self::State, a: Self, _b: Self) -> Self {
        a
    }
}

fn main() {
    let xstate1 = XState(Box::new(Test {
        s: 0u32,
        phantom: PhantomData,
    }));
    
    println!("{:?}", X::bar(&xstate1, X::X1(), X::X2()));
    
    // This version doesn't work:
    // let t2: Test<String, ()> = Test {
    //     s: " ".to_string(),
    //     phantom: PhantomData,
    // };
    // let xstate2 = XState(Box::new(t2) as Box<Test<dyn A<dyn B>, dyn B>>);
    // This version does work:
    let xstate2 = XState(Box::new(Test {
        s: " ".to_string(),
        phantom: PhantomData,
    }));
    
    println!("{:?}", X::bar(&xstate2, X::X1(), X::X2()));
    
    println!("{:?}", Y::bar(&(), Y::Y1(), Y::Y2()));
    
    ()
}

I'm not sure if the use of Sized is correct and casting an existing Test<u32, ()> to a Box<Test<S, T>> using as fails with "as expression can only be used to convert between primitive types or to coerce to a specific trait object". I'll keep playing around with it.

You can't apply an unsizing coercion except to type parameters that are part of the last field of Test. Therefore, you can't coerce Test<String, ()> to Test<String, dyn B> because the T type parameter appears in phantom, not s.

So, this change will compile:

    let t2: Test<String, dyn B> = Test {
        s: " ".to_string(),
        phantom: PhantomData,
    };
    let xstate2 = XState(Box::new(t2) as Box<Test<dyn A<dyn B>, dyn B>>);

but it's likely that that isn't what you want, since now all Tests will probably have T = dyn B instead of distinct types that provide any constraints.