C++ equivalent of algebraic datatype?

Question

Let's say I have this Haskell code:

data RigidBody = RigidBody Vector3 Vector3 Float Shape -- position, velocity, mass and shape
data Shape = Ball Float -- radius
           | ConvexPolygon [Triangle]

What would be the best way to express this in C++?

struct Rigid_body {
    glm::vec3 position;
    glm::vec3 velocity;
    float mass;
    *???* shape;
};

The thing I'm asking is how to represent shape inside the struct when it can be one of two types.

Answer 1

There are different approaches that can be used to solve that problem in C++.

The pure-OO approach you would define an interface Shape and have the two different options as derived types implementing that interface. Then the RigidBody would contain a pointer to a Shape that would be set to refer to either a Ball or a ConvexPolygon. Pro: people love OO (not sure this is a pro really :)), it is easily extensible (you can add more shapes later on without changing the type). Con: You should define a proper interface for Shape, it requires dynamic allocation of memory.

Putting OO aside, you can use a boost::variant or similar type, that is basically a tagged union that will hold one of the types. Pro: no dynamic allocations, shape is local to the object. Con: not pure-OO (people love OO, you remember right?), not so easy to extend, cannot use the shape generically

Answer 2

You are going to want to create a base class Shape. From here, you can create your actual shape classes, Ball and ConvexPolygon. You are going to want to make sure that Ball and ConvexPolygon are children of the base class.

class Shape {
    // Whatever commonalities you have between the two shapes, could be none.
};

class Ball: public Shape {
    // Whatever you need in your Ball class
};

class ConvexPolygon: public Shape {
    // Whatever you need in your ConvexPolygon class
};

Now, you can make a generalized object like this

struct Rigid_body {
    glm::vec3 position;
    glm::vec3 velocity;
    float mass;
    Shape *shape;
};

and when you actually initialize your shape variable, you can initialize it with either a Ball or ConvexPolygon class. You can continue making as many shapes as you would like.

Answer 3

The canonical way to do this in C++ is the inheritance-based solution given in Justin Wood's answer. Canonically, you endow the Shape with virtual functions that each kind of Shape

However, C++ also has union types. You can do "tagged unions" instead:

struct Ball { /* ... */ };
struct Square { /* ... */ };
struct Shape {
  int tag;
  union {
    Ball b;
    Square s;
    /* ... */
  }
};

You use the tag member to say whether the Shape is a Ball or a Square or whatever else. You can switch on the tag member and whatnot.

This has the disadvantage that a Shape is one int larger than the biggest of Ball and Square and the others; objects in OCaml and whatnot do not have this problem.

Which technique you use will depend on how you're using the Shapes.

Answer 4

To throw another possibility in here, you can also use boost::variant which is being added to the standard library in C++17 as std::variant:

struct Ball { float radius; };
struct ConvexPolygon { Triangle t; }

using Shape = boost::variant<Ball, ConvexPolygon>;

The advantages of this approach:

• Type-safe, unlike tagged unions
• Can hold complex types, unlike unions
• Does not require a uniform interface across all "child" types, unlike OO

Some disadvantages:

• Sometimes requires you to do a type check when accessing the variable to confirm that it is the type you want it to be, unlike OO
• Requires you to use boost, or be C++17 compatible; these may be difficult with some compilers or some organizations where OO and unions are universally supported