Возможен ли шаблон посетителей без состояния в C ++? - PullRequest
Новая
       11

Возможен ли шаблон посетителей без состояния в C ++?

11 голосов
/ 29 ноября 2011

Я пытался перевести следующий код на Haskell в C ++: 

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

Простое преобразование алгебраического типа данных в шаблон Visitor без сохранения состояния приводит к следующему 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);
  }
}

Ниже приведен код C ++, который у меня имеется: 

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;
};

Обратите внимание, что в версии Java используется виртуальная универсальная функция accept.Когда я перевожу его на C ++, я получаю функцию virtual template , которая не разрешена в C ++.

Есть ли какое-то решение, отличное от accept return void и требуют, чтобы посетители были с состоянием?

Обновление: По запросу, вот несколько примеров того, как можно использовать интерфейсы (умные указатели по модулю и возможные ошибки компиляции): 

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));
  }
};

Другой пример, высокоуровневая функция fold в Java, можно найти здесь: http://hpaste.org/54650

1 Ответ

13 голосов
/ 29 ноября 2011

Это, безусловно, можно улучшить (например, использовать умные указатели для владения хвостом), но основная идея: 

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);
     }
};

Демо . Нет необходимости в виртуальной диспетчеризации и иерархиях классов. nullptr - это C ++ 11, но он должен отлично работать на 03.

Может быть, лучше реализовать accept как свободную функцию, а не использовать нулевые указатели в качестве nil-узла, но, как я уже сказал, это основная вещь.

Примечание: это более или менее идея, лежащая в основе boost :: static_visitor .

Полная версия C ++ 11 Boost.Variant (требуются псевдонимы шаблона). Не проверено, потому что у меня нет g ++ 4.7 поблизости. 

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);
};
...