Интерфейс Monad в С++

Ответ 1

Прежде всего обратите внимание, что быть монадой - это не свойство типа, а конструктор типа.

Например. в Haskell у вас будет List a в качестве типа и List в качестве конструктора типа. В C++ у нас такая же функциональность с шаблонами: std::list - это конструктор типов, который может конструировать тип std::list<int>. Здесь List - это монада, а List Bool - нет.

Чтобы конструктор типов M был монадическим, ему необходимо предоставить две специальные функции:

1. Функция, которая выводит произвольные значения некоторого типа T в монаду, то есть функцию типа T -> M<T>. Эта функция называется return в Хаскеле.
2. Функция (в Haskell, называемая bind) типа M<T> ->(T -> M<T'>) -> M<T'>, то есть функция, которая принимает объект типа M<T> и функцию типа T -> M<T'> и применяет функцию аргумента к объектам T, заключенным внутри аргумент M<T>.

Есть также некоторые свойства, которые эти две функции должны выполнять, но поскольку семантические свойства не могут быть проверены во время компиляции (ни в Haskell, ни в C++), нам не нужно заботиться о них здесь.

Однако мы можем проверить существование и типы этих двух функций, как только мы определились с синтаксисом/именами для них. Для первого очевидным выбором является конструктор, который принимает ровно один элемент любого данного типа T. Для второго я решил пойти с operator>>=, так как хотел, чтобы он был оператором, чтобы избежать вызовов вложенных функций, и он похож на нотацию Haskell (но, к сожалению, это ассоциативно справа - да ладно).

Проверка монадического интерфейса

Так как же проверить свойства шаблона? К счастью, в C++ есть аргументы шаблона-шаблона и SFINAE.

Во-первых, нам нужен способ выяснить, существует ли на самом деле конструктор, который принимает произвольный тип. Мы можем приблизить это, проверив, что для данного конструктора типа M тип M<DummyType> правильно сформирован для фиктивного типа struct DummyType{};, который мы определяем. Таким образом, мы можем убедиться, что не может быть специализации для типа, с которым мы проверяем.

Для bind мы делаем то же самое: проверяем, что существует operator>>=(M<DummyType> const&, M<DummyType2>(*)(DummyType)) и что возвращаемый тип действительно M<DummyType2>.

Проверить, что функция существует, можно с помощью C++ 17s std::void_t (я настоятельно рекомендую выступление Уолтера Браунса на CppCon 2014, где он представляет эту технику). Проверить правильность типов можно с помощью std::is_same.

Все вместе это может выглядеть примерно так:

// declare the two dummy types we need for detecting constructor and bind
struct DummyType{};
struct DummyType2{};

// returns the return type of the constructor call with a single 
// object of type T if such a constructor exists and nothing 
// otherwise. Here 'Monad' is a fixed type constructor.
template <template<typename, typename...> class Monad, typename T>
using constructor_return_t
    = decltype(Monad<T>{std::declval<T>()});

// returns the return type of operator>>=(const Monad<T>&, Monad<T'>(*)(T))
// if such an operator is defined and nothing otherwise. Here Monad 
// is a fixed type constructor and T and funcType are arbitrary types.
template <template <typename, typename...> class Monad, typename T, typename T'>
using monadic_bind_t
    = decltype(std::declval<Monad<T> const&>() >>= std::declval<Monad<T'>(*)(T)>());

// logical 'and' for std::true_type and it children
template <typename, typename, typename = void>
struct type_and : std::false_type{};
template<typename T, typename T2>
struct type_and<T, T2, std::enable_if_t<std::is_base_of<std::true_type, T>::value && std::is_base_of<std::true_type, T2>::value>> 
    : std::true_type{};


// the actual check that our type constructor indeed satisfies our concept
template <template <typename, typename...> class, typename = void>
struct is_monad : std::false_type {};

template <template <typename, typename...> class Monad>
struct is_monad<Monad, 
                void_t<constructor_return_t<Monad, DummyType>,
                       monadic_bind_t<Monad, DummyType, DummyType2>>>
    : type_and<std::is_same<monadic_bind_t<Monad, DummyType, DummyType2>,
                            Monad<DummyType2>>,
               std::is_same<constructor_return_t<Monad, DummyType>,
                            Monad<DummyType>>> {};

Обратите внимание, что хотя мы обычно ожидаем, что конструктор типов будет принимать один тип T в качестве аргумента, я использовал параметр шаблона шаблона с переменным числом аргументов для учета распределителей по умолчанию, обычно используемых в контейнерах STL. Без этого вы не могли бы сделать std::vector монадой в смысле концепции, определенной выше.

Использование свойства типа для реализации универсальных функций на основе монадического интерфейса

Большим преимуществом монад является то, что с монадическим интерфейсом можно многое сделать. Например, мы знаем, что каждая монада также является аппликативной, поэтому мы можем написать функцию Haskell ap и использовать ее для реализации liftM, которая позволяет применять любую обычную функцию к монадическому значению.

// ap
template <template <typename, typename...> class Monad, typename T, typename funcType>
auto ap(const Monad<funcType>& wrappedFn, const Monad<T>& x) {
    static_assert(is_monad<Monad>{}(), "");
    return wrappedFn >>= [x] (auto&& x1) { return x >>= [x1 = std::forward<decltype(x1)>(x1)] (auto&& x2) {
        return Monad<decltype(std::declval<funcType>()(std::declval<T>()))> { x1 (std::forward<decltype(x2)>(x2)) }; }; };
}

// convenience function to lift arbitrary values into the monad, i.e.
// just a wrapper for the constructor that takes a single argument.
template <template <typename, typename...> class Monad, typename T>
Monad<std::remove_const_t<std::remove_reference_t<T>>> pure(T&& val) {
    static_assert(is_monad<Monad>{}(), "");
    return Monad<std::remove_const_t<std::remove_reference_t<T>>> { std::forward<decltype(val)>(val) };
}

// liftM
template <template <typename, typename...> class Monad, typename funcType>
auto liftM(funcType&& f) {
    static_assert(is_monad<Monad>{}(), "");
    return [_f = std::forward<decltype(f)>(f)] (auto x) {
        return ap(pure<Monad>(_f), x);
    };
}

// fmap
template <template <typename, typename...> class Monad, typename T, typename funcType>
auto fmap(funcType&& f, Monad<T> const& x) {
    static_assert(is_monad<Monad>{}(), "");
    return x >>= ( [_f = std::forward<funcType>(f)] (const T& val) {
        return Monad<decltype(_f(std::declval<T>()))> {_f(val)}; });
}

Давайте посмотрим, как мы можем его использовать, предполагая, что вы уже реализовали operator>>= для std::vector и optional.

// functor similar to std::plus<>, etc.
template <typename T = void>
struct square {
    auto operator()(T&& x) {
        return x * std::forward<decltype(x)>(x);
    }   
};

template <>
struct square<void> {
    template <typename T>
    auto operator()(T&& x) const {
        return x * std::forward<decltype(x)>(x);
    }
};

int main(int, char**) {
    auto vector_empty = std::vector<double>{};
    auto vector_with_values = std::vector<int>{2, 3, 31};
    auto optional_with_value = optional<double>{42.0};
    auto optional_empty = optional<int>{};

    auto v1 = liftM<std::vector>(square<>{})(vector_empty); // still an empty vector
    auto v2 = liftM<std::vector>(square<>{})(vector_with_values); // == vector<int>{4, 9, 961};
    auto o1 = liftM<optional>(square<>{})(optional_empty); // still an empty optional
    auto o2 = liftM<optional>(square<>{})(optional_with_value); // == optional<int>{1764.0};

    std::cout << std::boolalpha << is_monad<std::vector>::value << std::endl; // prints true
    std::cout << std::boolalpha << is_monad<std::list>::value << std::endl; // prints false

}

Ограничения

Хотя это позволяет использовать универсальный способ определения концепции монады и обеспечивает простую реализацию конструкторов монадических типов, существуют некоторые недостатки.

Прежде всего, я не знаю, что есть способ заставить компилятор определить, какой конструктор типа был использован для создания шаблонного типа, то есть я не знаю, как компилятору выяснить, что std::vector Шаблон был использован для создания типа std::vector<int>. Поэтому вы должны вручную добавить имя конструктора типа в вызове к реализации, например, fmap.

Во-вторых, довольно некрасиво писать функции, которые работают с общими монадами, как вы можете видеть с ap и liftM. С другой стороны, они должны быть написаны только один раз. Кроме того, весь подход станет намного легче писать и использовать, как только мы получим концепции (надеюсь, в C++ 2x).

И последнее, но не менее важное: в той форме, в которой я это написал, большинство преимуществ монад Хаскелла непригодны для использования, так как они сильно зависят от карри. Например. в этой реализации вы можете отображать функции только на монады, которые принимают ровно один аргумент. На моем github вы можете найти версию, которая также поддерживает карри, но синтаксис еще хуже.

А для интересующихся вот колирус.

ОБНОВЛЕНИЕ: Я только что заметил, что я был неправ в отношении того факта, что компилятор не может выводить Monad = std::vector и T = int при предоставлении аргумента типа std::vector<int>. Это означает, что у вас действительно может быть унифицированный синтаксис для отображения функции в произвольном контейнере с помощью fmap, т.е.

auto v3 = fmap(square<>{}, v2);
auto o3 = fmap(square<>{}, o2);

компилирует и делает правильные вещи.

Я добавил пример в колиру.

ОБНОВЛЕНИЕ: Использование концепций

Поскольку понятия C++ 20 находятся прямо за углом, а синтаксис в значительной степени окончательный, имеет смысл обновить этот ответ эквивалентным кодом, который использует понятия.

Самая простая вещь, которую вы можете сделать, чтобы заставить эту работу работать с концепциями, - это написать концепцию, охватывающую черту типа is_monad.

template<template<typename, typename...> typename T>
concept monad = is_monad<T>::value;

Тем не менее, он также может быть написан как концепция, что делает его немного более понятным.

template<template<typename, typename...> typename Monad>
concept monad = requires {
    std::is_same_v<monadic_bind_t<Monad, DummyType, DummyType2>, Monad<DummyType2>>;
    std::is_same_v<constructor_return_t<Monad, DummyType>, Monad<DummyType>>;
};

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

// fmap
template <monad Monad, typename T, typename funcType>
auto fmap(funcType&& f, Monad<T> const& x) {
    return x >>= ( [_f = std::forward<funcType>(f)] (const T& val) {
        return Monad<decltype(_f(std::declval<T>()))> {_f(val)}; });
}

Ответ 2

Я боюсь, что полиморфизм в стиле Haskell и шаблоны С++ слишком далеки, чтобы прагматически определить монады на С++, таким образом, что он действительно полезен.

Технически вы можете определить monad M как шаблонный шаблон следующей формы (я буду передавать все по значению, чтобы упростить его)

template <typename A>
struct M {
   // ...

   // this provides return :: a -> M a
   M(A a) { .... }

   // this provides (>>=) :: M a -> (a -> M b) -> M b
   template <typename B>
   M<B> bind(std::function< M<B> (A) > f) { ... }

   // this provides flip fmap :: M a -> (a -> b) -> M b
   template <typename B>
   M<B> map(std::function< B (A) > f) { ... }
};

Это может работать (я не эксперт на С++), но я не уверен, можно ли использовать его на С++. Разумеется, это приведет к не идиоматическому коду.

Затем возникает вопрос, как требовать, чтобы класс имел такой интерфейс. Вы можете использовать что-то вроде

template <typename A>
struct M : public Monad<M, A> {
...
};

где

template <template <typename T> M, typename A>
class Monad {
   // this provides return :: a -> M a
   Monad(A a) = 0;

   // this provides (>>=) :: M a -> (a -> M b) -> M b
   template <typename B>
   M<B> bind(std::function< M<B> (A) > f) = 0;

   // this provides flip fmap :: M a -> (a -> b) -> M b
   template <typename B>
   M<B> map(std::function< B (A) > f) = 0;

};

Но, увы,

monads.cpp:31:44: error: templates may not be ‘virtual’
   M<B> bind(std::function< M<B> (A) > f) = 0;

Шаблоны похожи на полиморфные функции, но это другое дело.

Новый подход, который, похоже, работает, но это не так:

template <template <typename T> typename M, typename A>
class Monad {
  // this provides return :: a -> M a
  Monad(A a) = 0;

  // this provides (>>=) :: M a -> (a -> M b) -> M b
  template <typename B>
  M<B> bind(std::function< M<B> (A) > f);

  // this provides flip fmap :: M a -> (a -> b) -> M b
  template <typename B>
  M<B> map(std::function< B (A) > f);

};

// The identity monad, as a basic case
template <typename A>
struct M : public Monad<M, A> {
  A x;
  // ...

  // this provides return :: a -> M a
  M(A a) : x(a) { }

  // this provides (>>=) :: M a -> (a -> M b) -> M b
  template <typename B>
  M<B> bind(std::function< M<B> (A) > f) {
    return f(x);
  }

  // this provides flip fmap :: M a -> (a -> b) -> M b
  template <typename B>
  M<B> map(std::function< B (A) > f) {
      return M(f(x));
  }
};

Однако удаление, например map, из типа M не вызывает ошибку типа. Действительно, ошибки будут генерироваться только во время создания. Шаблоны не являются forall s, снова.

Ответ 3

Я думаю, что самая основная форма этого стиля программирования в С++ - это примерно так:

#include <functional>
#include <cassert>
#include <boost/optional.hpp>

template<typename A>
struct Monad
{
public:
    explicit Monad(boost::optional<A> a) : m(a) {}

    inline bool valid() const { return static_cast<bool>(m); }
    inline const A& data() const {  assert(valid());  return *m;  }
private:
    const boost::optional<A> m;
};

Monad<double> Div(const Monad<double>& ma, const Monad<double>& mb)
{
    if (!ma.valid() || !mb.valid() ||  mb.data() == 0.0)
    {
        return Monad<double>(boost::optional<double>{});
    }
    return Monad<double>(ma.data() / mb.data());

};
int main()
{
    Monad<double> M1(3);
    Monad<double> M2(2);
    Monad<double> M0(0);

    auto MR1 = Div(M1, M2);
    if (MR1.valid())
        std::cout << "3/2 = " << MR1.data() << '\n';

    auto MR2 = Div(M1, M0);
    if (MR2.valid())
        std::cout << "3/0 = " << MR2.data() << '\n';

    return 0;
}