# Newtyping smart pointers for recursive datatypes

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?

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.