¿Cómo se puede hacer curry en C++?

https://stackoverflow.com/questions/152005

02-07-2019
|

Pregunta

¿Qué es el curry?

¿Cómo se puede hacer curry en C++?

¿Explique las carpetas en el contenedor STL?

Solución

En resumen, el curry toma una función f(x, y) y, dado un Y fijo, le da una nueva función g(x) donde

g(x) == f(x, Y)

Esta nueva función se puede invocar en situaciones en las que solo se proporciona un argumento y pasa la llamada a la función f original con el argumento <=> fijo.

Las carpetas en el STL le permiten hacer esto para las funciones de C ++. Por ejemplo:

#include <functional>
#include <iostream>
#include <vector>

using namespace std;

// declare a binary function object
class adder: public binary_function<int, int, int> {
public:
    int operator()(int x, int y) const
    {
        return x + y;
    }
};

int main()
{
    // initialise some sample data
    vector<int> a, b;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);

    // here we declare a function object f and try it out
    adder f;
    cout << "f(2, 3) = " << f(2, 3) << endl;

    // transform() expects a function with one argument, so we use
    // bind2nd to make a new function based on f, that takes one
    // argument and adds 5 to it
    transform(a.begin(), a.end(), back_inserter(b), bind2nd(f, 5));

    // output b to see what we got
    cout << "b = [" << endl;
    for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) {
        cout << "  " << *i << endl;
    }
    cout << "]" << endl;

    return 0;
}

Otros consejos

1.¿Qué es el curry?

Currying simplemente significa una transformación de una función de varios argumentos a una función de un solo argumento.Esto se ilustra más fácilmente con un ejemplo:

tomar una función f que acepta tres argumentos:

int
f(int a,std::string b,float c)
{
    // do something with a, b, and c
    return 0;
}

si queremos llamar f, tenemos que proporcionar todos sus argumentos. f(1,"some string",19.7f).

Luego una versión al curry de f, llamémoslo curried_f=curry(f) sólo espera un único argumento, que corresponde al primer argumento de f, es decir, el argumento a.Además, f(1,"some string",19.7f) También se puede escribir usando la versión al curry como curried_f(1)("some string")(19.7f).El valor de retorno de curried_f(1) por otro lado es simplemente otra función, que maneja el siguiente argumento de f.Al final, terminamos con una función o invocable. curried_f que cumple la siguiente igualdad:

curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg).

2.¿Cómo se puede lograr el curry en C++?

Lo siguiente es un poco más complicado, pero funciona muy bien para mí (usando c++11)...También permite curry de grado arbitrario como este: auto curried=curry(f)(arg1)(arg2)(arg3) y después auto result=curried(arg4)(arg5).Aquí va:

#include <functional>

namespace _dtl {

    template <typename FUNCTION> struct
    _curry;

    // specialization for functions with a single argument
    template <typename R,typename T> struct
    _curry<std::function<R(T)>> {
        using
        type = std::function<R(T)>;

        const type
        result;

        _curry(type fun) : result(fun) {}

    };

    // recursive specialization for functions with more arguments
    template <typename R,typename T,typename...Ts> struct
    _curry<std::function<R(T,Ts...)>> {
        using
        remaining_type = typename _curry<std::function<R(Ts...)> >::type;

        using
        type = std::function<remaining_type(T)>;

        const type
        result;

        _curry(std::function<R(T,Ts...)> fun)
        : result (
            [=](const T& t) {
                return _curry<std::function<R(Ts...)>>(
                    [=](const Ts&...ts){ 
                        return fun(t, ts...); 
                    }
                ).result;
            }
        ) {}
    };
}

template <typename R,typename...Ts> auto
curry(const std::function<R(Ts...)> fun)
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
    return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}

template <typename R,typename...Ts> auto
curry(R(* const fun)(Ts...))
-> typename _dtl::_curry<std::function<R(Ts...)>>::type
{
    return _dtl::_curry<std::function<R(Ts...)>>(fun).result;
}

#include <iostream>

void 
f(std::string a,std::string b,std::string c)
{
    std::cout << a << b << c;
}

int 
main() {
    curry(f)("Hello ")("functional ")("world!");
    return 0;
}

Bien, como comentó Samer, debería agregar algunas explicaciones sobre cómo funciona esto.La implementación real se realiza en el _dtl::_curry, mientras la plantilla funciona curry son sólo envoltorios de conveniencia.La implementación es recursiva sobre los argumentos del std::function argumento de plantilla FUNCTION.

