devc - dev c++ c++ 14

composición de funciones en C++/C++ 11

Question

Actualmente estoy codificando algunos algoritmos criptográficos en C ++ 11 que requieren muchas composiciones de funciones. Hay 2 tipos de composición con los que tengo que lidiar:

1. Componga una función en sí misma un número variable de veces. Matemáticamente, para una determinada función F, F ^ n (x) = (F ^ {n-1} o F) (x) = F ^ {n-1} (F (x)).

2. Componen diferentes funciones juntas. Por ejemplo, para algunas funciones f, g, h, i, j y k del mismo tipo, tendré f (g (h (i (j (k (x)))))).

En mi caso, estoy usando la siguiente definición de F:

const std::vector<uint8_t> F(const std::vector<uint8_t> &x);

Me gustaría componer esta función en sí misma n veces. He implementado la composición de una manera recursiva simple que funciona bien:

const std::vector<uint8_t> compose(const uint8_t n, const std::vector<uint8_t> &x)
{
if(n > 1)
return compose(n-1, F(x));
return F(x);
}

Para este caso, ¿hay una manera más eficiente de implementar esta composición usando c ++ 11 pero sin usar BOOST ? Sería genial usar este formulario si es posible, por supuesto:

answer = compose<4>(F)(x); // Same as ''answer = F^4(x) = F(F(F(F(x))))''

Para el segundo caso, me gustaría implementar la composición de un número variable de funciones. Para un conjunto dado de funciones F0, F1, ..., Fn que tiene la misma definición que F, ¿existe una forma eficiente y adecuada de componerlas donde n es variable? Creo que la plantilla variadic sería útil aquí, pero no sé cómo usarlos en ese caso.

Gracias por tu ayuda.

Answer 1

¿Qué pasa con (sin probar):

template < typename Func, typename T >
T compose_impl( Func &&, T &&x, std::integral_constant<std::size_t, 0> )
{ return std::forward<T>(x); }
template < typename Func, typename T, std::size_t N >
T compose_impl( Func &&f, T &&x, std::integral_constant<std::size_t, N> )
{
return compose_impl( std::forward<Func>(f),
std::forward<Func>(f)(std::forward<T>( x )),
std::integral_constant<std::size_t, N-1>{} );
}
template < std::size_t Repeat = 1, typename Func, typename T >
T compose( Func &&f, T &&x )
{
return compose_impl( std::forward<Func>(f), std::forward<T>(x),
std::integral_constant<std::size_t, Repeat>{} );
}

Podemos usar plantillas de funciones variables para múltiples funciones (no probadas):

template < typename Func, typename T >
constexpr // C++14 only, due to std::forward not being constexpr in C++11
auto chain_compose( Func &&f, T &&x )
noexcept( noexcept(std::forward<Func>( f )( std::forward<T>(x) )) )
-> decltype( std::forward<Func>(f)(std::forward<T>( x )) )
{ return std::forward<Func>(f)(std::forward<T>( x )); }
template < typename Func1, typename Func2, typename Func3, typename ...RestAndT >
constexpr // C++14 only, due to std::forward
auto chain_compose( Func1 &&f, Func2 &&g, Func3 &&h, RestAndT &&...i_and_x )
noexcept( CanAutoWorkHereOtherwiseDoItYourself )
-> decltype( auto ) // C++14 only
{
return chain_compose( std::forward<Func1>(f),
chain_compose(std::forward<Func2>( g ), std::forward<Func3>( h ),
std::forward<RestAndT>( i_and_x )...) );
}

El próximo decltype(auto) constructo calcula automáticamente el tipo de retorno de una función en línea. No sé si hay un cálculo automático similar para noexcept

Answer 2

Algo a lo largo de estas líneas, quizás (no probado):

template <typename F>
class Composer {
int n_;
F f_;
public:
Composer(int n, F f) : n_(n), f_(f) {}
template <typename T>
T operator()(T x) const {
int n = n_;
while (n--) {
x = f_(x);
}
return x;
}
};
template <int N, typename F>
Composer<F> compose(F f) {
return Composer<F>(N, f);
}

EDIT: Y para el segundo caso ( probado esta vez ):

#include <iostream>
template <typename F0, typename... F>
class Composer2 {
F0 f0_;
Composer2<F...> tail_;
public:
Composer2(F0 f0, F... f) : f0_(f0), tail_(f...) {}
template <typename T>
T operator() (const T& x) const {
return f0_(tail_(x));
}
};
template <typename F>
class Composer2<F> {
F f_;
public:
Composer2(F f) : f_(f) {}
template <typename T>
T operator() (const T& x) const {
return f_(x);
}
};
template <typename... F>
Composer2<F...> compose2(F... f) {
return Composer2<F...>(f...);
}
int f(int x) { return x + 1; }
int g(int x) { return x * 2; }
int h(int x) { return x - 1; }
int main() {
std::cout << compose2(f, g, h)(42);
return 0;
}

Answer 3

Gracias por la divertida pregunta, Gabriel del año 2013. Aquí hay una solución. Funciona en c ++ 14.

#include <functional>
#include <iostream>
using std::function;
// binary function composition for arbitrary types
template <class F, class G>
auto compose(F f, G g){
return [f,g](auto x){return f(g(x));};
}
// for convienience
template <class F, class G>
auto operator*(F f, G g){
return compose(f,g);
}
// composition for n arguments
template <class F, typename... Fs>
auto compose(F f, Fs&&... fs) {
return f * compose(fs...);
}
// composition for n copies of f
template <int i, class F>
//must wrap chain in a struct to allow partial template specialization
struct multi { static F chain(F f){
return f * multi<i-1,F>::chain(f);
}};
template <class F>
struct multi <2,F> { static F chain(F f){
return f * f;
}};
template <int i, class F>
F compose(F f) {return multi<i,F>::chain(f); }
int main(int argc, char const *argv[]) {
function<double(int)> f = [](auto i){return i + 3;};
function<int(double)> g = [](auto i){return i * 2;};
function<int(int) > h = [](auto i){return i + 1;};
std::cout
<< ''/n'' << "9 == " << compose(f,g,f) (0) /
<< ''/n'' << "9 == " << (f * g * h) (0) /
<< ''/n'' << "3 == " << compose<100>(h) (0) /
<< ''/n'';
return 0;
}

