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 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 3
How 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.

Popular Posts