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 {
    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 Boxed Exprs. For instance:

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


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

only requires copying two Boxes from the stack to the heap. With this in mind, I'm inclined to define a new type that represents a Boxed expression and work directly with that:

struct Expr(Box<_Expr>);

enum _Expr {
    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.