Y不动点组合子

最近想学习函数式编程语言，突然想起来之前 C++ lambda 中递归的一些问题，就放到这里来讲一讲了。就以 C++ 为例，先讲解两种比较简单的写法。

直接传参

auto f = [](auto&& self, int n) -> int {
    return n ? n * self(self, n - 1) : 1;
};
f(f, 3); //The answer is 6.
//or you can:
auto fact = [&](int n) {return f(f, n);};

这种方法的问题在于需要指定放回值，否则无法推导类型。lambda 的类可以近似成下面这种：

template<typename... Args>
class lam {
 private:
  //args...
 public:
  lam(Args... args) {//do something}
  //if you designate the return type, auto -> type.
  template<typename... Args2>
  auto operator() (Args...&& args) {
    //...
  }
};

初始化参数

auto fact = [f = [](auto&& self, int n) -> int {
    return n ? n * self(self, n - 1) : 1;
}](int n) {return f(f, n);};
fact(3); //The answer is 6.

还有其他方法，比如在 c++23 中还有更高级的用法，这里不一一叙述。

Y不动点组合子

接下来进入正题，非常有实力。将匿名函数进行递归。那么结果是怎么样的呢？

$$ \lambda f.\;(\lambda x.\;f(x\;x))(\lambda x.\;f(x\;x)) $$

这里来简单推导一下。就以阶乘为例。

定义为 $fact=\lambda f.\ \lambda n.\ \text{if}\ (\text{isZero}\ n)\ 1\ ((f\ f)(n-1))$。

定义 $w=\lambda f.f\ f.$。

那么答案就是

$$ \begin{aligned} fact&=\lambda f.\ \lambda n.\ \text{if}\ (\text{isZero}\ n)\ 1\ ((f\ f)(n-1))\\ &=\lambda f.\ (\lambda g.\ \lambda n.\ \text{if}\ (\text{isZero}\ n)\ 1\ g(n-1))(f\ f)\\ &=\lambda h.\ (\lambda f.\ h\ (f\ f)) \ (\lambda g.\ \lambda n.\ \text{if}\ (\text{isZero}\ n)\ 1\ g(n-1))\\ w\ fact&= fact\ fact\\ &=\lambda h.\ (\lambda f.\ h(f\ f))(\lambda f.\ h(f\ f))\ (\lambda g.\ \lambda n.\ \text{if}\ (\text{isZero}\ n)\ 1\ g(n-1)) \end{aligned} $$

可以看到，令

$$ S=\lambda f.\;(\lambda x.\;f(x\;x))(\lambda x.\;f(x\;x)) $$

那么我们所需要的就是 $S\ f$。

但是这样在 C++ 中难以方便实现，因为 C++ 中这样涉及到自己调用自己，返回值不能确定。观察了一下发现并没有很好的实现方法，就尽量别在 C++ 中用这玩意了，而且实现了效率低下。