Para una función con un solo argumento, el resultado es idéntico a la función original.

        _curry(std::function<R(T,Ts...)> fun)
        : result (
            [=](const T& t) {
                return _curry<std::function<R(Ts...)>>(
                    [=](const Ts&...ts){ 
                        return fun(t, ts...); 
                    }
                ).result;
            }
        ) {}

Aquí lo complicado:Para una función con más argumentos, devolvemos una lambda cuyo argumento está vinculado al primer argumento de la llamada a fun.Finalmente, el resto del curry para el resto. N-1 argumentos se delega a la implementación de _curry<Ts...> con un argumento de plantilla menos.

Actualización para c++14/17:

Me acaba de llegar una nueva idea para abordar el problema del curry...Con la introducción de if constexpr en c ++ 17 (y con la ayuda de void_t para determinar si una función está completamente currada), las cosas parecen volverse mucho más fáciles:

template< class, class = std::void_t<> > struct 
needs_unapply : std::true_type { };

template< class T > struct 
needs_unapply<T, std::void_t<decltype(std::declval<T>()())>> : std::false_type { };

template <typename F> auto
curry(F&& f) {
  /// Check if f() is a valid function call. If not we need 
  /// to curry at least one argument:
  if constexpr (needs_unapply<decltype(f)>::value) {
       return [=](auto&& x) {
            return curry(
                [=](auto&&...xs) -> decltype(f(x,xs...)) {
                    return f(x,xs...);
                }
            );
        };    
  }
  else {  
    /// If 'f()' is a valid call, just call it, we are done.
    return f();
  }
}

int 
main()
{
  auto f = [](auto a, auto b, auto c, auto d) {
    return a  * b * c * d;
  };

  return curry(f)(1)(2)(3)(4);
}

Vea el código en acción en aquí.Con un enfoque similar, aquí es cómo curry funciones con un número arbitrario de argumentos.

La misma idea parece funcionar también en C++14, si intercambiamos el constexpr if con una selección de plantilla dependiendo de la prueba needs_unapply<decltype(f)>::value:

template <typename F> auto
curry(F&& f);

template <bool> struct
curry_on;

template <> struct
curry_on<false> {
    template <typename F> static auto
    apply(F&& f) {
        return f();
    }
};

template <> struct
curry_on<true> {
    template <typename F> static auto 
    apply(F&& f) {
        return [=](auto&& x) {
            return curry(
                [=](auto&&...xs) -> decltype(f(x,xs...)) {
                    return f(x,xs...);
                }
            );
        };
    }
};

template <typename F> auto
curry(F&& f) {
    return curry_on<needs_unapply<decltype(f)>::value>::template apply(f);
}

Simplificando el ejemplo de Gregg, usando tr1:

#include <functional> 
using namespace std;
using namespace std::tr1;
using namespace std::tr1::placeholders;

int f(int, int);
..
int main(){
    function<int(int)> g     = bind(f, _1, 5); // g(x) == f(x, 5)
    function<int(int)> h     = bind(f, 2, _1); // h(x) == f(2, x)
    function<int(int,int)> j = bind(g, _2);    // j(x,y) == g(y)
}

Los componentes funcionales Tr1 le permiten escribir código rico en estilo funcional en C ++. Además, C ++ 0x permitirá que las funciones lambda en línea también hagan esto:

int f(int, int);
..
int main(){
    auto g = [](int x){ return f(x,5); };      // g(x) == f(x, 5)
    auto h = [](int x){ return f(2,x); };      // h(x) == f(2, x)
    auto j = [](int x, int y){ return g(y); }; // j(x,y) == g(y)
}

Y aunque C ++ no proporciona el rico análisis de efectos secundarios que realizan algunos lenguajes de programación orientados a funciones, el análisis constante y la sintaxis lambda C ++ 0x pueden ayudar:

struct foo{
    int x;
    int operator()(int y) const {
        x = 42; // error!  const function can't modify members
    }
};
..
int main(){
    int x;
    auto f = [](int y){ x = 42; }; // error! lambdas don't capture by default.
}

Espero que eso ayude.

Eche un vistazo a Boost.Bind lo que hace que el proceso mostrado por Greg sea más versátil:

transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));

Esto une 5 al segundo argumento de f.

Vale & # 8217; vale la pena señalar que esto es no curry (en cambio, es & # 8217; s aplicación parcial). Sin embargo, usar curry de manera general es difícil en C ++ (de hecho, solo recientemente se hizo posible) y en su lugar a menudo se usa una aplicación parcial.

