Comment faire pour currying en C ++?

https://stackoverflow.com/questions/152005

02-07-2019
|

Question

Qu'est-ce que le currying?

Comment currying peut-il être fait en C ++?

Veuillez expliquer les classeurs dans le conteneur STL?

La solution

En bref, le curry prend une fonction f(x, y) et donne un Y fixe, donne une nouvelle fonction g(x) où

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

Cette nouvelle fonction peut être appelée dans les cas où un seul argument est fourni et transmet l'appel à la fonction f d'origine avec l'argument <=> fixe.

Les classeurs de la STL vous permettent de le faire pour les fonctions C ++. Par exemple:

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

Autres conseils

1. Qu'est-ce que le currying?

Curry signifie simplement la transformation d’une fonction de plusieurs arguments en une fonction d’un seul argument. Ceci est plus facilement illustré à l'aide d'un exemple:

Prenez une fonction f qui accepte trois arguments:

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

Si nous voulons appeler f(1,"some string",19.7f), nous devons fournir tous ses arguments curried_f=curry(f).

Ensuite, une version curry de a, appelons-la curried_f(1)("some string")(19.7f), attend un seul argument, qui correspond au premier argument de curried_f(1), à savoir l'argument curried_f. De plus, auto curried=curry(f)(arg1)(arg2)(arg3) peut également être écrit en utilisant la version au curry comme auto result=curried(arg4)(arg5). Par contre, la valeur de retour de _dtl::_curry n'est qu'une autre fonction, qui gère l'argument suivant de curry. Au final, on se retrouve avec une fonction ou appelable std::function qui remplit l’égalité suivante:

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

2. Comment réaliser un currying en C ++?

Ce qui suit est un peu plus compliqué, mais fonctionne très bien pour moi (avec c ++ 11) ... Il permet également de traiter des degrés arbitraires comme ceci: FUNCTION et plus tard fun. Le voici:

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

Afficher le résultat

OK, comme l'a commenté Samer, je devrais ajouter quelques explications sur la façon dont cela fonctionne. L'implémentation réelle est effectuée dans N-1, tandis que les fonctions de modèle _curry<Ts...> ne sont que des wrappers pratiques. L'implémentation est récursive sur les arguments du if constexpr argument de modèle void_t.

Pour une fonction avec un seul argument, le résultat est identique à la fonction d'origine.

        _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;
            }
        ) {}

Ici, la chose la plus délicate: pour une fonction avec plus d’arguments, nous retournons un lambda dont l’argument est lié au premier argument de l’appel à constexpr if. Enfin, le currying restant pour les needs_unapply<decltype(f)>::value arguments restants est délégué à la mise en oeuvre de <=> avec un argument de modèle de moins.

Mise à jour pour c ++ 14/17:

Une nouvelle idée pour aborder le problème du curry vient de m’être venue ... Avec l’introduction de <=> dans c ++ 17 (et avec l’aide de <=> pour déterminer si une fonction est complètement curry), les choses semblent devenir beaucoup plus faciles:

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

Voir le code en action à la ici . Avec une approche similaire, voici comment utiliser les fonctions avec un nombre arbitraire d'arguments.

La même idée semble fonctionner également en C ++ 14, si nous échangeons le <=> avec une sélection de modèle en fonction du test <=>:

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

Simplifier l'exemple de Gregg en utilisant 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)
}

Les composants fonctionnels Tr1 vous permettent d’écrire un code de style fonctionnel riche en C ++. De même, C ++ 0x permettra aux fonctions lambda en ligne de le faire aussi:

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

Et bien que C ++ ne fournisse pas la riche analyse des effets secondaires effectuée par certains langages de programmation orientés fonctionnels, l'analyse const et la syntaxe lambda C ++ 0x peuvent aider:

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

L’espoir que cela aide.

Découvrez Boost.Bind . ce qui rend le processus présenté par Greg plus polyvalent:

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

Ceci lie 5 au second argument de f.

Cela & # 8217; vaut la peine de noter que ceci n’est pas currying (à la place, c’est une application partielle de & # 8217;). Cependant, utiliser le curry de manière générale est difficile en C ++ (en fait, cela n’a été possible que récemment) et une application partielle est souvent utilisée à la place.

