【转帖】 Y组合子详解（再版） 第一章：高阶函数和lambda表达式

huangyhg

前言：

实际上Y组合子在C#而言是一个很没用的lambda表达式，因为在C#中，我们可以使用非常简单的语法来实现函数的递归调用，Y组合子的意义在于在只有匿名函数的lambda演算中实现函数的递归调用。但对Y组合子分析和理解的过程，能够使我们的大脑做个保健操。这，也许就是分析和理解Y组合子的意义。

其实，在很久很久以前，装配脑袋就已经用lambda表达式实现并分析过Y组合子了，但由于高阶函数的晦涩性，加之装配脑袋用的代码范例是VB的（尽管后来加上了C#的版本）使得很多C#程序员直到今天都没办法很好的理解Y运算子的实现。所以我尝试用了几篇文章从C#和科普的角度对Y组合子的由来、形式再做一次分析。但由于旅居他乡，在网吧行文多有不便，写的七零八落，并没有达到预想的质量。所以，在今天终于回到故乡和老家的时候，将这个系列的文章重写一次。

特 别提示：本系列文章的分析过程将是一个极费脑子的过程，所以每阅读完一个小节、一个章节，请闭目养神，务必将这个章节的内容充分理解且融会贯通，再尝试继 续阅读。在任何时候遇到读不下去的情况，请立即关闭浏览器，泡杯香茗，打打游戏看看新闻，松弛一下再继续。如若不遵此嘱，造成头晕目眩、眼冒金星等用脑过 度的症状，本人一概不负责任。

第一章：高阶函数和lambda表达式

1、高阶函数

在开始话题之前，我们先搞清楚什么叫做高阶函数（也叫做泛函，或者算子）。简单的说高阶函数就是接收或者返回函数的函数（或者说参数或返回值是函数的函数，或者说值域或定义域是函数的函数）。在这一次的话题中，我们主要接触到的都是接收一个函数并返回一个函数的高阶函数。

用C#程序来表达就是接收一个委托并返回一个委托的方法（委托）。简单的说：

DelegateY F( DelegateX d )

这样的方法，就是高阶函数。用Func泛型委托来表示：

Func<Func<double, double>, Func<double, double>>

接受一个Func<double, double>，返回一个Func<double, double>。

装配脑袋特别提示：一定要注意区分函数与委托的区别，lambda表达式或匿名方法所表示的都是函数，只不过他们在代码中调用的时候必须通过委托的来做媒介。同样的高阶函数接收或输出的是函数而不是委托，只不过是因为受到语法的制约，我们必须利用委托这个媒介才能来传递函数而已。而实际上无论是编译成匿名方法的lambda表达式还是匿名方法，在编译后的结果中都存在一个真实的方法，只是不能直接调用而已。

做一个最简单的高阶函数的例子，让我们来习惯这种语法：

public static Func<double, double> F( Func<double, double> f )
{
   return delegate( double n ) { return Math.Abs( f( n ) ); }
}

这个高阶函数把输入当作f的输入，而把f的结果取绝对值后输出。

即，F(f)是一个这样的函数h，使得h(n) = Math.Abs(f(n))。

或者说：F(f)(n) = Math.Abs(f(n))

比如说我们给这个函数输入一个正弦函数：

var g = F( Math.Sin );

他返回的函数g就是一个没有负值的正弦函数，函数轨迹类似于一大堆蒙古包。

简单的说：g(x) = |sin(x)|

或：F(sin)(x) = |sin(x)|

或：F(Math.Sin)(x) = Math.Abs(Math.Sin(x))



我们继续下面的话题。在这个版本中，我们使用的是匿名方法的语法，也许大家还好理解，所以我决定把语法变得更复杂些：



public static Func<double, double> F( Func<double, double> f )
{
   return n => Math.Abs( f( n ) );
}

嗯，现在把匿名方法变成了Lambda表达式，看起来有点晕了吧。好，我们现在不想要这个方法，直接把这个方法变成一个委托实例：

Func<Func<double, double>, Func<double, double>> F = f => n => Math.Abs( f( n ) );

很多人在这一步晕倒了，这是很正常的。



晕倒的同志爬起来，让我们来梳理一下：

