كيف يمكن أن يتم الكاري في C++؟
-
02-07-2019 - |
سؤال
ما هو الكاري؟
كيف يمكن أن يتم الكاري في C++؟
يرجى شرح المجلدات الموجودة في حاوية STL؟
المحلول
باختصار، الكاري يأخذ وظيفة f(x, y)
وإعطاء ثابت Y
, ، يعطي وظيفة جديدة g(x)
أين
g(x) == f(x, Y)
يمكن استدعاء هذه الوظيفة الجديدة في الحالات التي يتم فيها توفير وسيطة واحدة فقط، وتمرير الاستدعاء إلى الوظيفة الأصلية f
وظيفة مع الثابتة Y
دعوى.
تسمح لك المجلدات الموجودة في STL بالقيام بذلك لوظائف C++.على سبيل المثال:
#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;
}
نصائح أخرى
1.ما هو الكاري؟
الكاري يعني ببساطة تحويل دالة من عدة وسائط إلى دالة من وسيطة واحدة.يتم توضيح ذلك بسهولة باستخدام مثال:
خذ وظيفة f
الذي يقبل ثلاث حجج:
int
f(int a,std::string b,float c)
{
// do something with a, b, and c
return 0;
}
إذا أردنا الاتصال f
, ، علينا أن نقدم جميع حججه f(1,"some string",19.7f)
.
ثم نسخة الكاري من f
, ، دعنا نسميها curried_f=curry(f)
يتوقع فقط وسيطة واحدة تتوافق مع الوسيطة الأولى لـ f
, ، أي الحجة a
.بالإضافة إلى ذلك، f(1,"some string",19.7f)
يمكن أيضًا كتابتها باستخدام النسخة الكاري كـ curried_f(1)("some string")(19.7f)
.قيمة الإرجاع curried_f(1)
من ناحية أخرى، فهي مجرد وظيفة أخرى تتعامل مع الوسيطة التالية لـ f
.في النهاية، ننتهي بوظيفة أو قابلة للاستدعاء curried_f
التي تحقق المساواة التالية:
curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg).
2.كيف يمكن تحقيق الكاري في C++؟
ما يلي أكثر تعقيدًا بعض الشيء، ولكنه يعمل جيدًا بالنسبة لي (باستخدام c++ 11)...كما يسمح أيضًا بالكاري بدرجة تعسفية مثل: auto curried=curry(f)(arg1)(arg2)(arg3)
و لاحقا auto result=curried(arg4)(arg5)
.من هنا تبدأ:
#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;
}
حسنًا، كما علق سامر، يجب أن أضيف بعض التوضيحات حول كيفية عمل ذلك.التنفيذ الفعلي يتم في _dtl::_curry
, ، بينما يعمل القالب curry
هي مجرد أغلفة الراحة.التنفيذ متكرر على حجج std::function
حجة القالب FUNCTION
.
بالنسبة للدالة التي تحتوي على وسيطة واحدة فقط، تكون النتيجة مطابقة للدالة الأصلية.
_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;
}
) {}
وهنا الأمر الصعب:بالنسبة إلى دالة تحتوي على المزيد من الوسائط، نعيد لامدا التي ترتبط حجتها بالوسيطة الأولى لاستدعاءها fun
.أخيرا، الكاري المتبقي للباقي N-1
يتم تفويض الحجج لتنفيذ _curry<Ts...>
مع وسيطة قالب واحدة أقل.
التحديث لـ c++ 14/17:
خطرت في بالي فكرة جديدة لحل مشكلة الكاري...مع مقدمة if constexpr
إلى c++ 17 (وبمساعدة void_t
لتحديد ما إذا كانت الوظيفة قد تم إنجازها بالكامل)، يبدو أن الأمور أصبحت أسهل كثيرًا:
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);
}
راجع التعليمات البرمجية قيد التنفيذ على هنا.وبمنهج مماثل، هنا هي كيفية دمج الوظائف مع عدد عشوائي من الوسائط.
يبدو أن نفس الفكرة تعمل أيضًا في C++ 14، إذا قمنا بتبادل constexpr if
مع اختيار القالب اعتمادا على الاختبار 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);
}
تبسيط مثال جريج باستخدام 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 كتابة تعليمات برمجية ذات نمط وظيفي غني بلغة C++.كذلك، سيسمح C++0x لوظائف lambda المضمنة بالقيام بذلك أيضًا:
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)
}
وعلى الرغم من أن C++ لا توفر التحليل الغني للتأثيرات الجانبية الذي تؤديه بعض لغات البرمجة ذات التوجه الوظيفي، إلا أن تحليل const وبناء جملة C++0x lambda يمكن أن يساعد:
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.
}
امل ان يساعد.
القي نظرة على Boost.Bind مما يجعل العملية التي أظهرها جريج أكثر تنوعًا:
transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));
هذا يربط 5
ل f
الحجة الثانية.
ومن الجدير بالذكر أن هذا هو لا الكاري (بدلاً من ذلك، هو تطبيق جزئي).ومع ذلك، فإن استخدام الكاري بطريقة عامة أمر صعب في لغة C++ (في الواقع، أصبح هذا ممكنًا مؤخرًا فقط) وغالبًا ما يتم استخدام التطبيق الجزئي بدلاً من ذلك.
الإجابات الأخرى تشرح المجلدات بشكل جيد، لذلك لن أكرر هذا الجزء هنا.سأوضح فقط كيف يمكن إجراء الكاري والتطبيق الجزئي باستخدام lambdas في C++ 0x.
مثال الكود: (الشرح في التعليقات)
#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
}
إذا كنت تستخدم C++ 14 فالأمر سهل للغاية:
template<typename Function, typename... Arguments>
auto curry(Function function, Arguments... args) {
return [=](auto... rest) {
return function(args..., rest...);
}
}
يمكنك بعد ذلك استخدامه مثل هذا:
auto add = [](auto x, auto y) { return x + y; }
// curry 4 into add
auto add4 = curry(add, 4);
add4(6); // 10
Currying هي طريقة لتقليل دالة تأخذ وسائط متعددة في سلسلة من الوظائف المتداخلة مع وسيطة واحدة لكل منها:
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 أمرًا رائعًا لأنه يمكنك تعريف الوظائف التي هي ببساطة ملتفة حول وظائف أخرى ذات قيم محددة مسبقًا، ثم تمرير الوظائف المبسطة.توفر مجلدات C++ STL تطبيقًا لهذا في C++.
بعض الإجابات الرائعة هنا.اعتقدت أنني سأضيف فكرتي الخاصة لأنه كان من الممتع تجربة هذا المفهوم.
تطبيق وظيفة جزئية:عملية "ربط" دالة ببعض معلماتها فقط، وتأجيل الباقي ليتم ملؤه لاحقًا.والنتيجة هي دالة أخرى ذات معلمات أقل.
الكاري:هو شكل خاص من تطبيقات الوظائف الجزئية حيث يمكنك فقط "ربط" وسيطة واحدة في كل مرة.والنتيجة هي دالة أخرى بمعلمة واحدة أقل بالضبط.
الكود الذي أنا على وشك تقديمه هو تطبيق وظيفة جزئية من الممكن الكاري، ولكن ليس الاحتمال الوحيد.إنه يقدم بعض الفوائد مقارنة بتطبيقات الكاري المذكورة أعلاه (يرجع ذلك أساسًا إلى أنه تطبيق وظيفي جزئي وليس كاري، هيه).
التقديم على دالة فارغة:
auto sum0 = [](){return 0;}; std::cout << partial_apply(sum0)() << std::endl;
تطبيق وسائط متعددة في وقت واحد:
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
الدعم الذي يسمح بوقت الترجمةstatic_assert
:static_assert(partial_apply(sum0)() == 0);
رسالة خطأ مفيدة إذا ذهبت بعيدًا عن طريق الخطأ في تقديم الوسائط:
auto sum1 = [](int x){ return x;}; partial_apply(sum1)(1)(1);
خطأ:فشل static_assert "محاولة تطبيق عدد كبير جدًا من الوسائط!"
الإجابات الأخرى أعلاه تُرجع lambdas التي تربط الوسيطة ثم تُرجع المزيد من lambdas.يقوم هذا الأسلوب بتغليف هذه الوظيفة الأساسية في كائن قابل للاستدعاء.تعريفات ل operator()
السماح باستدعاء لامدا الداخلي.تتيح لنا القوالب المتغيرة التحقق مما إذا كان شخص ما قد تجاوز الحد، وتسمح لنا دالة التحويل الضمنية لنوع نتيجة استدعاء الوظيفة بطباعة النتيجة أو مقارنة الكائن بكائن بدائي.
شفرة:
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;
};
عرض حي
بعض الملاحظات الإضافية:
- اخترت استخدام تم الكشف عن أساسا للتمتع والممارسة؛إنه يخدم نفس سمة النوع العادي هنا.
- من المؤكد أنه قد يكون هناك المزيد من العمل المنجز لدعم إعادة التوجيه المثالية لأسباب تتعلق بالأداء
- الكود هو C++ 17 لأنه يتطلب
constexpr
دعم لامدا في سي++17- ويبدو أن الإصدار 7.0.1 من مجلس التعاون الخليجي لم يصل إلى هذا الحد بعد أيضًا، لذلك استخدمت Clang 5.0.0
بعض الاختبارات:
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
لقد قمت بتطبيق الكاري باستخدام قوالب متنوعة أيضًا (انظر إجابة جوليان).ومع ذلك، لم أستفيد من العودية أو std::function
.ملحوظة:ويستخدم عددا من سي++14 سمات.
المثال المقدم (main
function) يتم تشغيلها فعليًا في وقت الترجمة، مما يثبت أن طريقة الكاري لا تتفوق على التحسينات الأساسية التي يقوم بها المترجم.
يمكن العثور على الكود هنا: https://Gist.github.com/Garciat/c7e4bef299ee5c607948
مع هذا الملف المساعد: https://Gist.github.com/Garciat/cafe27d04cfdff0e891e
لا يزال الكود بحاجة إلى (الكثير) من العمل، والذي قد أكمله أو لا أكمله قريبًا.وفي كلتا الحالتين، أنا نشر هذا هنا للرجوع إليها في المستقبل.
نشر التعليمات البرمجية في حالة موت الروابط (على الرغم من أنه لا ينبغي لها ذلك):
#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;
}
هذه الروابط ذات صلة:
تحتوي صفحة Lambda Calculus على ويكيبيديا على مثال واضح للكاري
http://en.wikipedia.org/wiki/Lambda_calculus#Motivation
تعالج هذه الورقة الكاري في C/C++
http://asg.unige.ch/site/papers/Dami91a.pdf