¿Aplicación parcial con un C++ lambda?

Question

EDITAR: uso curry a continuación, pero me han informado que esta es una aplicación parcial.

He estado tratando de descubrir cómo se escribiría una función de curry en C++, ¡y de hecho lo descubrí!

#include <stdio.h> 
#include <functional> 

template< class Ret, class Arg1, class ...Args > 
auto curry( Ret f(Arg1,Args...), Arg1 arg) 
    -> std::function< Ret(Args...) > 
{ 
    return [=](Args ...args) { return f(arg, args...); }; 
} 

Y también escribí una versión para lambdas.

template< class Ret, class Arg1, class ...Args > 
auto curry( const std::function<Ret(Arg1,Args...)>& f, Arg1 arg) 
    -> std::function< Ret(Args...) > 
{ 
    return [=](Args ...args) { return f(arg, args...); }; 
} 

Las pruebas:

int f(int x, int y) 
{ 
    return x + y; 
} 

int main() 
{ 
    auto f5 = curry(f, 5); 
    auto g2 = curry(std::function<int(int,int)>([](int x, int y){ return x*y; }), 2); 
    printf("%d\n",f5(3)); 
    printf("%d\n",g2(3)); 
} 

puaj! La línea que inicializa g2 es tan grande que podría haberlo cursado manualmente.

auto g2 = [](int y){ return 2*y; }; 

Mucho más corto. Pero dado que la intención es tener una función de curry realmente genérica y conveniente, ¿podría (1) escribir una función mejor o (2) de alguna manera mi lambda para construir implícitamente una función std ::? Me temo que la versión actual viola la regla de la menor sorpresa cuando f no es una función gratuita. Especialmente molesto es cómo parece que no existe la función make_function o similar que conozco. Realmente, mi solución ideal sería simplemente llamar a std :: bind, pero no estoy seguro de cómo usarlo con plantillas variadas.

PD: Sin impulso, por favor, pero me conformaré con nada más.

EDIT: ya sé sobre std :: bind. No estaría escribiendo esta función si std :: bind hizo exactamente lo que yo quería con la mejor sintaxis. Esto debería ser más un caso especial donde solo se une el primer elemento.

Como dije, mi solución ideal debería ser usar bind, pero si quisiera usar eso, lo usaría.

Answer 1

Muchos de los ejemplos que las personas proporcionaron y que vi en otras partes usaron clases de ayuda para hacer lo que sea que hayan hecho. ¡Me di cuenta de que esto se vuelve trivial cuando escribo eso!

#include <utility> // for declval 
#include <array> 
#include <cstdio> 

using namespace std; 

template< class F, class Arg > 
struct PartialApplication 
{ 
    F f; 
    Arg arg; 

    constexpr PartialApplication(F&& f, Arg&& arg) 
     : f(forward<F>(f)), arg(forward<Arg>(arg)) 
    { 
    } 

    /* 
    * The return type of F only gets deduced based on the number of arguments 
    * supplied. PartialApplication otherwise has no idea whether f takes 1 or 10 args. 
    */ 
    template< class ... Args > 
    constexpr auto operator() (Args&& ...args) 
     -> decltype(f(arg,declval<Args>()...)) 
    { 
     return f(arg, forward<Args>(args)...); 
    } 
}; 

template< class F, class A > 
constexpr PartialApplication<F,A> partial(F&& f, A&& a) 
{ 
    return PartialApplication<F,A>(forward<F>(f), forward<A>(a)); 
} 

/* Recursively apply for multiple arguments. */ 
template< class F, class A, class B > 
constexpr auto partial(F&& f, A&& a, B&& b) 
    -> decltype(partial(partial(declval<F>(),declval<A>()), 
         declval<B>())) 
{ 
    return partial(partial(forward<F>(f),forward<A>(a)), forward<B>(b)); 
} 

/* Allow n-ary application. */ 
template< class F, class A, class B, class ...C > 
constexpr auto partial(F&& f, A&& a, B&& b, C&& ...c) 
    -> decltype(partial(partial(declval<F>(),declval<A>()), 
         declval<B>(),declval<C>()...)) 
{ 
    return partial(partial(forward<F>(f),forward<A>(a)), 
        forward<B>(b), forward<C>(c)...); 
} 

int times(int x,int y) { return x*y; } 

int main() 
{ 
    printf("5 * 2 = %d\n", partial(times,5)(2)); 
    printf("5 * 2 = %d\n", partial(times,5,2)()); 
} 