Otras respuestas explican muy bien las carpetas, así que no repetiré esa parte aquí. Solo demostraré cómo se puede hacer curry y aplicación parcial con lambdas en C ++ 0x.

Ejemplo de código: (Explicación en los comentarios)

#include <iostream>
#include <functional>

using namespace std;

const function<int(int, int)> & simple_add = 
  [](int a, int b) -> int {
    return a + b;
  };

const function<function<int(int)>(int)> & curried_add = 
  [](int a) -> function<int(int)> {
    return [a](int b) -> int {
      return a + b;
    };
  };

int main() {
  // Demonstrating simple_add
  cout << simple_add(4, 5) << endl; // prints 9

  // Demonstrating curried_add
  cout << curried_add(4)(5) << endl; // prints 9

  // Create a partially applied function from curried_add
  const auto & add_4 = curried_add(4);
  cout << add_4(5) << endl; // prints 9
}

Si está utilizando C ++ 14 es muy fácil:

template<typename Function, typename... Arguments>
auto curry(Function function, Arguments... args) {
    return [=](auto... rest) {
        return function(args..., rest...);
    }
}

Puedes usarlo así:

auto add = [](auto x, auto y) { return x + y; }

// curry 4 into add
auto add4 = curry(add, 4);

add4(6); // 10

El curry es una forma de reducir una función que toma múltiples argumentos en una secuencia de funciones anidadas con un argumento cada uno:

full = (lambda a, b, c: (a + b + c))
print full (1, 2, 3) # print 6

# Curried style
curried = (lambda a: (lambda b: (lambda c: (a + b + c))))
print curried (1)(2)(3) # print 6

El curry es bueno porque puedes definir funciones que son simplemente envolturas alrededor de otras funciones con valores predefinidos, y luego pasar las funciones simplificadas. Los archivadores STL de C ++ proporcionan una implementación de esto en C ++.

Algunas respuestas geniales aquí. Pensé en agregar el mío porque era divertido jugar con el concepto.

Aplicación de función parcial : El proceso de " vinculante " una función con solo algunos de sus parámetros, aplazando el resto para que se complete más tarde. El resultado es otra función con menos parámetros.

Curry : es una forma especial de aplicación de función parcial donde solo puede " bind " Un solo argumento a la vez. El resultado es otra función con exactamente 1 parámetro menos.

El código que estoy a punto de presentar es la aplicación de función parcial desde la cual es posible curry, pero no es la única posibilidad. Ofrece algunos beneficios sobre las implementaciones de curry anteriores (principalmente porque es una aplicación de función parcial y no curry, heh).

Aplicar sobre una función vacía:

auto sum0 = [](){return 0;};
std::cout << partial_apply(sum0)() << std::endl;

Aplicando múltiples argumentos a la vez:

auto sum10 = [](int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){return a+b+c+d+e+f+g+h+i+j;};
std::cout << partial_apply(sum10)(1)(1,1)(1,1,1)(1,1,1,1) << std::endl; // 10

constexpr soporte que permite el tiempo de compilación static_assert:
```
static_assert(partial_apply(sum0)() == 0);
```
Un mensaje de error útil si accidentalmente va demasiado lejos al proporcionar argumentos:
```
auto sum1 = [](int x){ return x;};
partial_apply(sum1)(1)(1);
```
error: static_assert falló " ¡Intentando aplicar demasiados argumentos! "

Otras respuestas anteriores devuelven lambdas que unen un argumento y luego devuelven más lambdas. Este enfoque envuelve esa funcionalidad esencial en un objeto invocable. Las definiciones para operator() permiten llamar a la lambda interna. Las plantillas variables nos permiten verificar si alguien va demasiado lejos, y una función de conversión implícita al tipo de resultado de la llamada a la función nos permite imprimir el resultado o comparar el objeto con una primitiva.

Código:

namespace detail{
template<class F>
using is_zero_callable = decltype(std::declval<F>()());

template<class F>
constexpr bool is_zero_callable_v = std::experimental::is_detected_v<is_zero_callable, F>;
}

template<class F>
struct partial_apply_t
{
    template<class... Args>
    constexpr auto operator()(Args... args)
    {
        static_assert(sizeof...(args) == 0 || !is_zero_callable, "Attempting to apply too many arguments!");
        auto bind_some = [=](auto... rest) -> decltype(myFun(args..., rest...))
        {
           return myFun(args..., rest...);
        };
        using bind_t = decltype(bind_some);

        return partial_apply_t<bind_t>{bind_some};
    }
    explicit constexpr partial_apply_t(F fun) : myFun(fun){}

