Is stateless visitor pattern possible in C++?

Question

I was trying to translate the following Haskell code to C++:

data List t = Nil | Cons t (List t)

The straightforward translation of the algebraic data type to the stateless Visitor pattern yields the following Java code

interface List<T> {
  <R> R accept(ListVisitor<T,R> v);
}

interface ListVisitor<T,R> {
  R visitNil();
  R visitCons(T head, List<T> tail);
}

class Nil<T> implements List<T> {
  @Override
  public <R> R accept(ListVisitor<T,R> v) {
    return v.visitNil();
  }
}

class Cons<T> implements List<T> {
  public final T head;
  public final List<T> tail;
  public Cons(T head, List<T> tail) {
    this.head = head;
    this.tail = tail;
  }
  @Override
  public <R> R accept(ListVisitor<T,R> v) {
    return v.visitCons(head, tail);
  }
}

The following is the C++ code I have so far:

template<class T> class List;

template<class T, class R> class ListVisitor {
  virtual R visitNil() = 0;
  virtual R visitCons(T head, List<T> tail) = 0;
};

template<class T> class List {
  template<class R> virtual R accept(ListVisitor<T,R> v) = 0;
};

Note that the Java version uses a virtual generic function accept. When I translate it to C++, I end up with a virtual template function, which is not allowed by C++.

Is there a solution to it other than making accept return void and require visitors to be stateful?

Update: As requested, here are some examples of how the interfaces could be used (modulo smart pointers and possible compile errors):

template<class T> struct LengthVisitor : ListVisitor<T, int> {
  bool visitNil() { return 0; }
  bool visitCons(const T&, const List<T> &tail) { return 1 + tail.accept(*this); }
};

template<class T> struct ConcatVisitor : ListVisitor<T, const List<T> *> {
  const List<T> *right;
  ConcatVisitor(const List<T> *right) : right(right) {} 
  List<T> * visitNil() { return right; }
  List<T> * visitCons(const T &head, const List<T> & tail) {
    return new Cons(head, tail.accept(*this));
  }
};

Another example, a higher-level function fold, in Java, can be found here: http://hpaste.org/54650

Moulden

please, can you add an example of the final usage of the c++ code? – Electrocardiograph

why not use each language as it's meant to be used – Calendra

visitCons and accept methods also need to take a pointer to those abstract classes, rather than a value, so why not stateful? – Krissie

lionbest, they are supposed to take a const &. Alf, do you mean one should be happy using void and mutable visitors? – Moulden

Answer 1

This can certainly be improved (use smart pointers for tail ownership, for example), but the basic idea:

template <typename T>
struct cons_list {
     T head;
     cons_list<T>* tail;

     explicit cons_list(T head, cons_list *tail = nullptr)
         : head(head), tail(tail) {}

     template <template<typename> class Visitor>
     typename Visitor<T>::return_type accept(const Visitor<T>& visitor) {
          return visitor.visit(head, tail);
     }
};

template <typename T>
struct some_visitor {
     typedef void return_type;

     return_type visit(T head, cons_list<T>* tail) const {
          std::cout << head << '\n';
          if (tail != nullptr) tail->accept(*this);
     }
};

Demo. No need for virtual dispatch and class hierarchies. nullptr is C++11, but it should work just fine on 03.

It might be a better idea to implement accept as free function, and not use null pointers as nil node, but as I said, that's the basic thing.

Note: this is more-or-less the idea behind boost::static_visitor.

A full C++11 Boost.Variant version (needs template aliases). Not tested, because I don't have g++ 4.7 nearby.

struct nil_node {};
template <typename T> cons_node;

template <typename T>
using cons_list = boost::make_recursive_variant<
     nil_node, cons_node<T>
>::type;

template <typename T>
struct cons_node {
     T head;
     cons_list<T> tail;

     explicit cons_node(T head, const cons_list<T>& tail)
         : head(head), tail(tail)
     {}
};

template <typename T>
struct some_visitor : boost::static_visitor<T> {
     void operator()(nil_node&) {}
     void operator()(cons_node<T>& node) {
         std::cout << node.head << '\n';
         boost::apply_visitor(node.tail, *this);
     }
};

int main() {
    cons_node<int> x(1, cons_node<int>(2, cons_node<int>(3, nil_node())));
    boost::apply_visitor(some_visitor<int>(), x);
};

Traceetracer

Is my understanding correct, that the boost variant type implements this by abandoning the virtual dispatch, suggested by the usual description of the visitor pattern, in favour of switch on an enum accompanied with static casts? Your first example does not demonstrate that (very important) part because it avoids inheritance altogether by putting everything into a single data structure. – Moulden

@Rotsor: variant is an implementation of a tagged union, like Haskell's data. I don't know implementation details, you can read Boost sources if you want to know them. – Traceetracer