#include <boost/variant.hpp>
#include <iostream>

struct Nil {};
auto nil = Nil{};

template <typename T>
struct Cons;

template <typename T>
using List = boost::variant<Nil, boost::recursive_wrapper<Cons<T>>>;

template <typename T>
struct Cons {
  Cons( T val, List<T> list ) : head( val ), tail( list ) {}
  
  T head;
  List<T> tail;
};

template <typename T>
class length_visitor : public boost::static_visitor<size_t> {
public:
  int operator()( Nil ) const {
    return 0;
  }

  int operator()( const Cons<T>& c ) const {
    return 1 + length( c.tail );
  }
};

template <typename T>
auto cons( T head, List<T> tail ) {
  return List<T>( Cons<T>( head, tail ) );
}

template <typename T>
auto cons( T head, Nil ) {
  return List<T>( Cons<T>( head, List<T>( Nil{} ) ) );
}

template <typename T>
size_t length( const List<T>& list ) {
  return boost::apply_visitor( length_visitor<T>(), list );
}

int main() {

  auto l = cons( 3, cons( 2, cons( 1, nil ) ) );
  std::cout << length( l ) << std::endl;

  return 0;
}