在 C++ 中实现（类型化的）K 组合子

Question

我正在尝试从 SK combinator calculus in C++. The K combinator is a higher-order function 实现 K 组合器，它基本上采用一些值 x，而 returns 又又从中取值 y 和 returns x。也就是说，

K(x)(y) == x

或一步一步：

intermediate = K(x)
intermediate(y) == x

将 K(x) 视为独立于 y 的独立事物的能力至关重要。此外，如果只是创建 K(x) 而不是在 y 上调用它，则不必指定 y 的类型。 y 的类型可以在代码中某处计算 K(x)(y) 后指定。

我正在尝试修复我编写的试图实现 K 组合子的代码：

#include <iostream>

template<class A>
template<class B>
auto K = [](A x) {
    return [=](B y) {
        return x;
    };
};

int main()
{
    std::cout << "Hello world!\n";
    auto Kx = K<int>(3);
    auto Kxy = Kx<float>(4.5);
    std::cout << Kxy << std::endl;
}

输出error: extraneous template parameter list in template specialization or out-of-line template definition。我试过调整模板参数并移动它们无济于事。有谁知道我该如何解决这个错误？

Answer 1

您可以通过以下更改"solve"它：

template<class A, class B>
auto K = [](A x) {
    return [=](B y) {
        return x;
    };
};

但是，您还需要更改调用：

auto Kx = K<int, float>(3);
auto Kxy = Kx(4.5);

作为解释说明，虽然 lambda 本身不能模板化，但 C++14 变量可以，我正在做的是将 K 声明为模板化变量，它恰好发生了该变量被声明为 lambda 对象。

Answer 2

Lambda 不能是模板。你可以这样做：

#include <iostream>

auto K = [](auto x) {
    return [=](auto y) {
        return x;
    };
};

int main()
{
    std::cout << "Hello world!\n";
    auto Kx = K(3);
    auto Kxy = Kx(4.5);
    std::cout << Kxy << std::endl;
}

这些被称为通用 lambda（自 C++14 起就存在），基本上就是您想要的。他们的 operator() 是每个 auto 参数的模板。

Answer 3

即使您没有 C++14，这也是很有可能的——请记住，lambda 只是仿函数对象的快捷符号。因此，我们可以创建一个表示中间值的对象：

template<class A>
class Intermediate {
  A m_a;
public:
  explicit Intermediate(const A& a)
  : m_a(a)
  {}

  template<class B>
  A operator()(const B&) const
  { return m_a; }
};

template<class A>
Intermediate<A> K(const A& a)
{ return Intermediate<A>(a); }

单独的 K 函数对于模板参数推导是必要的，这样我们就可以写 K(x)(y).

在 C++ 中实现（类型化的）K 组合子

Implementing the (typed) K combinator in C++

c++

templates

metaprogramming

functor

higher-order-functions