Эквивалент экзистенциальной квантификации в С++?

Ответ 1

template<class K, class T>
struct NodeView {
  virtual NodeView const* left() const = 0;
  virtual NodeView const* right() const = 0;
  virtual K const& key() const = 0;
  virtual T const& value() const = 0;
private:
  ~NodeView() {} // no deleting it!
};

это интерфейс.

Пусть ваши узлы дерева реализуют этот интерфейс. Им разрешено и рекомендуется возвращать nullptr, когда у них нет ребенка с одной стороны или другого.

В базовой структуре возьмите корень node в качестве параметра шаблона. Убедитесь, что он черный с использованием шаблона tomfoolery.

Используйте make_shared для сохранения в std::shared_ptr

auto tree = std::make_shared<std::decay_t<decltype(tree)>>(decltype(tree)(tree));
std::shared_ptr<NodeView const> m_tree = std::move(tree);

Где член m_tree является членом вашей корневой структуры управления.

Теперь у вас есть доступ только для чтения к родовому дереву. Он гарантированно будет сбалансированным красно-черным деревом во время компиляции кодом, который его хранит. Во время выполнения просто гарантировано быть деревом.

В интерфейс, который я написал выше, вы могли бы утечка большей информации о гарантии, но это загромождает интерфейс, выходящий за пределы того, что обычно требуется знать читателю. (например, имеют разные типы Red и Black node).

Теперь, если тело одной короткой функции слишком доверчиво, и вы скорее доверяете стене кода шаблона, мы можем это сделать:

template<template<class...>class Test, class T>
struct restricted_shared_ptr {
  template<class U,
    std::enable_if_t< Test<U>{}, int> = 0
  >
  restricted_shared_ptr( std::shared_ptr<U> pin ):ptr(std::move(pin)) {}
  restricted_shared_ptr(restricted_shared_ptr const&)=default;
  restricted_shared_ptr(restricted_shared_ptr &&)=default;
  restricted_shared_ptr& operator=(restricted_shared_ptr const&)=default;
  restricted_shared_ptr& operator=(restricted_shared_ptr &&)=default;
  restricted_shared_ptr() = default;
  T* get() const { return ptr.get(); }
  explicit operator bool() const { return (bool)ptr; }
  T& operator*() const { return *ptr.get(); }
  T* operator->() const { return ptr.get(); }
private:
  std::shared_ptr<T> ptr;
};

Теперь мы просто напишем произвольную проверку шаблона, в которой говорится: "Это достаточно хорошо, чтобы удовлетворить меня".

И сохраните restricted_shared_ptr< MyCheck, NodeView<K,T> const >. Невозможно сохранить тип типа внутри этого общего указателя, который не пропускает MyCheck без поведения undefined.

Здесь вам нужно доверять конструктору MyCheck, чтобы делать то, что он говорит.

template<class T>
struct IsBlackNode:std::false_type{};

template<class K, class V, std::size_t Height, class Left, class Right>
struct IsBlackNode< BlackNode<K, V, Height, Left, Right> >:std::true_type{};

что является обязательным условием для прохождения только BlackNode.

Итак, restricted_shared_ptr< IsBlackNode, NodeView<K, T> const > является общим указателем на то, что проходит тест IsBlackNode и реализует интерфейс NodeView<K,T>.

Ответ 2

Примечание

Ответ Yakk более идиоматический С++ - этот ответ показывает, как писать (или, по крайней мере, начинать писать) нечто более похожее на версию Haskell.

Когда вы видите, сколько С++ требуется для эмуляции Haskell, вы можете вместо этого использовать собственные идиомы.

TL;DR

большинство ваших инвариантов Haskell (и свойств) на самом деле не выражаются статически в типе вообще, а в коде (runtime) различных конструкторов. Система типов помогает, гарантируя, что один из тех конструкторов действительно работает, и отслеживает, какой из них был предназначен для сопоставления с шаблоном.

IIUC, ваш тип Haskell Node не имеет четырех параметров типа, но два:

data Node (color :: Color) (height :: Nat) key value where

фиксирует типы цвета и высоты - только типы ключей и значений не определены. Все четыре записи, но две из этих записей имеют фиксированные типы.

Итак, ближайший простой перевод будет

template <typename Key, typename Value>
struct Node {
    Color color_;
    size_t height_;
    Key key_;
    Value val_;
};

В сложной части нет прямой поддержки для ваших разных конструкторов - информация о времени выполнения Haskell для вас.

Итак, a Leaf является Node, конструктор которого инициализировал поля цвета и высоты для вас, но используемый конструктор также отслеживается как часть созданного объекта.

Ближайший эквивалент этого и сопоставление с шаблоном, которое он дает вам, будет вариантом типа Boost.Variant, дающим вам что-то как:

// underlying record storage
template <typename Key, typename Value>
struct NodeBase {
    Color color_;
    size_t height_;
    Key key_;
    Value val_;
};

template <typename Key, typename Value>
struct Leaf: public NodeBase<Key,Value> {
    Leaf(Key k, Value v) : NodeBase{Color::Black, 0, k, v} {}
    // default other ctors here
};
// similarly for your BlackBranch and RedBranch constructors

template <typename Key, typename Value>
using Node = boost::variant<Leaf<Key,Value>,
                            RedBranch<Key,Value>,
                            BlackBranch<Key,Value>>;

еще раз отметим, что в вашем типе Branch есть записи для leftColor, rightColor, childHeight и что только параметры типа и значения создают тип.

Наконец, если вы используете сопоставление шаблонов для записи функции на разных конструкторах Node в Haskell, вы должны использовать

template <typename Key, typename Value>
struct myNodeFunction {
    void operator() (Leaf &l) {
        // use l.key_, l.value_, confirm l.height_==0, etc.
    }
    void operator() (RedBranch &rb) {
        // use rb.key_, rb.value_, confirm rb.color_==Color::Red, etc.
    }
    void operator() (BlackBranch &bb) {
        // you get the idea
    }
};

и примените его как:

boost::apply_visitor(myNodeFunction<K,V>(), myNode);

или, если вы используете этот шаблон много, вы можете его обернуть как

template <typename Key, typename Value,
          template Visitor<typename,typename> >
void apply(Node<Key,Value> &node)
{
    boost::apply_visitor(Visitor<Key,Value>{}, node);
}