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 successor(add(a.n(), b)); } }; 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 [ djhaskin987@djhaskin987-S301LA:~ ]$ ./sum_type a is 0 b is 1 c is 2 a + b is 3How about that?

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.