C ++でカレーを実行するにはどうすればよいですか?
-
02-07-2019 - |
質問
カレーとは何ですか?
C ++でカレーを行うにはどうすればよいですか
STLコンテナのバインダーについて説明してください
解決
要するに、カリー化は関数f(x, y)
を取り、固定のY
が与えられると、新しい関数g(x)
where
g(x) == f(x, Y)
この新しい関数は、引数が1つだけ指定されている場合に呼び出すことができ、固定のf
引数を使用して元の<=>関数に呼び出しを渡します。
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。カレーとは?
Curryingとは、複数の引数の関数を単一の引数の関数に変換することを意味します。これは、例を使用して最も簡単に説明できます。
3つの引数を受け入れる関数f
を取得します。
int
f(int a,std::string b,float c)
{
// do something with a, b, and c
return 0;
}
f(1,"some string",19.7f)
を呼び出したい場合は、その引数curried_f=curry(f)
をすべて指定する必要があります。
a
のカリー化されたバージョン、curried_f(1)("some string")(19.7f)
と呼びましょう。curried_f(1)
の最初の引数、つまり引数curried_f
に対応する単一の引数のみが必要です。さらに、カリー化されたバージョンをauto curried=curry(f)(arg1)(arg2)(arg3)
として使用してauto result=curried(arg4)(arg5)
を記述することもできます。一方、_dtl::_curry
の戻り値は別の関数であり、curry
の次の引数を処理します。最終的に、次の等式を満たす関数または呼び出し可能std::function
になります。
curried_f(first_arg)(second_arg)...(last_arg) == f(first_arg,second_arg,...,last_arg).
2。カレーはC ++でどのように達成できますか?
以下は少し複雑ですが、私にとっては非常にうまく機能します(c ++ 11を使用)...また、FUNCTION
以降のfun
のように任意の程度のカリー化も可能です。ここにあります:
#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;
}
OK、サマーがコメントしたように、これがどのように機能するかについての説明を追加する必要があります。実際の実装はN-1
で行われますが、テンプレート関数_curry<Ts...>
は単なる便利なラッパーです。実装は、if constexpr
テンプレート引数void_t
の引数に対して再帰的です。
引数が1つだけの関数の場合、結果は元の関数と同じです。
_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;
}
) {}
ここで注意が必要なこと:より多くの引数を持つ関数の場合、引数がconstexpr if
への呼び出しの最初の引数にバインドされているラムダを返します。最後に、残りのneeds_unapply<decltype(f)>::value
引数の残りのカリー化は、テンプレート引数が1つ少ない<=>の実装に委任されます。
c ++ 14/17の更新:
カリー化の問題にアプローチするための新しいアイデアが思いついた... <=>をc ++ 17に導入して(そして<=>の助けを借りて、関数が完全にカリー化されているかどうかを判断して)物事はずっと簡単になりそうです:
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でもうまくいくようです:
:
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:を使用してGreggの例を単純化する
#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では、インラインラムダ関数でも同様にこれを行うことができます。
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ラムダ構文は役立ちます:
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 をご覧くださいこれにより、Gregが示すプロセスの汎用性が高まります。
transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));
これは、5
をf
の2番目の引数にバインドします。
It <!>#8217;これはカレーではない ことに注意する価値があります(代わりに、it <!>#8217;の部分的なアプリケーションです)。ただし、C ++ではカレーを一般的な方法で使用するのは難しく(実際、ごく最近になって初めて可能になりました)、代わりに部分的なアプリケーションがよく使用されます。
その他の回答はバインダーをうまく説明しているので、ここではその部分を繰り返しません。 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は、複数の引数を取る関数を、それぞれ1つの引数を持つネストされた関数のシーケンスに縮小する方法です。
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 ++で実装します。
ここにいくつかの素晴らしい答えがあります。コンセプトをいじってみるのは楽しかったので、自分で追加すると思いました。
部分関数アプリケーション:<!> quot; binding <!> quot;いくつかのパラメータのみを持つ関数で、残りは後で入力するのを延期します。結果は、より少ないパラメーターを持つ別の関数です。
カリー:<!> quot; bind <!> quot;一度に1つの引数。結果は、パラメーターが1つ少ない別の関数です。
これから紹介するコードは、部分関数アプリケーションであり、そこからカレーが可能ですが、唯一の可能性はありません。上記のカリー化の実装よりもいくつかの利点があります(主にカリー化ではなく、部分的な関数アプリケーションであるためです)。
-
空の関数への適用:
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);
error:static_assert failed <!> quot;多すぎる引数を適用しようとしています!<!> quot;
上記の他の答えは、引数をバインドするラムダを返し、さらにラムダを返します。このアプローチは、その重要な機能を呼び出し可能なオブジェクトにラップします。 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;
};
ライブデモ
その他の注意事項:
- 主に楽しみと練習のために、 is_detected を使用することにしました。ここで通常の型特性と同じ働きをします。
- パフォーマンス上の理由から完全な転送をサポートするために、さらに多くの作業が行われる可能性があります
- <=>ラムダサポート inが必要なため、コードはC ++ 17です。 C ++ 17
- そして、GCC 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
可変個引数テンプレートを使用したカリー化も実装しました(Julianの回答を参照)。ただし、再帰またはstd::function
を使用しませんでした。注:多くの C ++ 14 機能を使用します。
提供された例(main
関数)は実際にコンパイル時に実行され、カリー化メソッドがコンパイラーによる本質的な最適化に勝るものではないことを証明しています。
コードは次の場所にあります: 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