    constexpr operator auto()
    {
        if constexpr (is_zero_callable)
            return myFun();
        else
            return *this; // a callable
    }
    static constexpr bool is_zero_callable = detail::is_zero_callable_v<F>;
    F myFun;
};

Demo en vivo

Algunas notas más:

Elegí usar is_detected principalmente para disfrutar y practicar; sirve lo mismo que un rasgo de tipo normal aquí.
Definitivamente podría haber más trabajo para apoyar el reenvío perfecto por razones de rendimiento
El código es C ++ 17 porque requiere <=> soporte de lambda en C ++ 17
- Y parece que GCC 7.0.1 todavía no está allí, así que usé Clang 5.0.0

Algunas pruebas:

auto sum0 = [](){return 0;};
auto sum1 = [](int x){ return x;};
auto sum2 = [](int x, int y){ return x + y;};
auto sum3 = [](int x, int y, int z){ return x + y + z; };
auto sum10 = [](int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){return a+b+c+d+e+f+g+h+i+j;};

std::cout << partial_apply(sum0)() << std::endl; //0
static_assert(partial_apply(sum0)() == 0, "sum0 should return 0");
std::cout << partial_apply(sum1)(1) << std::endl; // 1
std::cout << partial_apply(sum2)(1)(1) << std::endl; // 2
std::cout << partial_apply(sum3)(1)(1)(1) << std::endl; // 3
static_assert(partial_apply(sum3)(1)(1)(1) == 3, "sum3 should return 3");
std::cout << partial_apply(sum10)(1)(1,1)(1,1,1)(1,1,1,1) << std::endl; // 10
//partial_apply(sum1)(1)(1); // fails static assert
auto partiallyApplied = partial_apply(sum3)(1)(1);
std::function<int(int)> finish_applying = partiallyApplied;
std::cout << std::boolalpha << (finish_applying(1) == 3) << std::endl; // true

auto plus2 = partial_apply(sum3)(1)(1);
std::cout << std::boolalpha << (plus2(1) == 3) << std::endl; // true
std::cout << std::boolalpha << (plus2(3) == 5) << std::endl; // true

También implementé el curry con plantillas variadas (ver la respuesta de Julian). Sin embargo, no hice uso de recursividad o std::function. Nota: Utiliza una serie de características C ++ 14 .

El ejemplo proporcionado (main función) en realidad se ejecuta en tiempo de compilación, lo que demuestra que el método de curry no supera las optimizaciones esenciales por parte del compilador.

El código se puede encontrar aquí: https://gist.github.com/Garciat/c7e4bef299ee5c607948

con este archivo auxiliar: https://gist.github.com/Garciat/cafe27d04cfdff0e891e

El código todavía necesita (mucho) trabajo, que puedo o no completar pronto. De cualquier manera, estoy publicando esto aquí para referencia futura.

Código de publicación en caso de que los enlaces mueran (aunque no deberían):

#include <type_traits>
#include <tuple>
#include <functional>
#include <iostream>

// ---

template <typename FType>
struct function_traits;

template <typename RType, typename... ArgTypes>
struct function_traits<RType(ArgTypes...)> {
    using arity = std::integral_constant<size_t, sizeof...(ArgTypes)>;

    using result_type = RType;

    template <size_t Index>
    using arg_type = typename std::tuple_element<Index, std::tuple<ArgTypes...>>::type;
};

// ---

namespace details {
    template <typename T>
    struct function_type_impl
      : function_type_impl<decltype(&T::operator())>
    { };

    template <typename RType, typename... ArgTypes>
    struct function_type_impl<RType(ArgTypes...)> {
        using type = RType(ArgTypes...);
    };

    template <typename RType, typename... ArgTypes>
    struct function_type_impl<RType(*)(ArgTypes...)> {
        using type = RType(ArgTypes...);
    };

    template <typename RType, typename... ArgTypes>
    struct function_type_impl<std::function<RType(ArgTypes...)>> {
        using type = RType(ArgTypes...);
    };

    template <typename T, typename RType, typename... ArgTypes>
    struct function_type_impl<RType(T::*)(ArgTypes...)> {
        using type = RType(ArgTypes...);
    };

    template <typename T, typename RType, typename... ArgTypes>
    struct function_type_impl<RType(T::*)(ArgTypes...) const> {
        using type = RType(ArgTypes...);
    };
}

