Pertanyaan Bagaimana cara melakukan currying di C ++?


Apa itu curry?

Bagaimana cara melakukan currying di C ++?

Tolong Jelaskan pengikat dalam wadah STL?


33
2017-09-30 06:51


asal


Jawaban:


Singkatnya, currying mengambil fungsi f(x, y) dan diberi tetap Y, memberi fungsi baru g(x) dimana

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

Fungsi baru ini dapat dipanggil dalam situasi di mana hanya satu argumen yang disediakan, dan meneruskan panggilan ke yang asli f berfungsi dengan tetap Y argumen.

Pengikat pada STL memungkinkan Anda melakukan ini untuk fungsi C ++. Sebagai contoh:

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

32
2017-09-30 06:59



1. Apa itu curry?

Currying berarti transformasi fungsi dari beberapa argumen ke fungsi dari argumen tunggal. Ini paling mudah diilustrasikan menggunakan contoh:

Ambil sebuah fungsi f yang menerima tiga argumen:

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

Jika kami ingin menelepon f, kami harus memberikan semua argumennya f(1,"some string",19.7f).

Kemudian versi kari dari f, sebut saja curried_f=curry(f) hanya mengharapkan satu argumen, yang sesuai dengan argumen pertama f, yaitu argumen a. Selain itu, f(1,"some string",19.7f) juga bisa ditulis menggunakan versi curried as curried_f(1)("some string")(19.7f). Nilai kembalian dari curried_f(1) di sisi lain hanyalah fungsi lain, yang menangani argumen berikutnya f. Pada akhirnya, kita berakhir dengan suatu fungsi atau dapat dipanggil curried_f yang memenuhi persamaan berikut:

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

2. Bagaimana cara mengeringkan dapat dicapai dalam C ++?

Berikut ini sedikit lebih rumit, tetapi bekerja sangat baik untuk saya (menggunakan c ++ 11) ... Ini juga memungkinkan currying dari gelar arbitrer seperti: auto curried=curry(f)(arg1)(arg2)(arg3) dan kemudian auto result=curried(arg4)(arg5). Ini dia:

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

Lihat keluaran

OK, seperti komentar Samer, saya harus menambahkan beberapa penjelasan tentang bagaimana ini bekerja. Implementasi yang sebenarnya dilakukan di _dtl::_curry, sementara fungsi template curry hanya pembungkus kenyamanan. Implementasinya bersifat rekursif atas argumen dari std::function argumen template FUNCTION.

Untuk fungsi hanya dengan satu argumen, hasilnya identik dengan fungsi aslinya.

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

Di sini hal yang rumit: Untuk fungsi dengan lebih banyak argumen, kami mengembalikan lambda yang argumennya terikat pada argumen pertama untuk panggilan ke fun. Akhirnya, sisa curry untuk sisanya N-1 argumen didelegasikan kepada implementasi _curry<Ts...> dengan satu argumen template yang kurang.

Pembaruan untuk c ++ 14/17:

Sebuah ide baru untuk mendekati masalah currying baru saja datang kepada saya ... Dengan diperkenalkannya if constexpr ke c ++ 17 (dan dengan bantuan void_t untuk menentukan apakah suatu fungsi sepenuhnya dikeringkan), hal-hal menjadi jauh lebih mudah:

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

Lihat kode beraksi sini. Dengan pendekatan yang serupa, sini adalah cara menjaring fungsi dengan sejumlah argumen sembarang.

Ide yang sama tampaknya berhasil juga dalam C ++ 14, jika kita bertukar constexpr if dengan pemilihan template tergantung pada tes 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);
}

43
2017-11-05 22:29



Menyederhanakan contoh Gregg, menggunakan 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)
}

Komponen fungsional Tr1 memungkinkan Anda menulis kode gaya fungsional yang kaya dalam C ++. Selain itu, C ++ 0x akan memungkinkan fungsi lambda in-line untuk melakukan ini juga:

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

Dan sementara C + + tidak memberikan analisis efek samping yang kaya bahwa beberapa bahasa pemrograman fungsional-berorientasi melakukan, analisis const dan sintaks lambda C ++ 0x dapat membantu:

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

Semoga itu membantu.


17
2017-10-01 23:53



Silahkan lihat Boost.Bind yang membuat proses yang ditunjukkan oleh Greg lebih fleksibel:

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

Ini mengikat 5 untuk fargumen kedua.

Perlu dicatat bahwa ini tidak currying (sebagai gantinya, itu sebagian aplikasi). Namun, menggunakan currying dengan cara umum adalah sulit dalam C ++ (sebenarnya, ini baru-baru ini menjadi mungkin sama sekali) dan aplikasi parsial sering digunakan sebagai gantinya.


11
2017-09-30 08:44



Jawaban lain dengan baik menjelaskan pengikat, jadi saya tidak akan mengulangi bagian itu di sini. Saya hanya akan mendemonstrasikan bagaimana pengolesan dan aplikasi parsial dapat dilakukan dengan lambdas di C ++ 0x.

