Code shared from the Rust Playground

playground.rs

pub struct Int(i64);
pub struct Add<E>(E,E);
pub struct Mul<E>(E,E);

trait Evaluate { fn eval(&self) -> i64; }
impl Evaluate for Int { fn eval(&self) -> i64 { self.0 } }
impl<E> Evaluate for Add<E> where E: Evaluate { fn eval(&self) -> i64 { self.0.eval() + self.1.eval() } }
impl<E> Evaluate for Mul<E> where E: Evaluate { fn eval(&self) -> i64 { self.0.eval() * self.1.eval() } }

#[test]
fn can_evaluate() {
    assert_eq!(Int(6).eval(), 6);
    assert_eq!(Add(Int(1), Int(5)).eval(), 6);
    assert_eq!(Mul(Int(2), Int(3)).eval(), 6);
}

pub enum Enum<L,R>{Left(L), Right(R)}
impl<L,R> Evaluate for Enum<L,R> where L: Evaluate, R: Evaluate {
    fn eval(&self) -> i64 {
        match self {
            Enum::Left(l) => l.eval(),
            Enum::Right(r) => r.eval(),
        }
    }
}

type AddSig<E> = Enum<Int, Add<E>>;
pub struct AddExpr(Box<AddSig<AddExpr>>);
impl Evaluate for AddExpr { fn eval(&self) -> i64 { self.0.eval() } }   // A

#[test]
fn can_evaluate_add_expr() {
    let expr = AddExpr(Box::new(Enum::Right(Add(
        AddExpr(Box::new(Enum::Left(Int(1)))),
        AddExpr(Box::new(Enum::Left(Int(5))))))));
    assert_eq!(expr.eval(), 6);
}

type MulSig<E> = Enum<Int, Mul<E>>;
pub struct MulExpr(Box<MulSig<MulExpr>>);
impl Evaluate for MulExpr { fn eval(&self) -> i64 { self.0.eval() } }   // B

#[test]
fn can_evaluate_mul_expr() {
    let expr = MulExpr(Box::new(Enum::Right(Mul(
        MulExpr(Box::new(Enum::Left(Int(2)))),
        MulExpr(Box::new(Enum::Left(Int(3))))))));
    assert_eq!(expr.eval(), 6);
}

trait Expression {
    type Signature;
    fn wrap(sig: Self::Signature) -> Self;
    fn unwrap(&self) -> &Self::Signature;
}

impl Expression for AddExpr {
    type Signature = AddSig<AddExpr>;
    fn wrap(sig: Self::Signature) -> Self { AddExpr(Box::new(sig)) }
    fn unwrap(&self) -> &Self::Signature { &self.0 }
}

impl Expression for MulExpr {
    type Signature = MulSig<MulExpr>;
    fn wrap(sig: Self::Signature) -> Self { MulExpr(Box::new(sig)) }
    fn unwrap(&self) -> &Self::Signature { &self.0 }
}

// I'd love to be able to replace lines A and B above with the following!
/*
impl<E> Evaluate for E where E: Expression, E::Signature: Evaluate {
    fn eval(&self) -> i64 { self.unwrap().eval() }
}
*/

Rust playground link