template <typename T>
struct function_type
  : details::function_type_impl<typename std::remove_cv<typename std::remove_reference<T>::type>::type>
{ };

// ---

template <typename Args, typename Params>
struct apply_args;

template <typename HeadArgs, typename... Args, typename HeadParams, typename... Params>
struct apply_args<std::tuple<HeadArgs, Args...>, std::tuple<HeadParams, Params...>>
  : std::enable_if<
        std::is_constructible<HeadParams, HeadArgs>::value,
        apply_args<std::tuple<Args...>, std::tuple<Params...>>
    >::type
{ };

template <typename... Params>
struct apply_args<std::tuple<>, std::tuple<Params...>> {
    using type = std::tuple<Params...>;
};

// ---

template <typename TupleType>
struct is_empty_tuple : std::false_type { };

template <>
struct is_empty_tuple<std::tuple<>> : std::true_type { };

// ----

template <typename FType, typename GivenArgs, typename RestArgs>
struct currying;

template <typename FType, typename... GivenArgs, typename... RestArgs>
struct currying<FType, std::tuple<GivenArgs...>, std::tuple<RestArgs...>> {
    std::tuple<GivenArgs...> given_args;

    FType func;

    template <typename Func, typename... GivenArgsReal>
    constexpr
    currying(Func&& func, GivenArgsReal&&... args) :
      given_args(std::forward<GivenArgsReal>(args)...),
      func(std::move(func))
    { }

    template <typename... Args>
    constexpr
    auto operator() (Args&&... args) const& {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CanExecute = is_empty_tuple<RestArgsPrime>;

        return apply(CanExecute{}, std::make_index_sequence<sizeof...(GivenArgs)>{}, std::forward<Args>(args)...);
    }

    template <typename... Args>
    constexpr
    auto operator() (Args&&... args) && {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CanExecute = is_empty_tuple<RestArgsPrime>;

        return std::move(*this).apply(CanExecute{}, std::make_index_sequence<sizeof...(GivenArgs)>{}, std::forward<Args>(args)...);
    }

private:
    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::false_type, std::index_sequence<Indices...>, Args&&... args) const& {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CurryType = currying<FType, std::tuple<GivenArgs..., Args...>, RestArgsPrime>;

        return CurryType{ func, std::get<Indices>(given_args)..., std::forward<Args>(args)... };
    }

    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::false_type, std::index_sequence<Indices...>, Args&&... args) && {
        using ParamsTuple = std::tuple<RestArgs...>;
        using ArgsTuple = std::tuple<Args...>;

        using RestArgsPrime = typename apply_args<ArgsTuple, ParamsTuple>::type;

        using CurryType = currying<FType, std::tuple<GivenArgs..., Args...>, RestArgsPrime>;

        return CurryType{ std::move(func), std::get<Indices>(std::move(given_args))..., std::forward<Args>(args)... };
    }

    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::true_type, std::index_sequence<Indices...>, Args&&... args) const& {
        return func(std::get<Indices>(given_args)..., std::forward<Args>(args)...);
    }

    template <typename... Args, size_t... Indices>
    constexpr
    auto apply(std::true_type, std::index_sequence<Indices...>, Args&&... args) && {
        return func(std::get<Indices>(std::move(given_args))..., std::forward<Args>(args)...);
    }
};

// ---

template <typename FType, size_t... Indices>
constexpr
auto curry(FType&& func, std::index_sequence<Indices...>) {
    using RealFType = typename function_type<FType>::type;
    using FTypeTraits = function_traits<RealFType>;

    using CurryType = currying<FType, std::tuple<>, std::tuple<typename FTypeTraits::template arg_type<Indices>...>>;

    return CurryType{ std::move(func) };
}

template <typename FType>
constexpr
auto curry(FType&& func) {
    using RealFType = typename function_type<FType>::type;
    using FTypeArity = typename function_traits<RealFType>::arity;

    return curry(std::move(func), std::make_index_sequence<FTypeArity::value>{});
}

// ---

int main() {
    auto add = curry([](int a, int b) { return a + b; });

    std::cout << add(5)(10) << std::endl;
}

Estos enlaces son relevantes:

La página de cálculo Lambda en Wikipedia tiene un claro ejemplo de curry
http://en.wikipedia.org/wiki/Lambda_calculus#Motivation

Este documento trata el curry en C / C ++
http://asg.unige.ch/site/papers/Dami91a.pdf

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow