C++ 实现 Currying 和 Partial application

Curry 和 Partical application 是高阶函数的一个特点，在函数式编程中有着重要的应用。借助 C++11 的变长参数模板(Variadic template)，可以在 C++ 中实现 Currying 和 Partial application。

Currying and partial application

Currying 和 Partial application 都是高阶函数的体现，但这二者是不同的概念！ Currying 是将一个有 n 个参数的函数转换成 n 个只有 1 个参数的函数。 在 Lambda calculus 中，函数只能有一个参数。而 Parial application 则是接收函数的部分参数并返回一个新的函数。

Currying 和 Parial application 的区别就在于 Currying 每次只接受一个参数，而 Parial application 可以接受多个参数。

对于

f :: x -> y -> z -> res

f x y 值 Parial application 了一次，而从 Currying 的角度理解，则是 Curry 了两次。

根据Wikipedia的定义：

Currying

Currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument.

Parial application

Partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.

C++ 实现

Parial application 的实现

借助 C++ 的 Lambda expression, 非常容易实现 Partial application。

template<typename F, typename... Args>
auto partial(F f, Args... args) {
    return [=](auto... rest) -> auto {
        return f(args..., rest...);
    };
}

使用 partial 对函数做 Parial application:

void demo(int a, int & b, int c, int & d) {
    b = b + 1;
    d = d + 1;
}

int main() {
    int a = 11, b = 111, c = 1111, d = 11111;
    std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;

    partial(demo, a, std::ref(b))(c, std::ref(d));

    std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;

    return 0;
}

关于例子中的 std::ref 的使用，是因为引用传参的需要。注意到partial函数是一个模板函数，如果不用std::ref将参数转化为引用类型std::reference_wrapper，那么模板做类型推导时会认为参数是值类型，尽管demo函数的参数b的类型是int &，但是，这个引用是对参数拷贝之后的值(args中的值)的引用，而不是对main函数中的b的引用。这个地方，如果不使用std::ref，错误信息会很诡异：

error: binding value of type 'const int' to reference to type 'int' drops 'const' qualifier.

同理，我们也无法在partial返回的 Lambda expression 中将参数声明为引用类型，因此，参数d也会被认为是值类型，尽管demo函数的参数d的类型是int &，但是这个引用是对参数拷贝之后的值(rest中的值)的引用，而不是对main函数中的变量d的引用。

使用std::forward进一步优化partial函数，以减少运行过程中对参数的复制行为：

template<typename F, typename Arg>
auto partial(F && f, Arg && arg) {
    return [f=std::forward<F>(f), arg=std::forward<Arg>(arg)]
            (auto &&... rest) {
        return f(arg, decltype(rest)(rest)...);
    };
}

template<typename F, typename Arg, typename... Args>
auto partial(F && f, Arg && arg, Args &&... args) {
    return partial(partial(std::forward<F>(f),
            std::forward<Arg>(arg)), std::forward<Args>(args)...);
}

Currying 的实现

与 Parial application 相比，Currying 的实现要更加复杂一些。首先考虑简单的情形：将 std::function类型的函数科里化：

template<typename Return>
auto curry_impl(std::function<Return()> & f) {
    return std::forward<decltype(f)>(f);
}

template<typename Return, typename Arg>
auto curry_impl(std::function<Return(Arg)> & f) {
    return std::forward<decltype(f)>(f);
}

template<typename Return, typename Arg, typename... Args>
auto curry_impl(std::function<Return(Arg, Args...)> & f) {
    return [f=std::forward<decltype(f)>(f)](Arg arg) {
        std::function<Return(Args...)> rest = [&f, &arg](Args... args) -> Return {
            return f(arg, args...);
        };
        return curry_impl(rest);
    };
}

使用示例：

int main() {

    std::function<int(int &, int, int &, int)> demo = [](int & a, int b, int & c, int d) {
        a += 1;
        c += 1;
        return (a+b+c+d);
    };

    int a = 11, b = 111, c = 1111, d = 11111;

    std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;

    auto curried = curry(demo);
    auto partial_demo = curried(std::ref(a))(b);
    auto res = partial_demo(std::ref(c))(d);

    std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;

    return 0;
}

接下来，需要实现一个模板，将函数指针、成员函数、Lambda expression、仿函数(functor) 等都转换成一个std::function类型的函数，然后就可以方便地进行科里化了。

// for lambda expression, and functor object, after capturing,
// forward lambda expression to
//      `function_traits<Return (Class::*)(Args...) const>`,
// forward functor object to
//      `struct function_traits<Return (Class::*)(Args...)>`
template <typename Functor>
struct function_traits
        : public function_traits<decltype(&Functor::operator())> {};

// for std::function, ordinary functions and static member functions.
template <typename Return, typename... Args>
struct function_traits<Return(Args...)> {
    using func_type = std::function<Return(Args...)>;
};

// for function pointer. e.g, &f.
template <typename Return, typename... Args>
struct function_traits<Return (*)(Args...)> {
    using func_type = std::function<Return(Args...)>;
};

// for capturing functor object (callable struct, struct with overloaded `()`
// operator).
template <typename Class, typename Return, typename... Args>
struct function_traits<Return (Class::*)(Args...)> {
    using func_type = std::function<Return(Args...)>;
};

// for capturing lambda expression.
template <typename Class, typename Return, typename... Args>
struct function_traits<Return (Class::*)(Args...) const> {
    using func_type = std::function<Return(Args...)>;
};

有了function_traits，我们在进行科里化之前，只需要进行一次类型转换即可(转换成 function_traits<T>::func_type类型。使用示例：

template<typename F>
auto curry(F const & f) {
    typename function_traits<F>::func_type _f = f;
    return curry_impl(_f);
}

int f1(int a, int & b, int c, int & d) {
    b = b + 1;
    d = d + 1;
    return (a+b+c+d);
}

int main() {

    std::function<int(int &, int &)> f2 = [](int & m, int & k) {
        k = k + 1;
        m = m + 1;
        return k + 100;
    };
    auto f3 = [](int a, int & b, int c, int & d) -> auto {
        b = b + 1;
        d = d + 1;
    };

    int a = 11, b = 111, c = 1111, d = 11111;

    std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;

    curry(f1)(a)(std::ref(b))(c)(std::ref(d));
    curry(f2)(std::ref(a))(std::ref(c));
    curry(f3)(a)(std::ref(b))(c)(std::ref(d));

    std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;

    return 0;
}

Currying and partial application

C++ 实现

Comments: