c++ - ¿Hay un nombre para este modismo de creación de tuplas?

tuples variadic-templates

Question

En la lista de correo de Boost , @LouisDionne publicó recientemente el siguiente truco inteligente para crear una entidad similar a una tupla:

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

Ejemplo en vivo

La astucia es que la list es una lambda que toma una lista de parámetros variadica como entrada, y devuelve una lambda como salida que tomará otra lambda para actuar en su entrada. De forma similar, length es una lambda que toma una entidad de tipo lista, a la que suministrará el operador de tamaño variable de sizeof... a los parámetros de entrada originales de la lista. El operador sizeof... está envuelto dentro de una lambda para poder pasarlo a la list .

Pregunta : ¿hay un nombre para este modismo de creación de tuplas? Tal vez desde un lenguaje de programación funcional donde las funciones de orden superior se usan más comúnmente.

Answer 1

Creo que esta es una implementación sutil de algo parecido a una mónada, específicamente algo en el mismo espíritu de la mónada de continuación.

Las mónadas son una construcción de programación funcional utilizada para simular el estado entre diferentes pasos de un cálculo (Recuerde que un lenguaje funcional es sin estado).
Lo que hace una mónada es encadenar diferentes funciones, creando una "tubería de cálculo" donde cada paso conoce el estado actual del cálculo.

Las mónadas tienen dos pilares principales:

• Una función de retorno, que toma un valor y lo devuelve en una forma lista para Monad.
• Una función de vinculación, que toma un valor de Monad-ready (del paso de la tubería anterior) y lo desenvuelve a su original para pasar el valor al siguiente paso.

La Wikipedia tiene muy buenos ejemplos y explicaciones sobre las mónadas.

Permítanme reescribir el código C ++ 14 dado:

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

Creo que aquí identificamos la función de return de una mónada: toma el valor y lo devuelve de forma monádica. Específicamente, este retorno devuelve un funtor (en el sentido matemático, no un funtor C ++) que va de la categoría "tupla" a la categoría paquete variadic.

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

pack_size es solo una función normal. Sería usado en una tubería para hacer algún trabajo.

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

Y la length es solo una versión no genérica de algo cercano al operador de bind mónada, un operador que toma un valor monádico de un paso de canalización anterior, y lo deriva a la función especificada (Función que realmente hace el trabajo). Esa función es la funcionalidad que realiza este paso de cálculo.

Finalmente su llamada podría reescribirse como:

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

Entonces, ¿cuál es el nombre de este idioma de creación de tuplas? Bueno, creo que esto podría llamarse " tuplas tipo mónada ", ya que no es exactamente una mónada, pero la representación y expansión de la tupla funciona de manera similar, permaneciendo en la mónada de continuación de Haskell.

Editar: más divertido

Solo por el temblor de la divertida programación C ++, seguí explorando esta cosa parecida a una mónada. Puedes encontrar algunos ejemplos here .

Answer 2

Esto parece una forma de estilo de continuación de paso .

La idea aproximada de CPS es esta: en lugar de tener una función (digamos f ) devolver algún valor, le das a f otro argumento, que es una función, llamada continuación . Entonces, f llama a esta continuación con el valor de retorno en lugar de regresar. Tomemos un ejemplo:

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

se convierte

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

La llamada es una llamada de cola, y se puede optimizar en un salto (esta es la razón por la cual el TCO es obligatorio en algunos idiomas, como Scheme, cuya semántica depende de alguna forma de transformación en CPS).

Otro ejemplo:

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

Ahora puede hacer get_int (std::bind (f, _1, print_int)) para imprimir 54. Tenga en cuenta que todas las llamadas de continuación son siempre llamadas de cola (la llamada a printf también es una llamada de continuación).

Un ejemplo bien conocido son las devoluciones de llamada asincrónicas (llamadas AJAX en JavaScript, por ejemplo): pasa una continuación a una rutina que se ejecuta en paralelo.

Las continuas se pueden componer (y formar una mónada , en caso de que esté interesado), como en el ejemplo anterior. De hecho , es posible transformar un programa (funcional) completamente en CPS, de modo que cada llamada es una llamada final (¡y luego no necesita una pila para ejecutar el programa!).

Answer 3

Llamaría a este modificador de tuplas continuas o, más en general, continuador monádico . Definitivamente es una instancia de una mónada de continuación. Una gran introducción para la mónada de continuación para programadores de C ++ está here . En esencia, la list lambda anterior toma un valor (un paquete de parámetros variados) y devuelve un simple ''continuador'' (el cierre interno). Este continuador, cuando se le otorga un access invocable (llamado access ), pasa el paquete de parámetros y devuelve lo que retorna.

Tomando prestado del blogpost de FPComplete, un continuador es más o menos como el siguiente.

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

El Continuator anterior es abstracto, no proporciona una implementación. Entonces, aquí hay uno simple.

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 acepta un valor de tipo A y lo andThen para access cuando se llama y luego. La list lambda anterior es esencialmente la misma. Es más general. En lugar de un solo valor, el cierre interno captura un paquete de parámetros y lo pasa a la función de access . ¡Ordenado!