Answer 2

Su función curry es sólo un reducido sub-caso ineficiente de std::bind (std::bind1st y bind2nd no debe utilizarse más ahora que tenemos std::result_of)

Sus dos líneas de leer, de hecho,

auto f5 = std::bind(f, 5, _1); 
auto g2 = std::bind(std::multiplies<int>(), 2, _1); 

después de haber usado namespace std::placeholders. Esto evita cuidadosamente el boxeo en std::function y permite al compilador alinear más fácilmente el resultado en el sitio de la llamada.

Para funciones de dos argumentos, algo así como la piratería

auto bind1st(F&& f, T&& t) 
    -> decltype(std::bind(std::forward<F>(f), std::forward<T>(t), _1)) 
{ 
    return std::bind(std::forward<F>(f), std::forward<T>(t), _1) 
} 

podría funcionar, pero es difícil generalizar al caso variadic (para el que iba a terminar la reescritura de una gran cantidad de la lógica en std::bind) .

También currying no es una aplicación parcial. Currying tiene "firma"

((a, b) -> c) -> (a -> b -> c) 

ie. es la acción de transformar una función tomando dos argumentos en una función que devuelve una función. Tiene un inverso uncurry realizando la operación inversa (para los matemáticos: curry y uncurry son isomorfismos, y definen una adjunción). Este inverso es muy engorroso para escribir en C++ (sugerencia: use std::result_of).

Answer 3

Esta es una forma de tener currying en C++ y puede o no ser relevante después de las ediciones recientes en el OP.

Debido a la sobrecarga es muy problemático inspeccionar un functor y detectar su aridad. Sin embargo, lo que es posible es que, dado un functor f y un argumento a, podemos verificar si f(a) es una expresión válida. Si no es así, podemos almacenar a y dado el siguiente argumento b podemos verificar si f(a, b) es una expresión válida, y así sucesivamente. A saber:

#include <utility> 
#include <tuple> 

/* Two SFINAE utilities */ 

template<typename> 
struct void_ { using type = void; }; 

template<typename T> 
using Void = typename void_<T>::type; 

// std::result_of doesn't play well with SFINAE so we deliberately avoid it 
// and roll our own 
// For the sake of simplicity this result_of does not compute the same type 
// as std::result_of (e.g. pointer to members) 
template<typename Sig, typename Sfinae = void> 
struct result_of {}; 

template<typename Functor, typename... Args> 
struct result_of< 
    Functor(Args...) 
    , Void<decltype(std::declval<Functor>()(std::declval<Args>()...))> 
> { 
    using type = decltype(std::declval<Functor>()(std::declval<Args>()...)); 
}; 

template<typename Functor, typename... Args> 
using ResultOf = typename result_of<Sig>::type; 

template<typename Functor, typename... Args> 
class curry_type { 
    using tuple_type = std::tuple<Args...>; 
public: 
    curry_type(Functor functor, tuple_type args) 
     : functor(std::forward<Functor>(functor)) 
     , args(std::move(args)) 
    {} 

    // Same policy as the wrappers from std::bind & others: 
    // the functor inherits the cv-qualifiers from the wrapper 
    // you might want to improve on that and inherit ref-qualifiers, too 
    template<typename Arg> 
    ResultOf<Functor&(Args..., Arg)> 
    operator()(Arg&& arg) 
    { 
     return invoke(functor, std::tuple_cat(std::move(args), std::forward_as_tuple(std::forward<Arg>(arg)))); 
    } 

    // Implementation omitted for brevity -- same as above in any case 
    template<typename Arg> 
    ResultOf<Functor const&(Args..., Arg)> 
    operator()(Arg&& arg) const; 

    // Additional cv-qualified overloads omitted for brevity 

    // Fallback: keep calm and curry on 
    // the last ellipsis (...) means that this is a C-style vararg function 
    // this is a trick to make this overload (and others like it) least 
    // preferred when it comes to overload resolution 
    // the Rest pack is here to make for better diagnostics if a user erroenously 
    // attempts e.g. curry(f)(2, 3) instead of perhaps curry(f)(2)(3) 
    // note that it is possible to provide the same functionality without this hack 
    // (which I have no idea is actually permitted, all things considered) 
    // but requires further facilities (e.g. an is_callable trait) 
    template<typename Arg, typename... Rest> 
    curry_type<Functor, Args..., Arg> 
    operator()(Arg&& arg, Rest const&..., ...) 
    { 
     static_assert(sizeof...(Rest) == 0 
         , "Wrong usage: only pass up to one argument to a curried functor"); 
     return { std::forward<Functor>(functor), std::tuple_cat(std::move(args), std::forward_as_tuple(std::forward<Arg>(arg))) }; 
    } 

