"like that Enum, but with additional option" on recursive types

[anon80458984]

Suppose we have:

pub enum Color {
  Red,
  Blue,
  Green,
}

and we want to add another option, we can say:

pub enum ColorWithGold {
  Color(Color),
  Gold
}

so we can implement "like this other enum, but with this additional field" by merely "embedding" one struct within another.

Now, suppose we have a recursive type:

pub enum Expr {
  Var(String),
  Int(i64),
  Add(Rc<Expr>, Rc<Expr>),
  Mul(Rc<Ex;r>, Rc<Expr>)
}

and we want to add another option to this Enum, the constant Pi.

pub struct ExprWithPi {
  Expr(Expr),
  Pi
}

doesn't cut it since the inner Expr is a Expr, not a ExprWithPi

===

Is there a solution to this problem, or do type systems forbid any nice solution to this?

[RustyYato]

This would require an unbounded number of possible extensions (because there is always something else we could add to Expr, like Sub or Paren, or whatever else). Hmm, unbounded number of possiible Expr, why does that sound familiar?

This sounds like a job for traits!

pub trait Expr {}

struct Var(String);
struct Int(i64);
struct Add(Rc<dyn Expr>, Rc<dyn Expr>);
struct Mul(Rc<dyn Expr>, Rc<dyn Expr>);

impl Expr for Var {}
impl Expr for Int {}
impl Expr for Add {}
impl Expr for Mul {}

// later

struct Pi;

impl Expr for Pi {}

[anon80458984]

This was not mentioned as a requirement in the original question, but now we lose the ability to do match / de-structuring, and possibly other useful things.

[RustyYato]

Yes, but you also want an unbounded number of variants. You can't have both pattern matching and an unknown number of variants.

It is an unbounded number of variants because we don't know how many possible extensions we are going to have. Also, you can get many of the uses of pattern matching by just using polymorphism. Just make whatever behaviors that need to be customized based on the type a method.

trait Expr {
    fn eval(&self, context: &Context) -> i64;
}

[cbiffle]

Another option, if you control both types, is to allow for extension in the original type.

pub enum Expr<X> {
  Var(String),
  Int(i64),
  Add(Rc<Expr<X>>, Rc<Expr<X>>),
  Mul(Rc<Expr<X>>, Rc<Expr<X>>),
  Ext(X),
}

pub struct Pi;

pub type ExprWithPi = Expr<Pi>;

This retains pattern matching but, of course, the original type has to plan to be extended.

This overall problem is the topic of a paper from the Haskell world called Trees that Grow. That paper also provides solutions for adding fields after the fact (using, you guessed it, another type parameter). It is not the most readable paper, unfortunately, particularly if you don't speak Haskell.

[anon80458984]

@cbiffle : Modifying the original with a type parameter is the solution I'm looking for. Thanks!