首先我们把表达式分成两个部分：

Func<Func<double, double>, Func<double, double>> F

和

f => n => Math.Abs( f( n ) )



前面的部分很好理解，定义一个高阶函数委托F，后面的则是这个高阶函数委托的实现，我们干脆把这个表达式改一下：

f => { return n => Math.Abs( f( n ) ); }

这下看明白没？

f是参数，后面花括号里面的东西是实现。

等同于：

delegate( f )
{
   return n => Math.Abs( f ( n ) );
}



好吧，我再给你加上类型：
Func<double, double> delegate( Func<double, double> f )
{
   return n => Math.Abs( f ( n ) );
}

这下明白了吧。



提示：还没明白的同学，可以做做眼保健操、伸展运动，到窗台呼吸呼吸新鲜空气，然后继续回头看，看明白，再继续（不明白，继续看）。

在这一小节的最后，我希望大家已经能够在F(f)(n) = Math.Abs( f( n ) )和F = f => n => Math.Abs( f( n ) )这两种形式之间自如的转换了。

2、lambda表达式

会不会觉得这个小标题很奇怪，我们不是一直在使用lambda表达式的形式么？

答案是否定的，因为事实上lambda表达式正统的形式并不是像我们在C#里看到的那样，刚才的那个东西其实真正的在数学里的lambda表达式形式是：

λf.λn.Abs(f n)

小知识：符号λ发音为lambda（懒 的），这也是lambda表达式名称的由来。lambda表达式用于表达lambda演算逻辑，lambda演算分为有类型lambda演算和无类型 lambda演算。很不巧的是，Y组合子属于无类型lambda演算范畴，这使得我们在实现Y组合子的时候会遇到很大的阻碍。

天书！相信很多人的第一印象都是这样。还好我们不必在这种天书上面过多的纠缠，因为我们只需要搞清楚几件事情：

正统的lambda表达式表达的函数都是有且只有一个参数，那么多个参数的函数lambda表达式怎么表达呢？答案是返回另一个函数来接收第二个参数。这样说可能很难理解，我们抛开正统的lambda表达式形式，用我们喜闻乐见的C#语法来说明这件事情。比如说我要用lambda表达式定义一个函数，它接收两个参数，并返回这两个参数之和：

Func<int, Func<int, int>> f = x => y => x + y;

调用：

int i = f(1)(2);

其实C#的形式同样的令人难以理解，还是老办法，分解：

Func<int, Func<int, int>> f = x => { y => x + y }

f等于这样一个函数，接受一个int参数x，并返回另一个函数Func<int, int>，这个函数再接收一个int参数y，且对这个函数的调用结果是x + y。

小知识：接收一个参数，然后返回一个函数接收剩下的参数，且每个函数都只接受一个参数，这样形式的函数，叫做柯里化函数（Currying Function）。将一个多参数的函数转换成这样的形式，叫做将函数柯里化。

不难看出，在正统的lambda表达式中，连接收多个参数的函数都需要用高阶函数来表示。所以事实上整个lambda表达式的逻辑就是一个高阶函数逻辑，所以说如果不能正确理解高阶函数，就不能说是理解了lambda表达式！这也是本系列第一章如此着墨于高阶函数的原因。



我们需要搞清楚的第二件事情其实已经展现在我们眼前了，我们刚才在lambda随手创建了一个函数：y => x + y，如果说整个lambda表达式x => y => x + y还有个名字叫做f的话，那我们随手创建的这个函数，就是真正的无名氏了。这就是正统的lambda表达式的第二个特点。所有的函数都是匿名的。恰恰因为这一点，所以我们编程中很容易实现的函数递归调用在lambda表达式中看起来几乎是不可能的。而解决这个问题的东东，就是Y组合子。

如果有不相信的同学可以自己去尝试一下用一个lambda表达式来表示函数的递归，例如f(x) = x * f(x-1)（注意这个不是阶乘，因为没有<1的判断）。如果你写成这样：

f = x => x * f(x-1)

是无法通过编译的，因为在C#解析f的函数体x => x * f(x-1)的时候，是不知道f是什么东西的。

http://www.cnblogs.com/Ivony/archive/2009/08/16/1547771.html