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组合子是不对的,应该从其原理出发。我这样一步一步的跟着走就有种用过程式理解函数式的感觉。
还需深入学习
文章评论