Pattern matching with Box layers

Question

I am trying to solve the expression problem in Rust. I have defined a sum type of terms:

#[derive(Clone, Debug, PartialEq)]
pub enum Term {
    True,
    False,
    Not(Box<Term>),
    ...
}

The compiler and documentation say Box is needed for recursive terms because a structure cannot contain itself (infinite regress), and just plain &Term would not be enough to establish that a term owns its subterms. Okay, so far so good.

Now I'm trying to write a function that simplifies terms according to the definitions of the operators, e.g. not true = false:

impl Term {
    pub fn simplify(self) -> Term {
        let a = self.map(Term::simplify);
        match a {
            Term::Not(Box(Term::True)) => Term::False,
            _ => a,
        }
    }

    pub fn map(self, f: fn(Term) -> Term) -> Term {
        match self {
            Term::True
            | Term::False => self,
            Term::Not(a) => Term::Not(Box::new(a.map(f))),
            _ => panic!(),
        }
    }
}

but the compiler doesn't like any version of it that I have tried so far.

Term::Not(Term::True) is not valid because a Box needs to go in between.

Term::Not(Box::new(Term::True)) is valid when making a term, but not as a pattern match expression (which cannot contain function calls).

Term::Not(Box(Term::True)) is not valid either.

What is the right way to do this in Rust?

Answer 1

The compiler gives the following error: cannot match against a tuple struct which contains private fields. Okay, so let's look for the definition of Box (I removed the trait bounds for simplicity):

pub struct Box<_>(Unique<T>, A);

That looks like the tuple in the error message. But it also looks like the inner values are not public (that's the error), so you can't construct the box like this (Box(Term::True)).

What can we do? You could use the nightly feature box_patterns to create the box:

match a {
    Term::Not(box Term::True) => Term::False,
    _ => a,
}

Playground

Or, we try to extract the value out of the box (here in boxed_value) via dereferencing it and then check the inner value:

*boxed_value == Term::True

You can use this in combination with if guards in your match:

match a {
    Term::Not(content) if *content == Term::True => Term::False,
    _ => a,
}

This variant is in my opinion better, especially if you also want to map from Term::False to Term::True.

Playground