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 버전을 사용하여 작성할 수도 있습니다 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;
}
Samer가 언급했듯이, 나는 이것이 어떻게 작동하는지에 대한 설명을 추가해야합니다. 실제 구현은 _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을 사용하여 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 Analysis 및 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.
}
도움이되기를 바랍니다.
살펴보십시오 부스트 Greg가 보여주는 프로세스를보다 다재다능하게 만듭니다.
transform(a.begin(), a.end(), back_inserter(b), bind(f, _1, 5));
이것은 묶습니다 5
에게 f
두 번째 주장.
이것이 바로 주목할 가치가 있습니다 ~ 아니다 카레 링 (대신 부분 적용). 그러나 C ++에서는 일반적인 방식으로 카레를 사용하는 것이 어렵고 (실제로는 최근에만 가능해 졌음) 부분 적용이 종종 대신 사용됩니다.
다른 대답은 바인더를 잘 설명하므로 여기에서 그 부분을 반복하지 않을 것입니다. C ++ 0x에서 Lambdas로 카레와 부분 적용을 수행 할 수있는 방법 만 보여줍니다.
Code example: (의견에 대한 설명)
#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
카레는 여러 인수를 각각 하나의 인수로 중첩 함수 시퀀스로 가져 오는 함수를 줄이는 방법입니다.
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
카레 링은 사전 정의 된 값을 가진 다른 기능을 중심으로 한 기능을 정의한 다음 단순화 된 기능을 전달할 수 있기 때문에 좋습니다. C ++ STL 바인더는 C ++에서이를 구현합니다.
여기에 몇 가지 훌륭한 답변. 나는 개념을 가지고 놀는 것이 재미 있었기 때문에 내 자신을 추가 할 것이라고 생각했다.
부분 기능 응용 프로그램: 일부 매개 변수만으로 함수를 "바인딩"하는 프로세스는 나중에 채워질 나머지를 연기합니다. 결과는 매개 변수가 적은 또 다른 기능입니다.
카레: 한 번에 단일 인수 만 "바인딩"할 수있는 특수 형태의 부분 함수 응용 프로그램입니다. 결과는 정확히 1 파라미터가 정확히 1 인 다른 기능입니다.
제가 제시하려고하는 코드는입니다 부분 기능 응용 프로그램 카레가 가능하지만 유일한 가능성은 아닙니다. 위의 카레 구현에 비해 몇 가지 이점을 제공합니다 (주로 카레이 아닌 부분 기능 응용 프로그램이기 때문에 Currying, HEH).
빈 기능을 통해 적용 :
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가 "너무 많은 인수를 적용하려고 시도합니다!"
위의 다른 답변은 논쟁을 묶고 더 많은 람다를 반환하는 람다를 반환합니다. 이 접근법은 그 필수 기능을 호출 가능한 객체로 랩합니다. 정의에 대한 정의 operator()
내부 람다를 호출하도록 허용하십시오. Variadic 템플릿을 사용하면 누군가가 너무 멀리가는 것을 확인할 수 있으며, 결과 유형의 함수 호출 유형에 대한 암시적인 변환 기능을 통해 결과를 인쇄하거나 객체를 기본 요소와 비교할 수 있습니다.
암호:
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 주로 즐거움과 연습을 위해; 여기서는 일반적인 유형 특성과 동일하게 사용됩니다.
- 성능 이유에 대한 완벽한 전달을 지원하기 위해 더 많은 작업이있을 수 있습니다.
- 코드는 C ++ 17입니다.
constexpr
람다 지원 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;
}
이 링크는 관련이 있습니다.
Wikipedia의 Lambda 미적분학 페이지에는 카레이라는 명확한 예가 있습니다.
http://en.wikipedia.org/wiki/lambda_calculus#motivation
이 논문은 C/C ++로 카레를 취급합니다
http://asg.unige.ch/site/papers/dami91a.pdf