Wie kann currying in C ++ zu tun?

StackOverflow https://stackoverflow.com/questions/152005

Frage

Was ist currying?

Wie kann currying in C ++ durchgeführt werden?

Bitte beschreiben Bindemittel in STL-Containern?

War es hilfreich?

Lösung

Kurz gesagt, currying eine Funktion f(x, y) nimmt und bei einer festen Y, gibt eine neue Funktion g(x) wobei 

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

Diese neue Funktion in Situationen genannt werden, in denen nur ein Argument angegeben ist, und leitet den Aufruf an die ursprünglichen Funktion f mit dem festen Y Argumente.

Die Bindemittel in der STL können Sie diese Funktionen ++ für C tun. Zum Beispiel: 

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

Andere Tipps

1. Was ist currying?

Currying bedeutet einfach, eine Transformation einer Funktion mehrerer Argumente zu einer Funktion eines einzigen Argument. Dies geschieht am einfachsten dargestellt anhand eines Beispiels:

Nehmen Sie eine Funktion f die drei Argumente akzeptiert: 

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

Wenn wir f anrufen wollen, müssen wir alle seine Argumente f(1,"some string",19.7f) zur Verfügung zu stellen.

Dann wird eine curried Version von f, nennen wir es curried_f=curry(f) erwartet nur ein einziges Argument, das auf das erste Argument von f entspricht, nämlich dem Argument a. Zusätzlich f(1,"some string",19.7f) können auch die curried Version als curried_f(1)("some string")(19.7f) geschrieben werden. Der Rückgabewert von curried_f(1) auf der anderen Seite ist nur eine andere Funktion, die das nächste Argument von f behandelt. Am Ende haben wir am Ende mit einer Funktion oder kündbare curried_f, die folgende Gleichheit erfüllt: 

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

2. Wie kann currying in C ++ erreicht werden?

Im folgenden ein wenig komplizierter ist, funktioniert aber sehr gut für mich (C ++ 11) ... Es ermöglicht auch currying beliebigen Grades in etwa so: auto curried=curry(f)(arg1)(arg2)(arg3) und später auto result=curried(arg4)(arg5). Hier geht es: 

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

Ansicht Ausgabe

OK, so Samer kommentiert, sollte ich einige Erklärungen hinzufügen, wie dies funktioniert. Die tatsächliche Umsetzung ist in der _dtl::_curry getan, während die Template-Funktionen curry nur sind Convenience-Wrapper. Die Implementierung ist rekursiv über die Argumente der std::function Template-Argument FUNCTION.

Für eine Funktion mit nur einem einzigen Argumente, das Ergebnis ist identisch mit der ursprünglichen Funktion. 

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

Hier ist die heikle Sache: Für eine Funktion mit mehreren Argumenten, kehren wir ein Lambda dessen Argument auf das erste Argument auf den Anruf gebunden ist, fun. Schließlich wird das verbleibende currying für die verbleibenden N-1 Argumente für die Umsetzung der _curry<Ts...> mit einem weniger Template-Argumente delegiert.

Update für c ++ 14/17:

Eine neue Idee, das Problem der zu nähern currying nur kam zu mir ... Mit der Einführung von if constexpr in c ++ 17 (und mit Hilfe von void_t, um zu bestimmen, ob eine Funktion vollständig curried ist), scheinen die Dinge zu bekommen viel einfacher: 

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

Siehe Code in Aktion auf hier . Mit einem ähnlichen Ansatz rel="noreferrer"> ist, wie Funktionen Curry mit beliebiger Anzahl von Argumenten.

Die gleiche Idee scheint auch ++ 14 in C arbeiten, wenn wir die constexpr if mit einer Template-Auswahl je nach Test needs_unapply<decltype(f)>::value austauschen: 

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

Vereinfachen Greggs Beispiel mit 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)
}

Tr1 funktionale Komponenten können Sie reichen funktionellen Stil Code in C ++ schreiben. Wie gut, C ++ 0x kann für in-line Lambda-Funktionen, dies auch tun: 

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

Und während C ++ bietet keine reiche Nebeneffekt Analyse, dass einige Funktionsorientierten Programmiersprachen durchführen, Konst Analyse und C ++ 0x Lambda-Syntax helfen kann: 

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

Ich hoffe, das hilft.

Hier finden Sie aktuelle Boost.Bind das macht den Prozess von Greg gezeigt vielseitiger: 

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

Dies bindet 5 zu f zweiten Argumente.

Es ist erwähnenswert, dass dies nicht currying (statt, dann ist es teilweise Anwendung). Jedoch in allgemeiner Weise mit currying ist schwer in C ++ (in der Tat, es erst seit kurzem möglich, wurde überhaupt) und teilweise Anwendung wird häufig verwendet, statt.

