Есть ли название для этой идиомы создания кортежей?

#include <iostream>

auto list = [](auto ...xs) {
return [=](auto access) { return access(xs...); };
};

auto length = [](auto xs) {
return xs([](auto ...z) { return sizeof...(z); });
};

int main()
{
std::cout << length(list(1, '2', "3")); // 3
}

auto list = []( auto... xs )
{
return [=]( auto access ) { return access(xs...); };
};

auto pack_size = [](auto... xs ) { return sizeof...(xs); };

auto bind = []( auto xs , auto op )
{
return xs(op);
};

auto result = bind(list(1,'2',"3"), pack_size);

Я бы назвал это идиомой Кортеж-продолжатель или, в общем, монадический-продолжатель. Это, безусловно, пример продолжения монады. Отличным введением для продолжения монады для программистов на C ++ является Вот. По сути, list Лямбда, приведенная выше, принимает значение (пакет с переменными параметрами) и возвращает простой «продолжатель» (внутреннее замыкание). Этот продолжатель, когда дан вызываемый (называется access), передает пакет параметров в него и возвращает все, что возвращает вызываемый объект.

Заимствуя из блога FPComplete, продолжатель более или менее похож на следующее.

template<class R, class A>
struct Continuator {
virtual ~Continuator() {}
virtual R andThen(function<R(A)> access) = 0;
};

Continuator выше является абстрактным — не обеспечивает реализацию. Итак, вот простой.

template<class R, class A>
struct SimpleContinuator : Continuator<R, A> {
SimpleContinuator (A x) : _x(x) {}
R andThen(function<R(A)> access) {
return access(_x);
}
A _x;
};

SimpleContinuator принимает одно значение типа A и передает это access когда andThen называется. list лямбда выше по сути такая же. Это более общее. Вместо одного значения внутреннее замыкание захватывает пакет параметров и передает его access функция. Ухоженная!

Надеюсь, это объясняет, что значит быть продолжателем. но что значит быть монадой? Вот хороший вступление используя картинки.

я думаю list Лямбда также является монадой списка, которая реализована как монада продолжения. Обратите внимание, что продолжение монада — мать всех монад. Т.е., вы можете реализовать любую монаду с продолжением монады. Конечно, список монада не вне досягаемости.

Поскольку пакет параметров вполне естественно является «списком» (часто разнородного типа), имеет смысл для него работать как монада списка / последовательности. list Выше лямбда — очень интересный способ преобразования пакетов параметров C ++ в монадическую структуру. Следовательно, операции могут быть связаны друг с другом.

length Однако лямбда выше немного разочаровывает, потому что она разбивает монаду, а вложенная лямбда внутри просто возвращает целое число. Возможно, есть лучший способ написать длину ‘getter’, как показано ниже.

—-Функтор—-

Прежде чем мы сможем сказать, что список лямбда — это монада, мы должны показать, что это функтор. То есть, fmap должен быть записан для списка.

Список лямбда выше служит создателем функтора из пакета параметров — по сути, он служит return, Этот созданный функтор хранит пакет параметров при себе (перехват) и обеспечивает «доступ» к нему при условии, что вы даете вызываемую функцию, которая принимает переменное число аргументов. Обратите внимание, что вызываемый объект называется ТОЛЬКО ОДИН РАЗ.

Давайте напишем fmap для такого функтора.

auto fmap = [](auto func) {
return [=](auto ...z) { return list(func(z)...); };
};

Тип функции должен быть (a -> b). То есть, на C ++ говорят,

template <class a, class b>
b func(a);

Тип fmap это fmap: (a -> b) -> list[a] -> list[b] То есть, на C ++ говорят,

template <class a, class b, class Func>
list<b> fmap(Func, list<a>);

То есть, fmap просто отображает list-of-a в list-of-b.

Теперь вы можете сделать

auto twice = [](auto i) { return 2*i; };
auto print = [](auto i) { std::cout << i << " "; return i;};
list(1, 2, 3, 4)
(fmap(twice))
(fmap(print)); // prints 2 4 6 8 on clang (g++ in reverse)

Поэтому это функтор.

—-Монада —-

Теперь давайте попробуем написать flatmap (А.к.а. bind, selectmany)

Тип плоской карты flatmap: (a -> list[b]) -> list[a] -> list[b].

То есть, учитывая функцию, которая отображает a на list-of-b и list-of-a, flatmap возвращает list-of-b. По сути, он берет каждый элемент из list-of-a, вызывает для него func, получает (потенциально пустой) list-of-b один за другим, затем объединяет все list-of-b и, наконец, возвращает окончательный список -of-б.

Вот реализация flatmap для списка.

auto concat = [](auto l1, auto l2) {
auto access1 = [=](auto... p) {
auto access2 = [=](auto... q) {
return list(p..., q...);
};
return l2(access2);
};
return l1(access1);
};

template <class Func>
auto flatten(Func)
{
return list();
}

template <class Func, class A>
auto flatten(Func f, A a)
{
return f(a);
}

template <class Func, class A, class... B>
auto flatten(Func f, A a, B... b)
{
return concat(f(a), flatten(f, b...));
}

auto flatmap = [](auto func) {
return [func](auto... a) { return flatten(func, a...); };
};

Теперь вы можете сделать много полезных вещей с помощью списка. Например,

