#include <functional>
#include <utility>
#include <vector>
#include <algorithm>
#include <iostream>
template<template<class ...> class M>
struct Monad {
// return :: a -> m a
template<typename T>
static auto ret(T a) -> M<T>;
// bind :: m a -> (a -> m b) -> m b
template<typename T, typename U>
static auto bind(M<T>, std::function<M<U>(T)>) -> M<U>;
};
// return :: a -> m a
template<template<class...> class M, typename T>
auto ret(T a) -> M<T>
{
return Monad<M>::ret(std::move(a));
}
// (>>=) :: m a -> (a -> m b) -> m b
template<template<class...> class M, typename T, typename F>
auto operator >>= (M<T> ma, F fun) -> decltype(fun(std::declval<T>())) // запутанно, но не знаю, как сделать лучше, чтобы работали лямбды
{
using R = decltype(fun(std::declval<T>()));
return Monad<M>::bind(ma, std::function<R(T)>(std::move(fun)));
}
// (>>) :: m a -> m b -> m b
template<template<class...> class M, typename T, typename U>
auto operator >> (M<T> ma, M<U> mb) -> M<U>
{
return ma >>= [=](T){ return mb; };
}
template<typename T>
struct list : private std::vector<T> {
using impl = std::vector<T>;
using impl::value_type;
list() = default;
list(std::initializer_list<T> il)
: std::vector<T>(std::move(il))
{
}
using impl::push_back;
using impl::insert;
using impl::begin;
using impl::end;
};
template<typename T>
auto mk_list(std::initializer_list<T> il) -> list<T>
{
return list<T>(il);
}
template<>
template<typename T>
auto Monad<list>::ret(T a) -> list<T>
{
// заворачиваем объект в список
return list<T>{a};
}
template<>
template<typename T, typename U>
auto Monad<list>::bind(list<T> ma, std::function<list<U>(T)> f) -> list<U>
{
// формируем список списков путем применения к каждому элементу переданной функции
// (которая принимает объект, а возвращает монаду(список))
list<list<U> > tmp;
std::transform(ma.begin(), ma.end(), std::back_inserter(tmp), f);
// конкатенируем списки в один
list<U> res;
for (auto & v : tmp) {
res.insert(res.end(), v.begin(), v.end());
}
return res;
}
template<typename T, typename U>
std::ostream & operator << (std::ostream & os, std::pair<T,U> p)
{
os << "(" << p.first << "," << p.second << ")";
return os;
}
template<typename T>
std::ostream & operator << (std::ostream & os, const list<T> & a)
{
os << "[";
int i = 0;
for (auto & e : a) {
if (i++) os << ",";
os << e;
}
os << "]";
return os;
}
int main()
{
auto res = mk_list({1, 2, 3}) >>= [](auto x) {
return mk_list({4, 5, 6}) >>= [=](auto y) {
return ret<list>(std::make_pair(x, y));
};
};
std::cout << res << std::endl;
}
I2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aW9zdHJlYW0+Cgp0ZW1wbGF0ZTx0ZW1wbGF0ZTxjbGFzcyAuLi4+IGNsYXNzIE0+CnN0cnVjdCBNb25hZCB7CiAgICAvLyByZXR1cm4gOjogYSAtPiBtIGEKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQ+CiAgICBzdGF0aWMgYXV0byByZXQoVCBhKSAtPiBNPFQ+OwogCiAgICAvLyBiaW5kIDo6IG0gYSAtPiAoYSAtPiBtIGIpIC0+IG0gYgogICAgdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgVT4KICAgIHN0YXRpYyBhdXRvIGJpbmQoTTxUPiwgc3RkOjpmdW5jdGlvbjxNPFU+KFQpPikgLT4gTTxVPjsKfTsKIAovLyByZXR1cm4gOjogYSAtPiBtIGEKdGVtcGxhdGU8dGVtcGxhdGU8Y2xhc3MuLi4+IGNsYXNzIE0sIHR5cGVuYW1lIFQ+CmF1dG8gcmV0KFQgYSkgLT4gTTxUPgp7CiAgICByZXR1cm4gTW9uYWQ8TT46OnJldChzdGQ6Om1vdmUoYSkpOwp9CiAKLy8gKD4+PSkgOjogbSBhIC0+IChhIC0+IG0gYikgLT4gbSBiCnRlbXBsYXRlPHRlbXBsYXRlPGNsYXNzLi4uPiBjbGFzcyBNLCB0eXBlbmFtZSBULCB0eXBlbmFtZSBGPgphdXRvIG9wZXJhdG9yID4+PSAoTTxUPiBtYSwgRiBmdW4pIC0+IGRlY2x0eXBlKGZ1bihzdGQ6OmRlY2x2YWw8VD4oKSkpICAvLyDQt9Cw0L/Rg9GC0LDQvdC90L4sINC90L4g0L3QtSDQt9C90LDRjiwg0LrQsNC6INGB0LTQtdC70LDRgtGMINC70YPRh9GI0LUsINGH0YLQvtCx0Ysg0YDQsNCx0L7RgtCw0LvQuCDQu9GP0LzQsdC00YsKewogICAgdXNpbmcgUiA9IGRlY2x0eXBlKGZ1bihzdGQ6OmRlY2x2YWw8VD4oKSkpOwogICAgcmV0dXJuIE1vbmFkPE0+OjpiaW5kKG1hLCBzdGQ6OmZ1bmN0aW9uPFIoVCk+KHN0ZDo6bW92ZShmdW4pKSk7Cn0KIAovLyAoPj4pIDo6IG0gYSAtPiBtIGIgLT4gbSBiCnRlbXBsYXRlPHRlbXBsYXRlPGNsYXNzLi4uPiBjbGFzcyBNLCB0eXBlbmFtZSBULCB0eXBlbmFtZSBVPgphdXRvIG9wZXJhdG9yID4+IChNPFQ+IG1hLCBNPFU+IG1iKSAtPiBNPFU+CnsKICAgIHJldHVybiBtYSA+Pj0gWz1dKFQpeyByZXR1cm4gbWI7IH07Cn0KCnRlbXBsYXRlPHR5cGVuYW1lIFQ+CnN0cnVjdCBsaXN0IDogcHJpdmF0ZSBzdGQ6OnZlY3RvcjxUPiB7Cgl1c2luZyBpbXBsID0gc3RkOjp2ZWN0b3I8VD47Cgl1c2luZyBpbXBsOjp2YWx1ZV90eXBlOwoKCWxpc3QoKSA9IGRlZmF1bHQ7CglsaXN0KHN0ZDo6aW5pdGlhbGl6ZXJfbGlzdDxUPiBpbCkKCQk6IHN0ZDo6dmVjdG9yPFQ+KHN0ZDo6bW92ZShpbCkpCiAgICB7Cgl9CgoJdXNpbmcgaW1wbDo6cHVzaF9iYWNrOwoJdXNpbmcgaW1wbDo6aW5zZXJ0OwoJdXNpbmcgaW1wbDo6YmVnaW47Cgl1c2luZyBpbXBsOjplbmQ7Cn07Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgphdXRvIG1rX2xpc3Qoc3RkOjppbml0aWFsaXplcl9saXN0PFQ+IGlsKSAtPiBsaXN0PFQ+CnsKCXJldHVybiBsaXN0PFQ+KGlsKTsKfQoKdGVtcGxhdGU8Pgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgphdXRvIE1vbmFkPGxpc3Q+OjpyZXQoVCBhKSAtPiBsaXN0PFQ+CnsKCS8vINC30LDQstC+0YDQsNGH0LjQstCw0LXQvCDQvtCx0YrQtdC60YIg0LIg0YHQv9C40YHQvtC6CglyZXR1cm4gbGlzdDxUPnthfTsKfQoKdGVtcGxhdGU8Pgp0ZW1wbGF0ZTx0eXBlbmFtZSBULCB0eXBlbmFtZSBVPgphdXRvIE1vbmFkPGxpc3Q+OjpiaW5kKGxpc3Q8VD4gbWEsIHN0ZDo6ZnVuY3Rpb248bGlzdDxVPihUKT4gZikgLT4gbGlzdDxVPgp7CgkvLyDRhNC+0YDQvNC40YDRg9C10Lwg0YHQv9C40YHQvtC6INGB0L/QuNGB0LrQvtCyINC/0YPRgtC10Lwg0L/RgNC40LzQtdC90LXQvdC40Y8g0Log0LrQsNC20LTQvtC80YMg0Y3Qu9C10LzQtdC90YLRgyDQv9C10YDQtdC00LDQvdC90L7QuSDRhNGD0L3QutGG0LjQuAoJLy8gKNC60L7RgtC+0YDQsNGPINC/0YDQuNC90LjQvNCw0LXRgiDQvtCx0YrQtdC60YIsINCwINCy0L7Qt9Cy0YDQsNGJ0LDQtdGCINC80L7QvdCw0LTRgyjRgdC/0LjRgdC+0LopKQoJbGlzdDxsaXN0PFU+ID4gdG1wOwoJc3RkOjp0cmFuc2Zvcm0obWEuYmVnaW4oKSwgbWEuZW5kKCksIHN0ZDo6YmFja19pbnNlcnRlcih0bXApLCBmKTsKCgkvLyDQutC+0L3QutCw0YLQtdC90LjRgNGD0LXQvCDRgdC/0LjRgdC60Lgg0LIg0L7QtNC40L0KCWxpc3Q8VT4gcmVzOwoJZm9yIChhdXRvICYgdiA6IHRtcCkgewoJCXJlcy5pbnNlcnQocmVzLmVuZCgpLCB2LmJlZ2luKCksIHYuZW5kKCkpOwoJfQoJcmV0dXJuIHJlczsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgVT4Kc3RkOjpvc3RyZWFtICYgb3BlcmF0b3IgPDwgKHN0ZDo6b3N0cmVhbSAmIG9zLCBzdGQ6OnBhaXI8VCxVPiBwKQp7CglvcyA8PCAiKCIgPDwgcC5maXJzdCA8PCAiLCIgPDwgcC5zZWNvbmQgPDwgIikiOwoJcmV0dXJuIG9zOwp9CiAKdGVtcGxhdGU8dHlwZW5hbWUgVD4Kc3RkOjpvc3RyZWFtICYgb3BlcmF0b3IgPDwgKHN0ZDo6b3N0cmVhbSAmIG9zLCBjb25zdCBsaXN0PFQ+ICYgYSkKewoJb3MgPDwgIlsiOwoJaW50IGkgPSAwOwoJZm9yIChhdXRvICYgZSA6IGEpIHsKCQlpZiAoaSsrKSBvcyA8PCAiLCI7CgkJb3MgPDwgZTsKCX0KCW9zIDw8ICJdIjsKCXJldHVybiBvczsKfQoKaW50IG1haW4oKQp7CglhdXRvIHJlcyA9IG1rX2xpc3QoezEsIDIsIDN9KSA+Pj0gW10oYXV0byB4KSB7CgkJcmV0dXJuIG1rX2xpc3QoezQsIDUsIDZ9KSA+Pj0gWz1dKGF1dG8geSkgewoJCQlyZXR1cm4gcmV0PGxpc3Q+KHN0ZDo6bWFrZV9wYWlyKHgsIHkpKTsKCQl9OwoJfTsKCXN0ZDo6Y291dCA8PCByZXMgPDwgc3RkOjplbmRsOwp9Cg==
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]