Остановка универсальной рекурсии функции C ++ 14 `curry`
Я пытаюсь реализовать общий curry функция в C ++ 14, которая принимает вызываемый объект в качестве входного параметра и позволяет Выделка.
Желаемый синтаксис:
auto sum3 = [](int x, int y, int z){ return x + y + z; };
int main()
{
assert(curry(sum3)(1)(1)(1) == 3);
auto plus2 = curry(sum3)(1)(1);
assert(plus2(1) == 3);
assert(plus2(3) == 5);
}
Моя идея реализации заключается в следующем: curry Функция возвращает унарную функцию, которая связывает свой аргумент с будущим вызовом исходной функции, рекурсивно. Вызовите связанную исходную функцию на «последний рекурсивный шаг».
Обнаружение «последнего рекурсивного шага» является проблемной частью.
Моя идея заключалась в том, чтобы определить, является ли текущая связанная функция (во время рекурсии) был юридически вызван с нулевыми аргументами, используя is_zero_callable тип черты:
template <typename...>
using void_t = void;
template <typename, typename = void>
class is_zero_callable : public std::false_type
{
};
template <typename T>
class is_zero_callable<T, void_t<decltype(std::declval<T>()())>>
: public std::true_type
{
};
К сожалению, я не могу найти способ проверить правильную функцию на «вызываемость» с нулевым аргументом — мне нужно как-то проверить, если функция это будет возвращено из текущей связанной функции является ноль-вызываемой.
Вот что у меня так далеко (ссылка Godbolt):
template <typename TF, bool TLastStep>
struct curry_impl;
// Base case (last step).
// `f` is a function callable with no arguments.
// Call it and return.
template <typename TF>
struct curry_impl<TF, true>
{
static auto exec(TF f)
{
return f();
}
};
// Recursive case.
template <typename TF, bool TLastStep>
struct curry_impl
{
static auto exec(TF f)
{
// Bind `x` to subsequent calls.
return [=](auto x)
{
// This is `f`, with `x` bound as the first argument.
// (`f` is the original function only on the first recursive
// step.)
auto bound_f = [=](auto... xs)
{
return f(x, xs...);
};
// Problem: how to detect if we need to stop the recursion?
using last_step = std::integral_constant<bool, /* ??? */>;
// `is_zero_callable<decltype(bound_f)>{}` will not work,
// because `bound_f` is variadic and always zero-callable.// Curry recursively.
return curry_impl<decltype(bound_f),
last_step{}>::exec(bound_f);
};
}
};
// Interface function.
template <typename TF>
auto curry(TF f)
{
return curry_impl<TF, is_zero_callable<decltype(f)>{}>::exec(f);
}
Жизнеспособен ли мой подход / интуиция? (Действительно ли возможно остановить рекурсию, обнаружив, достигли ли мы исходной функции с нулевым аргументом?)
…или есть лучший способ решения этой проблемы?
(Пожалуйста, игнорируйте отсутствующую идеальную пересылку и отсутствие полировки в примере кода.)
(Обратите внимание, что я протестировал эту реализацию карри, используя указанный пользователем шаблон int TArity Параметр для остановки рекурсии, и он работал правильно. Пользователь вручную указывает арность оригинала f функция недопустима, однако.)
Решение
Минимальные изменения, необходимые для работы в Clang:
auto bound_f = [=](auto... xs) -> decltype(f(x, xs...))
// ^^^^^^^^^^^^^^^^^^^^^^^^^
{
return f(x, xs...);
};
using last_step = std::integral_constant<bool,
is_zero_callable<decltype(bound_f)>{}>;
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Явное указание типа возврата должно сделать его удобным для SFINAE и способным быть обнаруженным is_zero_callable, К сожалению, GCC недоволен этим, вероятно, из-за ошибки.
Обыкновенная лямбда — это в основном класс с шаблонным operator()так что мы можем просто написать это сами:
template<class F, class T>
struct bound_function {
F f;
T arg;
template<class... Args>
auto operator()(Args... args) const -> decltype(f(arg, args...)){
return f(arg, args...);
}
};
Обратите внимание, что я имитирую семантику общей лямбды здесь и делаю operator() const, Полнофункциональная реализация, вероятно, захочет перегружать категории константности и значений.
затем
auto bound_f = bound_function<TF, decltype(x)>{f, x};
работает как в GCC, так и в Clang, но имеет теоретическую проблему: когда только f(arg) допустимо (а не с дополнительными аргументами), а затем создает bound_function (который создает декларацию своего operator()) плохо сформирован NDR, потому что каждая действительная специализация operator()Для объявления требуется пустой пакет параметров.
Чтобы этого избежать, давайте специализируемся bound_function для случая «никаких дополнительных аргументов». И так как мы все равно вычисляем эту информацию, давайте просто выразим ее в элементе typedef.
template<class F, class T, class = void>
struct bound_function {
using zero_callable = std::false_type;
F f;
T arg;
template<class... Args>
auto operator()(Args... args) const -> decltype(f(arg, args...)){
return f(arg, args...);
}
};
template<class F, class T>
struct bound_function<F, T, void_t<decltype(std::declval<const F&>()(std::declval<const T&>()))>> {
using zero_callable = std::true_type;
F f;
T arg;
decltype(auto) operator()() const {
return f(arg);
}
};
затем
auto bound_f = bound_function<TF, decltype(x)>{f, x};
using last_step = typename decltype(bound_f)::zero_callable;
Другие решения
под проверкой файла. Пожалуйста.
https://github.com/sim9108/Study2/blob/master/SDKs/curryFunction.cpp
// ConsoleApplication4.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"#include <iostream>
#include <string>
#include <functional>
#include <type_traits>
// core function
template<typename FN, std::size_t N>
struct curry
{
FN fn_;
curry(FN fn) :fn_{ fn }
{
}
template<typename... TS, typename = std::enable_if_t< (N - sizeof...(TS)) != 0, int >>
auto operator()(TS... ts1) {
auto fn = [f = this->fn_, ts1...](auto... args) mutable {
return f(ts1..., args...);
};
return curry<decltype(fn), N - sizeof...(TS)>(fn);
}
template<typename... TS, typename Z = void, typename = std::enable_if_t< (N - sizeof...(TS)) == 0, int > >
auto operator()(TS... ts1) {
return fn_(ts1...);
}
};
//general make curry function
template<typename R, typename... Args>
auto make_curry(R(&f)(Args...)) {
auto fn = [&f](Args... args) {
return f(args...);
};
return curry<decltype(fn), sizeof...(Args)>(fn);
}
//general make curry member function
template<typename C, typename R, typename... Args>
auto make_curry(R(C::*f)(Args...), C c) {
auto fn = [f, c](Args... args) mutable {
return (c.*f)(args...);
};
return curry<decltype(fn), sizeof...(Args)>(fn);
}
template<typename C, typename R, typename... Args>
auto make_curry(R(C::*f)(Args...) const, C c) {
auto fn = [f, c](Args... args) mutable {
return (c.*f)(args...);
};
return curry<decltype(fn), sizeof...(Args)>(fn);
}
//general make curry lambda function
template<typename C>
auto make_curry(C&& c) {
using CR = std::remove_reference_t<C>;
return make_curry(&CR::operator(), c);
}
using std::string;
using std::function;
string func(string a, string b, string c) {
return "general function:" + a + b + c;
}
struct A {
string func(string a, string b, string c) {
return "member function:" + a + b + c;
};
};
int main(int argc, char* argv[])
{
{ //general function curry
auto c = make_curry(func);
auto m1 = c("t1")("t2")("t3");
auto m2 = c("test1")("test2")("test3");
auto m3 = c("m1");
auto m4 = m3("m2");
auto m5 = m4("m3");
std::cout << m5 << std::endl;
std::cout << m2 << std::endl;
std::cout << m5 << std::endl;
}
{ //member function curry
A a;
auto c = make_curry(&A::func, a);
auto m1 = c("t1")("t2")("t3");
auto m2 = c("test1")("test2")("test3");
auto m3 = c("m1");
auto m4 = m3("m2");
auto m5 = m4("m3");
std::cout << m1 << std::endl;
std::cout << m2 << std::endl;
std::cout << m5 << std::endl;
}
{ //lambda function curry
auto fn = [](string a, string b, string c) {
return "lambda function:" + a + b + c;
};
auto c = make_curry(fn);
auto m1 = c("t1")("t2")("t3");
auto m2 = c("test1")("test2")("test3");
auto m3 = c("m1");
auto m4 = m3("m2");
auto m5 = m4("m3");
std::cout << m1 << std::endl;
std::cout << m2 << std::endl;
std::cout << m5 << std::endl;
}
auto func3 = make_curry(func);
std::cout << func3("Hello, ")( "World!", " !hi") << std::endl;
std::cout << func3("Hello, ","World!")(" !hi") << std::endl;
std::cout << func3("Hello, ","World!", " !hi") << std::endl;
std::cout << func3()("Hello, ", "World!", " !hi") << std::endl;
return 0;
}