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?

score 5 · Accepted Answer · answered Dec 22 '21 at 12:38

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

That works! I like the first one better, particularly as it turns out you can also use the `box` syntax in ordinary expressions – it requires another feature guard to be enabled, but it's worth it, is enough of an improvement on the general syntax for making compound things, to make Rust a significantly better language for this domain. — rwallace, Dec 22 '21 at 12:54

Pattern matching with Box layers

1 Answers1