几何尺寸与公差论坛------致力于产品几何量公差标准GD&T (GDT:ASME)|New GPS(ISO)研究/CAD设计/CAM加工/CMM测量  


返回   几何尺寸与公差论坛------致力于产品几何量公差标准GD&T (GDT:ASME)|New GPS(ISO)研究/CAD设计/CAM加工/CMM测量 » 酉空间:CAX软件开发(一)基础理论 » 数学库 » 数学基础库
用户名
密码
注册 帮助 会员 日历 银行 搜索 今日新帖 标记论坛为已读


回复
 
主题工具 搜索本主题 显示模式
旧 2009-09-30, 04:16 PM   #1
huangyhg
超级版主
 
huangyhg的头像
 
注册日期: 04-03
帖子: 18592
精华: 36
现金: 249466 标准币
资产: 1080358888 标准币
huangyhg 向着好的方向发展
默认 【转帖】 Y组合子详解(再版) 第一章:高阶函数和lambda表达式

前言:

实际上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 ) )这两种形式之间自如的转换了。

2lambda表达式

会不会觉得这个小标题很奇怪,我们不是一直在使用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
__________________
借用达朗贝尔的名言:前进吧,你会得到信心!
[url="http://www.dimcax.com"]几何尺寸与公差标准[/url]
huangyhg离线中   回复时引用此帖
GDT自动化论坛(仅游客可见)
回复


主题工具 搜索本主题
搜索本主题:

高级搜索
显示模式

发帖规则
不可以发表新主题
不可以回复主题
不可以上传附件
不可以编辑您的帖子

vB 代码开启
[IMG]代码开启
HTML代码关闭



所有的时间均为北京时间。 现在的时间是 07:11 AM.


于2004年创办,几何尺寸与公差论坛"致力于产品几何量公差标准GD&T | GPS研究/CAD设计/CAM加工/CMM测量"。免责声明:论坛严禁发布色情反动言论及有关违反国家法律法规内容!情节严重者提供其IP,并配合相关部门进行严厉查处,若內容有涉及侵权,请立即联系我们QQ:44671734。注:此论坛须管理员验证方可发帖。
沪ICP备06057009号-2
更多