Contoh kode: (Penjelasan dalam komentar)

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

9
2018-05-26 11:49



Jika Anda menggunakan C ++ 14 itu sangat mudah:

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

Anda kemudian dapat menggunakannya seperti ini:

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

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

add4(6); // 10

8
2017-10-06 10:06



Currying adalah cara mengurangi fungsi yang mengambil beberapa argumen ke dalam urutan fungsi bersarang dengan satu argumen masing-masing:

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 bagus karena Anda dapat mendefinisikan fungsi yang hanya merupakan pembungkus di sekitar fungsi lain dengan nilai yang telah ditentukan, dan kemudian meneruskan fungsi yang disederhanakan. Pengikat C ++ STL menyediakan implementasi ini di C ++.


6
2017-09-30 07:00



Beberapa jawaban yang bagus di sini. Saya pikir saya akan menambahkan sendiri karena itu menyenangkan untuk bermain-main dengan konsep itu.

Aplikasi fungsi parsial: Proses "mengikat" suatu fungsi hanya dengan beberapa parameternya, menunda sisanya untuk diisi nanti. Hasilnya adalah fungsi lain dengan lebih sedikit parameter.

Currying: Apakah bentuk khusus dari aplikasi fungsi parsial di mana Anda hanya dapat "mengikat" satu argumen pada suatu waktu. Hasilnya adalah fungsi lain dengan tepat 1 parameter lebih sedikit.

Kode yang akan saya presentasikan adalah aplikasi fungsi parsial dari mana currying dimungkinkan, tetapi bukan satu-satunya kemungkinan. Ini menawarkan beberapa manfaat di atas implementasi currying (terutama karena aplikasi fungsi parsial dan bukan currying, heh).

  • Menerapkan fungsi yang kosong:

    auto sum0 = [](){return 0;};
    std::cout << partial_apply(sum0)() << std::endl;
    
  • Menerapkan banyak argumen sekaligus:

    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 dukungan yang memungkinkan untuk waktu kompilasi static_assert:

    static_assert(partial_apply(sum0)() == 0);
    
  • Pesan kesalahan yang berguna jika Anda secara tidak sengaja bertindak terlalu jauh dalam memberikan argumen:

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

    kesalahan: static_assert gagal "Mencoba menerapkan terlalu banyak argumen!"

Jawaban lain di atas mengembalikan lambdas yang mengikat argumen dan kemudian mengembalikan lambdas lebih lanjut. Pendekatan ini membungkus fungsionalitas penting itu menjadi objek yang dapat dipanggil. Definisi untuk operator() biarkan lambda internal dipanggil. Template variadic memungkinkan kita untuk memeriksa seseorang yang terlalu jauh, dan fungsi konversi implisit ke jenis hasil dari pemanggilan fungsi memungkinkan kita untuk mencetak hasil atau membandingkan objek dengan primitif.

Kode:

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 Live

Beberapa catatan lagi:

  • Saya memilih untuk menggunakan is_detected terutama untuk kesenangan dan latihan; itu berfungsi sama dengan sifat tipe normal di sini.
  • Pasti ada lebih banyak pekerjaan yang dilakukan untuk mendukung penyampaian sempurna untuk alasan kinerja
  • Kode ini C ++ 17 karena diperlukan untuk constexpr dukungan lambda dalam C ++ 17
    • Dan tampaknya GCC 7.0.1 juga belum ada di sana, jadi saya menggunakan Clang 5.0.0

Beberapa tes:

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

4
2018-03-31 02:09



Saya menerapkan currying dengan template variadic juga (lihat jawaban Julian). Namun, saya tidak menggunakan rekursi atau std::function. Catatan: Ini menggunakan sejumlah C ++ 14 fitur.

Contoh yang disediakan (main fungsi) benar-benar berjalan pada waktu kompilasi, membuktikan bahwa metode currying tidak mengalahkan optimasi penting oleh compiler.

Kode dapat ditemukan di sini: https://gist.github.com/Garciat/c7e4bef299ee5c607948

dengan file helper ini: https://gist.github.com/Garciat/cafe27d04cfdff0e891e

Kode masih membutuhkan (banyak) pekerjaan, yang saya mungkin atau mungkin tidak akan selesai segera. Either way, saya posting ini di sini untuk referensi di masa mendatang.

Kode posting jika tautan mati (meskipun seharusnya tidak):

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

3
2018-01-02 01:24



Tautan ini relevan:

Halaman Kalkulus Lambda di Wikipedia memiliki contoh yang jelas tentang currying
http://en.wikipedia.org/wiki/Lambda_calculus#Motivation

Makalah ini memperlakukan currying dalam C / C ++
http://asg.unige.ch/site/papers/Dami91a.pdf


2
2017-10-29 18:19