¿Es posible el patrón de visitante sin estado en C ++?
Pregunta
Estaba tratando de traducir el siguiente código Haskell a C ++:
data List t = Nil | Cons t (List t)
La traducción directa del tipo de datos algebraicos al patrón de visitante sin estado produce el siguiente código Java
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);
}
}
El siguiente es el código C ++ que tengo hasta ahora:
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;
};
Tenga en cuenta que la versión Java usa una función genérica virtual accept
. Cuando lo traduzco a C ++, termino con un plantilla virtual función, que no está permitida por C ++.
¿Hay una solución que no sea hacer? accept
devolver void
¿Y requieren que los visitantes sean condenados?
Actualizar:Según lo solicitado, aquí hay algunos ejemplos de cómo se podrían usar las interfaces (punteros inteligentes de Modulo y posibles errores de compilación):
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));
}
};
Otro ejemplo, una función de nivel superior fold
, en Java, se puede encontrar aquí: http://hpaste.org/54650
Solución
Esto ciertamente se puede mejorar (use consejos inteligentes para la propiedad de la cola, por ejemplo), pero la idea básica:
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);
}
};
Manifestación. No hay necesidad de envío virtual y jerarquías de clase. nullptr
es C ++ 11, pero debería funcionar bien en 03.
Podría ser una mejor idea implementar accept
Como función libre, y no usar punteros nulos como nodo nulo, pero como dije, eso es lo básico.
NOTA: Esta es más o menos la idea detrás Boost :: static_visitor.
Una versión completa de C ++ 11. Variante (necesita alias de plantilla). No probado, porque no tengo G ++ 4.7 cerca.
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);
};