停止通用 C++14 `curry` 函数递归

Question

我正在尝试在 C++14 中实现通用 curry 函数，该函数将可调用对象作为输入参数并允许 currying.

所需语法：

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 函数 return 是一个一元函数，它以递归方式将其参数绑定到将来对原始函数的调用。在"last recursive step".

上调用绑定的原始函数

检测"last recursive step"是有问题的部分。

我的想法是检测当前绑定函数 （在递归期间） 是否可以合法地使用零参数调用，使用 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
{
};

不幸的是，我似乎无法找到一种方法来检查零参数的正确函数 "callability" - 我需要以某种方式检查函数 是否会 return来自当前绑定函数的 ed 是可零调用的。

这是我目前得到的 (godbolt link):

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

我的 approach/intuition 可行吗？ （是否真的有可能通过检测我们是否已经达到原始函数的零参数可调用版本来停止递归？）

...或者有更好的方法来解决这个问题吗？

（请忽略示例代码中缺少的完美转发和润色不足。）

（请注意，我已经使用用户指定的模板 int TArity 参数测试了此柯里化实现以停止递归，并且它正常工作。让用户手动指定的数量但是，原始的 f 功能是不可接受的。）

Answer 1

在 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)>{}>;
//                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

明确指定 return 类型应该使其对 SFINAE 友好并且能够被 is_zero_callable 检测到。不幸的是，GCC 对此不满意，可能是由于错误。

一个通用的 lambda 基本上是一个 class 和一个模板化的 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...);
    }
};

请注意，我在这里模仿通用 lambda 的语义并制作 operator() const。一个全功能的实现可能希望在 constness 和值类别上超载。

然后

auto bound_f = bound_function<TF, decltype(x)>{f, x};

在 GCC 和 Clang 中都有效，但有一个理论上的问题：当只有 f(arg) 有效（并且没有额外的参数），然后实例化 bound_function（实例化其 operator() 的声明）是格式错误的 NDR，因为 operator() 声明的每个有效特化都需要一个空参数包。

为了避免这种情况，让我们将 bound_function 专门化为 "no further arguments needed" 的情况。由于我们无论如何都要计算这些信息，所以我们只用成员 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;

Answer 2

正在检查文件。请

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

停止通用 C++14 `curry` 函数递归

Stopping generic C++14 `curry` function recursion

c++

recursion

functional-programming

currying

c++14