Esperemos que eso explique lo que significa ser un continuador. pero ¿qué significa ser una mónada? Aquí hay una buena introduction usando imágenes.

Creo que la list lambda también es una lista de mónadas, que se implementa como una mónada de continuación. Tenga en cuenta que la mónada de continuación es la madre de todas las mónadas . Es decir, puede implementar cualquier mónada con una mónada de continuación. Por supuesto, la lista de mónada no está fuera de su alcance.

Como un paquete de parámetros es, naturalmente, una ''lista'' (a menudo de tipos heterogéneos), tiene sentido que funcione como una mónada de lista / secuencia. La list anterior de lambda es una forma muy interesante de convertir paquetes de parámetros C ++ a una estructura monádica. Por lo tanto, las operaciones se pueden encadenar una tras otra.

La length lambda anterior, sin embargo, es un poco decepcionante porque rompe la mónada y la lambda anidada en su interior simplemente devuelve un número entero. Podría decirse que hay una mejor manera de escribir la longitud ''getter'' como se muestra a continuación.

---- Functor ----

Antes de que podamos decir que la lista lambda es una mónada, tenemos que demostrar que es un funtor. Es decir, fmap debe escribirse para la lista.

La lista anterior de lambda sirve como el creador del functor de un paquete de parámetros, esencialmente sirve como return . Ese functor creado mantiene el paquete de parámetros consigo mismo (captura) y permite el "acceso" a él siempre que proporcione un invocable que acepte una cantidad variable de argumentos. Tenga en cuenta que el llamable se llama EXACTAMENTE-UNA VEZ.

Vamos a escribir fmap para tal functor.

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

El tipo de func debe ser (a -> b). Es decir, en C ++ hablar,

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

El tipo de fmap es fmap: (a -> b) -> list[a] -> list[b] es decir, en C ++ speak,

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

Es decir, fmap simplemente asigna la lista de-a a una lista-de-b.

Ahora puedes hacer

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)

Por lo tanto, es un funtor.

----Monada----

Ahora, intentemos escribir un flatmap (aka bind , selectmany )

El tipo de flatmap es flatmap: (a -> list[b]) -> list[a] -> list[b].

Es decir, dada una función que mapea a a list-of-b y a list-of-a, flatmap devuelve una lista-de-b. Básicamente, toma cada elemento de la lista-de-a, las funciones funcionan en él, recibe (potencialmente vacío) list-of-b uno por uno, luego concatena toda la lista-de-b, y finalmente devuelve la lista final -de B.

Aquí hay una implementación de flatmap for list.

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

Ahora puedes hacer muchas cosas poderosas con una lista. Por ejemplo,

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.

La función de recuento es una operación de mantenimiento de mónadas porque devuelve una lista de un solo elemento. Si realmente desea obtener la longitud (no incluida en una lista), debe finalizar la cadena monádica y obtener el valor de la siguiente manera.

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

Si se hace bien, el patrón de canalización de la colección (por ejemplo, filter , reduce ) ahora se puede aplicar a los paquetes de parámetros de C ++. ¡Dulce!

---- Leyes de Monad ----

Asegurémonos de que la list mónada cumpla con las tres leyes de mónadas .

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

Todas las afirmaciones están satisfechas.

---- Tubería de recolección ----

Aunque la lambda de ''lista'' anterior es probablemente una mónada y comparte características de la proverbial ''lista-mónada'', es bastante desagradable. Especialmente, porque el comportamiento de los combinadores comunes de tuberías de recolección , como el filter (también conocido como " where ) no cumple con las expectativas comunes.

La razón es cómo funcionan las lambdas C ++. Cada expresión lambda produce un objeto de función de un tipo único. Por lo tanto, list(1,2,3) produce un tipo que no tiene nada que ver con list(1) y una lista vacía, que en este caso sería list() .

La implementación directa de where falla la compilación porque en C ++ una función no puede devolver dos tipos diferentes.

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

En la implementación anterior, func devuelve un booleano. Es un predicado que dice verdadero o falso para cada elemento. El operador?: No compila.

Por lo tanto, se puede usar un truco diferente para permitir la continuación de la canalización de la colección. En lugar de filtrar los elementos, simplemente se marcan como tales, y eso es lo que lo hace desagradable.

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

The where_unpleasant hace el trabajo pero desagradablemente ...

Por ejemplo, así es como puedes filtrar los elementos negativos.

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

---- Tuplas heterogéneas ----

Hasta ahora, la discusión fue sobre tuplas homogéneas. Ahora vamos a generalizarlo a tuplas verdaderas. Sin embargo, fmap , flatmap , where toma solo una devolución de llamada lambda. Para proporcionar múltiples lambdas cada uno trabajando en un tipo, podemos sobrecargarlos. Por ejemplo,

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    

Usemos la técnica lambda sobrecargada para procesar un continuador heterogéneo de tuplas.

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

Por último, Live Ejemplo