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

В списке рассылки Boost @LouisDionne недавно опубликовал следующий хитрый трюк по созданию сущности, похожей на кортеж:

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

Живой пример.

Хитрость в том, что list это лямбда, принимающая переменный список параметров в качестве входных данных, и возвращающая лямбда в качестве выходных данных, которая будет принимать другую лямбда, чтобы воздействовать на свой ввод. Так же, length является лямбда-выражением, подобным списковому объекту, которому оно будет выдавать переменную sizeof... оператор к исходным входным параметрам списка. sizeof... Оператор обернут внутри лямбды, чтобы его можно было передать list,

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

3 ответа

Решение

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

Монады - это функциональная конструкция программирования, используемая для имитации состояния между различными этапами вычислений (помните, что функциональный язык не имеет состояний).
Монада состоит в том, чтобы связывать различные функции, создавая "конвейер вычислений", где каждый шаг знает о текущем состоянии вычислений.

Монады имеют два основных пилара:

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

В Википедии есть очень хорошие примеры и объяснения по поводу монад.

Позвольте мне переписать данный код C++14:

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

Я думаю, что здесь мы определяем return Функция монады: принимает значение и возвращает его монадическим способом. В частности, этот возврат возвращает функтор (в математическом смысле, а не функтор C++), который переходит из категории "кортеж" в категорию пакета с переменным числом элементов.

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

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

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

А также length только неуниверсальная версия чего-то рядом с монадой bind оператор, оператор, который принимает монадическое значение из предыдущего шага конвейера и обходит его для указанной функции (функция, которая действительно выполняет эту работу). Эта функция является функциональностью, выполняемой на этом этапе вычисления.

Наконец, ваш звонок может быть переписан как:

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

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

Изменить: больше веселья

Просто ради забавы программирования на C++ я продолжил исследовать эту монадоподобную вещь. Вы можете найти несколько примеров здесь.

Я бы назвал этот идиома кортежем-продолжателем или, в более общем смысле, монадическим продолжателем. Это, безусловно, пример продолжения монады. Отличное введение в монаду продолжения для программистов на 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 (ака 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, так что каждый вызов является хвостовым (и тогда вам не нужен стек для запуска программы!).

Другие вопросы по тегам