    // Again, additional overloads omitted 

    // This is actually not part of the currying functionality 
    // but is here so that curry(f)() is equivalent of f() iff 
    // f has a nullary overload 
    template<typename F = Functor> 
    ResultOf<F&(Args...)> 
    operator()() 
    { 
     // This check if for sanity -- if I got it right no user can trigger it 
     // It *is* possible to emit a nice warning if a user attempts 
     // e.g. curry(f)(4)() but requires further overloads and SFINAE -- 
     // left as an exercise to the reader 
     static_assert(sizeof...(Args) == 0, "How did you do that?"); 
     return invoke(functor, std::move(args)); 
    } 

    // Additional cv-qualified overloads for the nullary case omitted for brevity 

private: 
    Functor functor; 
    mutable tuple_type args; 

    template<typename F, typename Tuple, int... Indices> 
    ResultOf<F(typename std::tuple_element<Indices, Tuple>::type...)> 
    static invoke(F&& f, Tuple&& tuple, indices<Indices...>) 
    { 
     using std::get; 
     return std::forward<F>(f)(get<Indices>(std::forward<Tuple>(tuple))...); 
    } 

    template<typename F, typename Tuple> 
    static auto invoke(F&& f, Tuple&& tuple) 
    -> decltype(invoke(std::declval<F>(), std::declval<Tuple>(), indices_for<Tuple>())) 
    { 
     return invoke(std::forward<F>(f), std::forward<Tuple>(tuple), indices_for<Tuple>()); 
    } 
}; 

template<typename Functor> 
curry_type<Functor> curry(Functor&& functor) 
{ return { std::forward<Functor>(functor), {} }; } 

El código anterior compila utilizando una instantánea de GCC 4.8 (salvo errores de copia y pegar), siempre que hay un tipo indices y una utilidad de indices_for. This question y su respuesta demuestra la necesidad y la implementación de tales cosas, donde seq desempeña el papel de indices y gens se puede utilizar para implementar un (más conveniente) indices_for.

Se tiene mucho cuidado en lo anterior cuando se trata de la categoría de valor y la duración de (posibles) temporales. curry (y el tipo que lo acompaña, que es un detalle de implementación) está diseñado para ser lo más liviano posible a la vez que lo hace muy, muy seguro de usar. En particular, el uso de tales como:

foo a; 
bar b; 
auto f = [](foo a, bar b, baz c, int) { return quux(a, b, c); }; 
auto curried = curry(f); 
auto pass = curried(a); 
auto some = pass(b); 
auto parameters = some(baz {}); 
auto result = parameters(0); 

no copia f, a o b; ni resulta en referencias pendientes a los temporales. Todo esto sigue siendo cierto incluso si auto se sustituye por auto&& (suponiendo que quux está en su sano juicio, pero eso está más allá del control de curry). Todavía es posible generar diferentes políticas al respecto (por ejemplo, decadencia sistemática).

Tenga en cuenta que los parámetros (pero no el funtor) se pasan con la misma categoría de valor en la llamada final que cuando se pasan a la envoltura curry. De ahí que en

auto functor = curry([](foo f, int) {}); 
auto curried = functor(foo {}); 
auto r0 = curried(0); 
auto r1 = curried(1); 

esto significa que se pasa a la funtor subyacente al calcular r1 un trasladó-de foo.

Answer 4

Con algunas características de C++ 14, la aplicación parcial que funciona en lambda se puede implementar de una manera bastante concisa.

template<typename _function, typename _val> 
auto partial(_function foo, _val v) 
{ 
    return 
    [foo, v](auto... rest) 
    { 
     return foo(v, rest...); 
    }; 
} 

template< typename _function, typename _val1, typename... _valrest > 
auto partial(_function foo, _val1 val, _valrest... valr) 
{ 
    return 
    [foo,val,valr...](auto... frest) 
    { 
     return partial(partial(foo, val), valr...)(frest...); 
    }; 
} 

// partial application on lambda 
int p1 = partial([](int i, int j){ return i-j; }, 6)(2); 
int p2 = partial([](int i, int j){ return i-j; }, 6, 2)();