### Modeling Recursive Sum Types in C++11 Using boost::variant

It's been a while. But here's something cool.

I used to love pattern matching with sum types in OCaml in college. But I also love how useful and ubiquitous C++ is. So I wanted pattern matching and sum types, but in C++. Well, people say boost::variant can be used as a sum type. The library boost::variant is fairly ubiquitous, well-maintained, and can even run on C++98, the older C++ standard. I can see how discriminated unions can implement “flat” sum types, but can it be used to implement recursive sum types?

Well, I decided to try it. It turns out, with a bit of scaffolding on my part, I was able to implement a recursive sum type. I tried to model the quintessential recursive type, the natural number, which is either zero or the successor to some other number. The following code shows the results of my efforts.

```// sum_type.cpp
#include <iostream>
#include <boost/variant.hpp>
#include <memory>

struct zero {};
class successor;

typedef boost::variant<zero,successor> number;

class successor
{
private:
std::unique_ptr<const number> num;
public:
successor() = delete;
successor(const number& n) : num(new number(n)) {}
successor(const successor& s) : num(new number(s.n())) {}
successor(successor&& s) : num(std::move(s.num)) {}

const number& n() const {
return *num;
}
};

struct match_count : public boost::static_visitor<int>
{
int operator ()(const zero& z) const
{
return 0;
}
int operator ()(const successor& s) const
{
// Do NOT use `return (*this)(s.n()) + 1`
return boost::apply_visitor(*this, s.n()) + 1;
}
};

number add(const number& a, const number& b)
{
/*
match a with
0 => b
S n => S add(n, b)
*/
struct match_a : public boost::static_visitor
{
const number b;
match_a(const number& b) : b(b) {}
number operator()(const zero& a) const
{
return b;
}
number operator()(const successor& a) const
{
}
};
return  boost::apply_visitor(match_a(b), a);
}

int main() {
number a = zero();
number b = successor(a);
number c = successor(b);
number d = add(b,c);
match_count mc;
int c_count = boost::apply_visitor(mc, c);
int b_count = boost::apply_visitor(mc, b);
int a_count = boost::apply_visitor(mc, a);
int added = boost::apply_visitor(mc, d);
std::cout << "a is " << a_count << std::endl;
std::cout << "b is " << b_count << std::endl;
std::cout << "c is " << c_count << std::endl;
std::cout << "a + b is " << added << std::endl;
}
```

Output:

```[ djhaskin987@djhaskin987-S301LA:~ ]\$ g++ -o sum_type -std=c++11 sum_type.cpp
a is 0
b is 1
c is 2
a + b is 3
```
I modelled the type as a discriminated union between “zero” and “successor”. Some interesting things I learned when I did this, or at least some things to note:
• As long as you manage memory properly in the recursive cases, they work fine as part of the sum type using boost::variant.
• It’s okay to have a type with no members (e.g. struct zero {};)
• You can define anonymous classes inside function definitions. Here, they aren’t anonymous, but experimentation will show that you can (in C++11).
• You can call functions recursively when you define structs inside those functions. That’s nice.
• When defining “matching” structs inside functions, try to match variable names with class member names that they are used to construct. This saves time later reasoning about what’s going on.