Daily C/C++ Y组合子

参考文章

这篇文章说实话我也是照葫芦画瓢，我还没有去看Y组合子的那篇官方的文章，这里只是给出一些用于实践上的理解

首先就是定义，Y组合子是一个特殊的高阶函数

$y(f) = f(y(f))$

看起来定义蛮奇怪的，f和y都是参数为函数，返回值为函数的一个函数

当我们尝试展开的时候会发现，这个函数是无限展开的，我们正是利用了这个特点，来帮助我们写出递归函数

更准确的说，是lambda中的递归

因为我们都知道，lambda表达式是没名字的，所以我们无法在lambda表达式内部去调用他自己，所以在这里我们需要Y组合子来帮我们实现递归

那么原理到底为什么Y组合子可以帮助我们省掉函数的名字从而实现递归，这个我目前也不是太清楚

下面是一个例子，我们尝试写出阶乘的版本

首先定义阶乘为 $fact(n) = zero(n)\ then\ 1\ else\ n \times fact(n - 1)$

然后我们观察，对于Y组合子来说，我们已经有了 $y$ 的定义，但是还不明确 $f$ ，所以这里我们就需要求出 $f$ 。求出 $f$ 后我们就可以使用 $y(f)$ 来得到结果

我们假设 $fact$ 可以表示成 $y(F)$

那么我们通过替换可以得到

$y(F)(n) = zero(n)\ then\ 1\ else\ n \times y(F)(n - 1)$

$F(y(F))(n) = zero(n)\ then\ 1\ else\ n \times y(F)(n - 1)$

然后把 $y(F)$ 替换成 $f$ ，我们就可以得到

$F(f)(n) = zero(n)\ then\ 1\ else\ n \times f(n - 1)$

在这里其实可以感觉到，我们的F就是f，一会儿我们也可以通过代码和另一种方法发现这一点。

但是注意，我们的lambda表达式是不能直接调用自己的，所以这里的方法更像是把自己作为参数传入的lambda表达式

比如这种写法

const auto& sum2 = [](const int& n) {
    const auto& s = [&](auto&& self, const int& x) -> int{
        return x == 1 ? 1 : x + self(self, x - 1);
    };
    return s(s,n);
};

这里感觉我们可以直接调用 $F(F, n)$ 来得到结果

不过接着上文，我们得到了F，就得到了fact，下面看代码

template <class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template <class T>
  explicit y_combinator_result(
    T&& fun)
    : fun_(std::forward<T>(fun))
  {
  }

  template <class... Args>
  decltype(auto)
  operator()(Args&&... args)
  {
    // y(f) = f(y(f))
    return fun_(
      std::ref(*this),
      std::forward<Args>(args)...);
  }
};

template <class Fun>
decltype(auto)
y_combinator(Fun&& fun)
{
  return y_combinator_result<
    std::decay_t<Fun>>(
    std::forward<Fun>(fun));
}

int main()
{
  // 上面的那个 F
  auto almost_fact =
    [](auto f, int n) -> int {
    if (n == 0)
      return 1;
    else
      return n * f(n - 1);
  };
  // fact = y(F)
  auto fact =
    y_combinator(almost_fact);
  cout << fact(10) << endl;
}

很棒的代码，我们来看一下

首先是一个类，用来实现我们的Y组合子

我们这里用完美转发来传入参数，也就是我们的f

然后重载了()运算符，就是我们具体使用的地方

fun接受至少一个参数，及我们的Y组合子，这里使用了引用传值传给f，然后把剩下的参数也传过去

下面的y_combinator就会调用这个函数对象，我们用decay得到原始的值类型来初始化函数对象，并把fun转发过去

这样就得到了y，此时再传入我们的f，即上面推导的那个式子

然后我们传入对应的参数，就可以得到结果。这时这里发生的是fact会调用我们Y组合子函数对象，即调用almost_fact(ref(*this), args...)

然后里面的f就又会调用这个函数对象，以达到递归的效果

说到这里其实Y组合子大家应该也理解的差不多了，下面是我在网上看到的另一种方法，也来分享一下

const auto& y = [](const auto& f) {
    return [&](const auto& x) {
        return x(x);
    }([&](const auto& x) -> std::function<int(int)> {
        return f([&](const int& n) {
            return x(x)(n);
        });
    });
};

const auto& sum3 = [](const auto& f) {
    return [=](const int& n) {
        return n == 1 ? 1 : n + f(n - 1);
    };
};

这里大家应该也可以看到，我们在sum3中传入了f，相比之后一定会重复的调用这个f，其实也就是sum3

我们看上面那一块，究竟是怎么推导出来的

这里我给出我个人的见解

$y(f) = f(y(f))$

我们令 $y(f) = F(F)$

则有 $y(f) = f(F(F))$

$F(F) = f(F(F))$

那么我们替换参数，就得到了 $F(x) = f(x(x))$

所以这里我们实现这个 $F$ ，即可以得到 $y(f)$

然后我们继续按照之前的思路，设递归函数为 $y(F)$ ，注意和上面的F不同

然后有 $sum3(n) = sum3(n - 1)$ （简写）

那么就有 $y(F)(n) = sum3(n - 1)$

$F(y(F))(n) = sum3(n - 1)$

再替换f，即 $F(f)(n) = f(n - 1)$

再根据结合性，以及上面Y组合子的写法，我们可以得到F接受一个函数作为参数，返回值是一个以n作为参数的函数。即上面的sum3。其实也就是f

那么上面之前的F，可以得到他的类型和f是相同的，即接受一个函数作为参数，返回值是一个n作为参数的函数，通过上面的第四行代码也可以看出来

我们在那里返回的是 $f(x(x))(n)$ ，即sum3中的那个返回值

到这里，大概的理解算是差不多了，不过我感觉这样来理解Y组合子是不对的，应该从其原理出发。我这样一步一步的跟着走就有种用过程式理解函数式的感觉。

还需深入学习

Daily C/C++ Y组合子

Daily C/C++ Y组合子

文章评论