функциональное программирование — интерфейс Monad в Stack Overflow

auto foo(const int x) const -> std::string;

auto bar() const -> const *Monad<int>;

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

Например. в Хаскеле вы бы 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 (но, к сожалению, он ассоциативно-правый — ну, хорошо).

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

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

Во-первых, нам нужен способ выяснить, существует ли на самом деле конструктор, который принимает произвольный тип. Мы можем приблизить это, проверяя это для данного конструктора типа 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
= declval(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's 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 Монада в смысле концепции, определенной выше.

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

Большим преимуществом монад является то, что с монадическим интерфейсом можно многое сделать. Например, мы знаем, что каждая монада также является аппликативной, поэтому мы можем написать 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 Вы можете найти версию, которая также имеет поддержку карри, но синтаксис еще хуже.

А для заинтересованных, вот coliru.

РЕДАКТИРОВАТЬ: я только заметил, что я был неправ в отношении того, что компилятор не может вывести Monad = std::vector а также T = int когда предоставляется аргумент типа std::vector<int>, Это означает, что вы действительно можете иметь единый синтаксис для отображения функции в произвольном контейнере с fmapт.е.

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

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

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

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

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