Les autres réponses expliquent bien les classeurs, je ne vais donc pas répéter cette partie-là. Je ne ferai que démontrer comment une application partielle et curry peut être réalisée avec lambdas en C ++ 0x.

Exemple de code: (explication dans les commentaires)

#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 vous utilisez C ++ 14, c'est très simple:

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

Vous pouvez ensuite l'utiliser comme ceci:

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

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

add4(6); // 10

Le curry est un moyen de réduire une fonction qui prend plusieurs arguments en une séquence de fonctions imbriquées avec un argument chacun:

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

Currying est agréable parce que vous pouvez définir des fonctions qui enveloppent simplement d’autres fonctions avec des valeurs prédéfinies, puis vous transmettent les fonctions simplifiées. Les classeurs C ++ STL fournissent une implémentation de cela en C ++.

Quelques bonnes réponses ici. Je pensais ajouter le mien car c’était amusant de jouer avec le concept.

Application de fonction partielle : processus de " liaison " une fonction avec seulement certains de ses paramètres, différant le reste pour qu'il soit rempli ultérieurement. Le résultat est une autre fonction avec moins de paramètres.

Currying : il s'agit d'une forme spéciale d'application de fonction partielle dans laquelle vous pouvez uniquement & "lier &"; un seul argument à la fois. Le résultat est une autre fonction avec exactement 1 paramètre de moins.

Le code que je vais vous présenter est la application de fonction partielle à partir de laquelle le currying est possible, mais pas la seule possibilité. Il offre quelques avantages par rapport aux implémentations de curry ci-dessus (principalement parce qu’il s’agit d’une application de fonction partielle et non de curry, heh).

Application sur une fonction vide:

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

Application de plusieurs arguments à la fois:

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 supportant le temps de compilation static_assert:
```
static_assert(partial_apply(sum0)() == 0);
```
Un message d'erreur utile si vous allez accidentellement trop loin en fournissant des arguments:
```
auto sum1 = [](int x){ return x;};
partial_apply(sum1)(1)(1);
```
erreur: static_assert a échoué & "Tentative d'appliquer trop d'arguments! &";

D'autres réponses ci-dessus renvoient des lambdas qui lient un argument, puis renvoient d'autres lambdas. Cette approche englobe cette fonctionnalité essentielle dans un objet appelable. Les définitions de operator() permettent d’appeler le lambda interne. Les modèles variés nous permettent de vérifier si quelqu'un va trop loin, et une fonction de conversion implicite en type de résultat de l'appel de fonction nous permet d'imprimer le résultat ou de comparer l'objet à une primitive.

Code:

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

démonstration en direct

Quelques notes supplémentaires:

J'ai choisi d'utiliser is_detected principalement pour le plaisir et la pratique; il sert ici comme un trait de caractère normal ici.
Il pourrait certainement y avoir davantage de travail pour soutenir une transmission parfaite pour des raisons de performance
Le code est C ++ 17 car il nécessite le <=> support lambda in C ++ 17
- Et il semble que GCC 7.0.1 ne soit pas encore tout à fait là, alors j’ai utilisé Clang 5.0.0

Quelques tests:

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

J'ai également implémenté le currying avec des modèles variadiques (voir la réponse de Julian). Cependant, je n’ai pas utilisé la récursivité ou std::function. Remarque: Il utilise un certain nombre de fonctionnalités C ++ 14 .

L'exemple fourni (main fonction) s'exécute en fait au moment de la compilation, ce qui prouve que la méthode de currying ne l'emporte pas sur les optimisations essentielles du compilateur.

Le code peut être trouvé ici: https://gist.github.com/Garciat/c7e4bef299ee5c607948"/ a>

avec ce fichier d'assistance: https://gist.github.com/Garciat/cafe27d04cfdff0e891e

Le code a encore besoin de (beaucoup) de travail, que je pourrais ou non terminer bientôt. Quoi qu'il en soit, je publie ce message ici pour référence future.

Code de publication dans le cas où les liens meurent (bien qu'ils ne devraient pas le faire):

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

Ces liens sont pertinents:

La page Lambda Calculus sur Wikipedia contient un exemple clair de currying
http://fr.wikipedia.org/wiki/Lambda_calculus#Motivation

Cet article traite du currying en C / C ++
http://asg.unige.ch/site/papers/Dami91a.pdf

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow