"enum specialization" or sort of GADTs


#1

I’ve been wondering if something like the following has been tried or proposed. I’d love to be able to put type constraints based on generics for specific variants of an enum. Something like

enum Set<T> {
  Bytes([bool; 256]) where T: u8,
  Hash(HashSet<T>) where T: Hash + Eq + !u8,
  Vec(Vec<T>) where T: !Hash + Eq + !u8,
}

Here the where constraints mean that you cannot create a Set::Bytes of any type other than Set<u8> and this enum type would require no tag, since the variant is known at compile time. This would be to morphology similar to trait specialization is to algorithm. It would be similar I’m many ways to Haskell’s GADTs, with the major simplification that it would not enable existential types.

This feature as I imagine it would have a few significant benefits. One is that generic data types could be specialized, so that you wouldn’t need to pay an abstraction penalty as you currently do. With current rust you would need to pay both a space and time penalty in terms of tag storage and checking.

A second benefit is that we could write a single function that handles multiple types in their own best way. I suppose a third would be to enable type level enforcement of data structure invariants, which was the initial selling point of GADTs, with the common example being creating an abstract syntax tree with type of an expression expressed at the type level.

Anyhow, it seems like it would be useful, so I am guessing that it already had a name and an implementation, or a good argument why it would be difficult or unsound.


#2

You can use associated types with trait specialization for that (requires nightly):

trait SetImpl {
    type Backing;
}
impl<T> SetImpl for T where T: Eq {
    default type Backing = Vec<T>;
}
impl<T> SetImpl for T where T: Eq + Hash {
    default type Backing = HashSet<T>;
}
impl SetImpl for u8 {
    type Backing = [bool; 256];
}