Andere Antworten gut erklären Bindemittel, so dass ich diesen Teil hier nicht wiederholen. Ich will nur zeigen, wie Striegeln und partielle Anwendung kann mit Lambda-Ausdrücke in C ++ 0x erfolgen.

Code-Beispiel: (Erklärung in den Kommentaren) 

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

Wenn Sie mit 14 C ++ ist es sehr einfach: 

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

Sie können dann wie folgt verwenden: 

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

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

add4(6); // 10

Currying ist ein Weg, um eine Funktion der Reduzierung, die mehrere Argumente in eine Folge von verschachtelten Funktionen mit einem Argument nimmt jeder: 

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 ist nett, weil Sie Funktionen zu definieren, die einfach Wrapper mit vordefinierten Werten um andere Funktionen sind, und dann um die vereinfachten Funktionen übergeben. C ++ STL Bindemittel bieten eine Implementierung dieser in C ++.

Einige große Antworten hier. Ich dachte, ich würde meine eigenen hinzufügen, weil es Spaß war mit dem Konzept zu spielen, um.

Teilfunktion Anwendung : Der Prozess der „Bindung“ eine Funktion mit nur einige Parameter, einen Aufschub, den Rest später ausgefüllt werden. Das Ergebnis ist eine weitere Funktion mit weniger Parameter.

Currying : Ist eine spezielle Form der Teilfunktion Anwendung, wo man nur „binden“ ein einziges Argument zu einer Zeit. Das Ergebnis ist eine weitere Funktion mit genau 1 weniger Parameter.

Der Code, den ich bin zu präsentieren, ist Teilfunktion Anwendung aus dem currying möglich ist, aber nicht die einzige Möglichkeit. Es bietet einige Vorteile gegenüber dem oben currying Implementierungen (vor allem, weil es teilweise Funktionsanwendung und nicht currying, heh).

  • Die Anwendung über eine leere Funktion: 

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

  • Die Anwendung mehr Argumente zu einer Zeit: 

    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 Unterstützung, die für die Kompilierung-static_assert erlaubt: 

    static_assert(partial_apply(sum0)() == 0);

  • Eine nützliche Fehlermeldung, wenn Sie versehentlich bei der Bereitstellung von Argumenten zu weit gehen: 

    auto sum1 = [](int x){ return x;};
partial_apply(sum1)(1)(1);
      

    Fehler: static_assert fehlgeschlagen "zu viele Argumente anwenden Versuch!"

Andere Antworten über Rückkehr Lambdas, die ein Argument binden und dann wieder weiter lambda. Dieser Ansatz hüllt, dass wesentliche Funktionen in einem abrufbaren Objekt. Definitionen für operator() erlauben die interne Lambda genannt werden. Variadische Vorlagen ermöglichen es uns, für jemand zu weit zu gehen, und eine implizite Konvertierungsfunktion zum Ergebnistyp des Funktionsaufrufes überprüfen ermöglicht es uns, das Ergebnis zu drucken oder das Objekt zu einem primitiven vergleichen.

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

Live Demo

Noch ein paar Anmerkungen:

  • Ich entschied mich für die Verwendung is_detected hauptsächlich für Genuss und Praxis; es dient das gleiche wie ein normaler Typ Merkmal würde hier.
  • Es auf jeden Fall mehr Arbeit getan werden könnte perfekt Weiterleitung aus Leistungsgründen
    • Unterstützung
  • Der Code ist C ++ 17, weil es für constexpr Lambda-Unterstützung erfordert in C + +17
    • Und es scheint, dass GCC 7.0.1 ist noch nicht so weit, entweder, so habe ich Clang 5.0.0

Einige 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

implementiert ich mit variadische Vorlagen currying als auch (Julian Antwort sehen). Allerdings habe ich keinen Gebrauch von Rekursion oder std::function machen. Hinweis:. Es verwendet eine Reihe von C ++ 14 Eigenschaften

Das mitgelieferte Beispiel (main Funktion) läuft tatsächlich zum Zeitpunkt der Kompilierung zu beweisen, dass die Zurichtung nicht Trumpf wesentliche Optimierungen durch den Compiler.

Der Code kann hier gefunden werden: https://gist.github.com/Garciat/c7e4bef299ee5c607948

Mit dieser Hilfsdatei: https://gist.github.com/Garciat/cafe27d04cfdff0e891e

Der Code muss noch (viel) Arbeit, die ich kann oder nicht bald abschließen können. So oder so, ich bin dies für die Zukunft hier veröffentlichen.

Buchungscode bei Links sterben (obwohl sie es nicht soll): 

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

Diese Links sind relevant:

Die Lambda-Kalküls Seite auf Wikipedia hat ein klares Beispiel für currying
http://en.wikipedia.org/wiki/Lambda_calculus#Motivation

Dieses Papier behandelt currying in C / C ++
http://asg.unige.ch/site/papers/Dami91a.pdf

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top