Here's my understanding of a problem I've encountered several times. Suppose I want to represent simple arithmetic expressions (integers, sums, products). If I want to allocate the nodes on the heap and I don't require shared ownership, then the most straightforward implementation appears to be:

```
enum Expr {
Num(isize),
Sum(Box<Expr>, Box<Expr>),
Prod(Box<Expr>, Box<Expr>),
}
use Expr::*
```

With this definition, we can represent the expressions `1 + 2`

and `3`

as

```
let e1 = Sum(Box::new(Num(1)), Box::new(Num(2)));
let e2 = Num(3);
```

At the moment, the values bound to `e1`

and `e2`

are allocated on the stack, whereas the children of the sum (`Expr::Num(1)`

and `Expr::Num(2)`

) are allocated on the heap. Consequently, the following

```
let e3 = Prod(Box::new(e1), Box::new(e2));
```

must first *copy* the values bound to `e1`

and `e2`

from their locations on the stack into the heap. We can avoid this copying by always working with `Box`

ed `Expr`

s. For instance:

```
let e1 = Box::new(Sum(Box::new(Num(1)), Box::new(Num(2))));
let e2 = Box::new(Num(3));
```

Then

```
let e3 = Box::new(Prod(e1, e2));
```

only requires copying two `Box`

es from the stack to the heap. With this in mind, I'm inclined to define a new type that represents a `Box`

ed expression and work directly with that:

```
struct Expr(Box<_Expr>);
enum _Expr {
Num(isize),
Sum(Expr, Expr),
Prod(Expr, Expr),
}
```

This resembles the use of "opaque pointers" in C, since the `Box`

is now "hidden" inside the (newtype) struct `Expr`

.

What are your thoughts on this pattern? Is this a common way to work with recursive datatypes, or am I over-thinking some of the issues here?