Usted puede definir

Matrix compose(Matrix f, Matrix g);

o

Rotation compose(Rotation f, Rotation g);

Para reutilizar este código para todo tipo de cosas.

Answer 4

No ha mostrado el cuerpo de F , pero si puede modificarlo para que mute la entrada para formar la salida, cambie la firma a:

void F(std::vector<uint8_t>& x);

A partir de entonces puedes implementar Fn como:

void Fn(std::vector<uint8_t>& x, size_t n)
{
for (size_t i = 0; i < n; i++)
F(x);
}

El compilador desenrollará el bucle para usted si es más eficiente, pero incluso si no lo hace, un incremento / comparación de una variable local será órdenes de magnitud más rápido que llamar a F.

Luego, puede explorar y construir nuevos vectores cuando desee hacer una copia:

vector<uint8_t> v1 = ...;
vector<uint8_t> v2 = v1; // explicitly take copy
Fn(v2,10);

Answer 5

Un ejemplo muy general ( g++ -std=c++1y composition.cpp ):

// ---------------------------------------------------------
// "test" part
// ---------------------------------------------------------
int f(int a) { return 2*a; }
double g(int a) { return a+2.5; }
double h(double a) { return 2.5*a; }
double i(double a) { return 2.5-a; }
class Functor {
double x;
public:
Functor (double x_) : x(x_) { }
double operator() (double a) { return a*x; }
};
// ---------------------------------------------------------
// ---------------------------------------------------------
int main () {
auto l1 = [] (double a) { return a/3; };
auto l2 = [] (double a) { return 3.5+a; };
Functor fu {4.5};
auto compos1 = compose (f, g, l1, g, h, h, l1, l2);
auto compos2 = compose (compos1, l1, l2, fu);
auto x = compos2 (3);
cout << x << endl;
cout << compos2(3) << endl;
cout << fu(l2(l1(l2(l1(h(h(g(l1(g(f(3))))))))))) << endl;
} // ()

Parte de la biblioteca:

// ---------------------------------------------------------
// "library" part
// ---------------------------------------------------------
template<typename F1, typename F2>
class Composite{
private:
F1 f1;
F2 f2;
public:
Composite(F1 f1, F2 f2) : f1(f1), f2(f2) { }
template<typename IN>
decltype(auto) operator() (IN i)
{
return f2 ( f1(i) );
}
};
// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename F2>
decltype(auto) compose (F1 f, F2 g) {
return Composite<F1, F2> {f,g};
}
// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename... Fs>
decltype(auto) compose (F1 f, Fs ... args)
{
return compose (f, compose(args...));
}

Todo el programa:

// g++ -std=c++1y composition.cpp
#include <iostream>
using namespace std;
// ---------------------------------------------------------
// "library" part
// ---------------------------------------------------------
template<typename F1, typename F2>
class Composite{
private:
F1 f1;
F2 f2;
public:
Composite(F1 f1, F2 f2) : f1(f1), f2(f2) { }
template<typename IN>
decltype(auto) operator() (IN i)
{
return f2 ( f1(i) );
}
};
// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename F2>
decltype(auto) compose (F1 f, F2 g) {
return Composite<F1, F2> {f,g};
}
// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename... Fs>
decltype(auto) compose (F1 f, Fs ... args)
{
return compose (f, compose(args...));
}
// ---------------------------------------------------------
// "test" part
// ---------------------------------------------------------
int f(int a) { return 2*a; }
double g(int a) { return a+2.5; }
double h(double a) { return 2.5*a; }
double i(double a) { return 2.5-a; }
class Functor {
double x;
public:
Functor (double x_) : x(x_) { }
double operator() (double a) { return a*x; }
};
// ---------------------------------------------------------
// ---------------------------------------------------------
int main () {
auto l1 = [] (double a) { return a/3; };
auto l2 = [] (double a) { return 3.5+a; };
Functor fu {4.5};
auto compos1 = compose (f, g, l1, g, h, h, l1, l2);
auto compos2 = compose (compos1, l1, l2, fu);
auto x = compos2 (3);
cout << x << endl;
cout << compos2(3) << endl;
cout << fu(l2(l1(l2(l1(h(h(g(l1(g(f(3))))))))))) << endl;
} // ()

Answer 6

Una rápida implementación de la iteración de funciones con envío de argumentos. El tipo de ayuda desafortunadamente es necesario porque las plantillas de funciones no pueden ser parcialmente especializadas.

#include <functional>
#include <iostream>
using namespace std;
template<int n, typename A>
struct iterate_helper {
function<A(A)> f;
iterate_helper(function<A(A)> f) : f(f) {}
A operator()(A&& x) {
return f(iterate_helper<n - 1, A>(f)(forward<A>(x)));
};
};
template<typename A>
struct iterate_helper<1, A> {
function<A(A)> f;
iterate_helper(function<A(A)> f) : f(f) {}
A operator()(A&& x) {
return f(forward<A>(x));
};
};
template<int n, typename A>
function<A(A)> iterate(function<A(A)> f) {
return iterate_helper<n, A>(f);
}
int succ(int x) {
return x + 1;
}
int main() {
auto add5 = iterate<5>(function<int(int)>(succ));
cout << add5(10) << ''/n'';
}