auto pair  = [](auto i) { return list(-i, i); };
auto count = [](auto... a) { return list(sizeof...(a)); };
list(10, 20, 30)
(flatmap(pair))
(count)
(fmap(print)); // prints 6.

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

auto len = [](auto ...z) { return sizeof...(z); };
std::cout << list(10, 20, 30)
(flatmap(pair))
(len);

Если все сделано правильно, то коллекторный трубопровод шаблон (например, filter, reduce) теперь можно применять к пакетам параметров C ++. Милая!

—-Законы Монады —-

Давайте удостоверимся, что list монада удовлетворяет всем трем законы монады.

auto to_vector = [](auto... a) { return std::vector<int> { a... }; };

auto M = list(11);
std::cout << "Monad law (left identity)\n";
assert(M(flatmap(pair))(to_vector) == pair(11)(to_vector));

std::cout << "Monad law (right identity)\n";
assert(M(flatmap(list))(to_vector) == M(to_vector));

std::cout << "Monad law (associativity)\n";
assert(M(flatmap(pair))(flatmap(pair))(to_vector) ==
M(flatmap([=](auto x) { return pair(x)(flatmap(pair)); }))(to_vector));

Все утверждения удовлетворены.

—-Сборный трубопровод —-

Хотя вышеприведенная «лямбда-список», как утверждается, является монадой и обладает характеристиками общеизвестной «монады-списка», она довольно неприятна. Тем более, что поведение общего коллекторный трубопровод комбинаторы, такие как filter (a.k.a where) не соответствует общим ожиданиям.

Причина в том, как работают C ++ лямбды. Каждое лямбда-выражение создает функциональный объект уникального типа. Следовательно, list(1,2,3) производит тип, который не имеет ничего общего с list(1) и пустой список, который в этом случае будет list(),

Прямая реализация where компиляция не удалась, потому что в C ++ функция не может возвращать два разных типа.

auto where_broken = [](auto func) {
return flatmap([func](auto i) {
return func(i)? list(i) : list(); // broken :-(
});
};

В приведенной выше реализации func возвращает логическое значение. Это предикат, который говорит true или false для каждого элемента. Оператор?: Не компилируется.

Таким образом, можно использовать другой прием для продолжения конвейера сбора. Вместо того, чтобы фактически фильтровать элементы, они просто помечаются как таковые — и это делает его неприятным.

auto where_unpleasant = [](auto func) {
return [=](auto... i) {
return list(std::make_pair(func(i), i)...);
};
};

where_unpleasant выполняет свою работу, но неприятно …

Например, так вы можете фильтровать отрицательные элементы.

auto positive = [](auto i) { return i >= 0; };
auto pair_print = [](auto pair) {
if(pair.first)
std::cout << pair.second << " ";
return pair;
};
list(10, 20)
(flatmap(pair))
(where_unpleasant(positive))
(fmap(pair_print)); // prints 10 and 20 in some order

—-Гетерогенные кортежи —-

Пока что речь шла об однородных кортежах. Теперь давайте обобщим это на истинные кортежи. Тем не мение, fmap, flatmap, where принять только один обратный вызов лямбда. Чтобы обеспечить несколько лямбд, каждая из которых работает с одним типом, мы можем перегрузить их. Например,

template <class A, class... B>
struct overload : overload<A>, overload<B...> {
overload(A a, B... b)
: overload<A>(a), overload<B...>(b...)
{}
using overload<A>::operator ();
using overload<B...>::operator ();
};

template <class A>
struct overload<A> : A{
overload(A a)
: A(a) {}
using A::operator();
};

template <class... F>
auto make_overload(F... f) {
return overload<F...>(f...);
}

auto test =
make_overload([](int i) { std::cout << "int = " << i << std::endl; },
[](double d) { std::cout << "double = " << d << std::endl; });
test(10); // int
test(9.99); // double

Давайте использовать перегруженную лямбда-технику для обработки разнородного продолжателя кортежа.

auto int_or_string =
make_overload([](int i) { return 5*i; },
[](std::string s) { return s+s; });
list(10, "20")
(fmap(int_or_string))
(fmap(print)); // prints 2020 and 50 in some order

В заключение, Живой пример

Это выглядит как форма продолжение прохождения стиля.

Грубая идея CPS заключается в следующем: вместо того, чтобы иметь функцию (скажем, f) вернуть какое-то значение, которое вы даете f другой аргумент, который является функцией, называется продолжение. Затем, f вызывает это продолжение с возвращаемым значением вместо возврата. Давайте возьмем пример:

int f (int x) { return x + 42; }

становится

void f (int x, auto cont) { cont (x + 42); }

Вызов является хвостовым вызовом и может быть оптимизирован в переход (именно поэтому TCO является обязательным в некоторых языках, таких как Scheme, семантика которых зависит от некоторой формы преобразования в CPS).

Другой пример:

void get_int (auto cont) { cont (10); }
void print_int (int x) { printf ("%d", x), }

Теперь вы можете сделать get_int (std::bind (f, _1, print_int)) на печать 54. Обратите внимание, что все продолжающиеся вызовы всегда хвостовые звонки (вызов printf это также продолжение звонка).

Хорошо известный пример — асинхронные обратные вызовы (например, вызовы AJAX в javascript): вы передаете продолжение подпрограмме, выполняющейся параллельно.

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