艾伟_转载:使用Lambda表达式编写递归函数

前言

著名的牛顿同学曾经说过:如果说我比别人看得更远些,那是因为我站在了巨人的肩上.

原文:If I have been able to see further, it was only because I stood on the shoulders of giants.

What's Lambda表达式?

请参考msdn:Lambda 表达式(C# 编程指南)

Lambda表达式编写递归函数? How?

建议没有看过老赵的《使用Lambda表达式编写递归函数》这篇文章的朋友,请先前往围观,你会受益匪浅。

原文实现如下的递归效果:

var fac = Fix<int, int>(f => x => x <= 1 ? 1 : x * f(x - 1));
var fib = Fix<int, int>(f => x => x <= 1 ? 1 : f(x - 1) + f(x - 2));
var gcd = Fix<int, int, int>(f => (x, y) => y == 0 ? x : f(y, x % y));

颇有意思,能够把递归发挥到这种极致。更有意思的是Fix这个简短而又神秘莫测的方法:

static Func Fix(Func<Func, Func> f)
{
    return x => f(Fix(f))(x);
}
static Func Fix(Func<Func, Func> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

Oh my god! 这是人类写的代码吗?

据原文介绍,此得意之作是装配脑袋的脑袋想出来的。至于有兴趣且希望前往一窥究竟的朋友,我先给大家打个预防针——首先选择你一天中最清醒的时候,最好带上氧气瓶,以防由于其大师级的文章而可能造成短暂性的脑缺氧...

(装配脑袋的两篇大师级文章:1. VS2008亮点:用Lambda表达式进行函数式编程 和 2. 用Lambda表达式进行函数式编程(续):用C#实现Y组合子

人在江湖,高手如云。葵花宝典,如来神掌,此乃上乘武功,高手行走江湖的必杀技。我等后辈,深知神功非一日可练就,日夜苦练。幸好鄙人天资聪慧,一日秋高气爽,幸见两位大师切磋比试,深得大师真传,练就“抛砖引玉”神功,我抛,我抛!——大家请接好 -.-!

抛的是什么砖?

前面由Lambda表达式使出的一招函数式编程,经润色成递归函数,犹如手握屠龙刀一般登峰造极;今日我略懂窍门,奉上倚天剑,与屠龙刀集一身,可谓无懈可击。

大家发现前面实现的3个递归函数有什么共同点吗?没错,都是有返回值的。因为 Fix 返回的是 Func 或 Func 类型,换句话说 TResult 就是递归结束后期望返回的类型。如果是无返回值的递归呢?好的,聪明的你此刻应该知道又是Action 出场了。

没错,我们要做的事情就是让 Fix 返回 Action 。当然,和前面的不一般的 Func 一样, Action 也不是等闲之辈。

x => f(Fix(f))(x)

是的,我一不小心写了一个(实际上是照葫芦画瓢):

public static Action Fix(Func<Action, Action> f)
{
    return x => f(Fix(f))(x);
}
public static Action Fix(Func<Action, Action> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

 

好的,在你还没被以上代码弄晕之前,我先举一个大家都熟悉的例子——二叉树遍历 (二叉树是我大学时学数据结构最感兴趣的一部分,另一个感兴趣的是教我数据结构的女老师)

先来回顾一下二叉树的一般递归算法,如中序遍历算法可用经典的C语言描述为:

void InOrder(BinTree T)
{
    if(T)// 如果二叉树非空
   {
        InOrder(T->lchild);
        printf("%c",T->data); // 访问结点
        InOrder(T->rchild);
     }
} // InOrder

(题外话:想当年我用C语言费了多少时间不断写二叉树的结构和遍历,请注意不是照搬书本的代码。多少次内存溢出,多少次与指针作斗争,了解,忘记,再了解,又忘记,... 现在如果让我来用C语言写二叉树遍历,可能写出的代码会把编译器吓跑,嘿嘿。何况,此宝地乃.Net 牛人的汇集之地,更何况我想写的是泛型二叉树)

泛型二叉树

class Node
{
    public T Value { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
    public Node()
    { }
    public Node(T value)
        : this(value, null, null)
    { }
    public Node(T value, T left, T right)
        : this(value, new Node(left), new Node(right))
    { }
    public Node(T value, Node left, Node right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
}

 

老实说,在实现手动构造二叉树时,我不知道如何写尽量少的代码并且这些代码还要能够清晰反映树的结构。为此我唯一想到的是类似XElement那样,它写出的代码是树形的,让人从代码可以联想到对象的结构。

现在,我们试着用 Node 来构造以下的二叉树:

        /*
    建立一棵简单的二叉树:
     A
    / \
   B  C
  /   / \
 D  E   F
         */
static Node<char> BuildTree()
{
    return new Node<char>('A',
                new Node<char>('B',
                    new Node<char>('D'), null),
                new Node<char>('C',
                    'E', 'F'));
}

(以上代码始终不够理想,too many Node,期待更好的构造二叉树写法)

请原谅我带大家兜了一圈花园,现在回到刚才的非人类写的代码:

public static Action Fix(Func<Action, Action> f)
{
    return x => f(Fix(f))(x);
}

 

结合刚才的二叉树,现在装配以上代码来实现对二叉树的三种遍历——中序,先序和后序

var inorder = Fix<Node<char>>(f=> n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });
var preorder = Fix<Node<char>>(f=> n => { if (n != null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });
var postorder = Fix<Node<char>>(f=> n => { if (n != null) { f(n.Left); f(n.Right); Console.Write(n.Value); } });
Node<char> tree = BuildTree();
Console.WriteLine("(1) 中序序列(inorder traversal)");
inorder(tree);
Console.WriteLine();
Console.WriteLine("(2) 先序序列(preorder traversal)");
preorder(tree);
Console.WriteLine();
Console.WriteLine("(3) 后序序列(postorder traversal)");
postorder(tree);
Console.WriteLine();

 

运行后的效果:

(大家可以在脑里对结果进行验证一下,或点此查看

其实以上代码的关键部分f => n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } } 跟我们的思维还是类似的。如果你不习惯这种写法,也可以写成多行的形式:

f =>
    n =>
    {
        if (n != null)
        {
            f(n.Left);
            Console.Write(n.Value);
            f(n.Right);
        }
    });

 

f 是 Action 类型,可以理解为将要实现递归的委托;

n 是 T类型,在本文它是 Node<char> 类型,是当前遍历的节点。

f(n.Left) 和 f(n.Right) 也就很好理解了,就是访问左右节点。

多参数

对于多参数的情况,如 f => (arg1, arg2) =>{ ... } ,虽然上述方法也可以“凑合”着用,例如可以改成单参数的形式:

object arg2; f => arg1 =>{use arg2 to do sth... }

但是这样一来,其中一个弊端就是f => arg1 =>{use arg2 to do sth... }不能单独抽取出来进行复用,意味着它的使用范围变窄了。因为如刚才的中序遍历,并不一定在方法里构造相应的委托,大可“搬”到方法外面去。

例如:

var inorder = Fix<Node<char>>(...);

 

“搬”出去以后:

public  static Action<Node<char>> inorder = Fix<Node<char>>(...);

 

因此,完全有必要重载 Fix 方法提供多参数的形式。

文章开端已经列出了2个参数的重载方法:

public static Action Fix(Func<Action, Action> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

 

现在使用上述方法来写一个递归遍历指定目录的所有子目录,并记录这些目录到一个List 对象里:

var traversal_help = Fix<string, List<string>>(f => (current, pathList) =>
{
    //添加当前目录到pathList
    pathList.Add(current);
    //访问当前目录的文件夹
    foreach (string path in Directory.GetDirectories(current))
    {
        //递归调用
        f(path, pathList);
    }
});
List<string> result = new List<string>();
traversal_help("C:\\", result);

重载 (纯Action版)

x => f(Fix(f), x)

Oh my god! 又是非人类写的代码?

是的,我又一不小心写了另外一个版本:

public static Action Fix(Action<Action, T> f)
{
    return x => f(Fix(f), x);
}
static Action Fix(Action<Action, T1, T2> f)
{
    return (x, y) => f(Fix(f), x, y);
}

 

以上两个方法已经彻底见不到 Func 的踪影了,我谓之为“纯Action”版,跟前一个版本同样是实现无返回值的递归调用。

使用上也极其简单,这里还是拿二叉树遍历来说明:

var inorder = Fix<Node<char>>((f, n) => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });
var preorder = Fix<Node<char>>((f, n) => { if (n != null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });
var postorder = Fix<Node<char>>((f, n) => { if (n != null) { f(n.Left); f(n.Right); Console.Write(n.Value); } });

 

这种写法其实跟前一种写法只有很小的差别:

f => n => ... 写成:(f, n) => ...

同理,多参数的情况:

f => (n1, n2) => ... 写成:(f, n1, n2) => ...

没错,如此而已。这里我想问问大家更乐于使用哪种写法呢?

性能比较

两个版本在性能上区别会不会有很大区别?

使用计时器 CodeTimer ,测试代码:

var inorder1 = Fix<Node<char>>(f => n => { if (n != null) { f(n.Left); f(n.Right); } });
var inorder2 = Fix<Node<char>>((f, n) => { if (n != null) { f(n.Left); f(n.Right); } });
Node<char> tree = BuildTree();
CodeTimer.Initialize();
new List<int> { 10000, 100000, 1000000 }.ForEach(n =>
{
    CodeTimer.Time("Fix v1 * " + n, n, () => inorder1(tree));
    CodeTimer.Time("Fix v2 * " + n, n, () => inorder2(tree));
});

 

测试代码其实就是二叉树中序遍历,只是打印节点的语句被去掉(即去掉 Console.Write(n.Value) )。

两个版本分别执行一万,十万及一百万次,得到的测试结果是:


Fix v1 * 10000
        Time Elapsed:   413ms
        CPU Cycles:     897,224,108
        Gen 0:          10
        Gen 1:          0
        Gen 2:          0

Fix v2 * 10000
        Time Elapsed:   308ms
        CPU Cycles:     671,960,256
        Gen 0:          5
        Gen 1:          0
        Gen 2:          0

 

Fix v1 * 100000
        Time Elapsed:   3,118ms
        CPU Cycles:     6,796,717,873
        Gen 0:          109
        Gen 1:          0
        Gen 2:          0

Fix v2 * 100000
        Time Elapsed:   3,061ms
        CPU Cycles:     6,680,823,182
        Gen 0:          54
        Gen 1:          1
        Gen 2:          0

 

Fix v1 * 1000000
        Time Elapsed:   31,358ms
        CPU Cycles:     67,992,085,293
        Gen 0:          1090
        Gen 1:          3
        Gen 2:          0

Fix v2 * 1000000
        Time Elapsed:   31,576ms
        CPU Cycles:     68,836,391,613
        Gen 0:          545
        Gen 1:          3
        Gen 2:          0

 

结果显示两个版本在速度上旗鼓相当,而“纯Action”版在GC上优于前者。

多参数的VS智能提示问题

上述代码从理论上和实际上来说都是没问题的。但是作为这篇文章的作者,我必须要很负责任的告诉大家,无论哪个Fix版本,对于多参数的情况,VS智能提示令我感到很意外,甚至无法理解。 而且更令我抓不着头脑的是,这些VS智能提示并不是完全“瘫痪”,而是时而行,时而丢失,好像在跟你玩捉迷藏那样。我所见到的有以下两种情况:

1. 类型推断正确,但智能提示丢失

虽然 VS 对类型的推断是正确的:

(看后面 f 的类型够吓人的)

但当你接着编写 pathList 时,VS就判断成未知类型:

然后当写完整个pathList后,点不到任何方法出来。此时对于VS来说,这个pathList相当于是凭空捏造的那样。

于是硬着头皮写完Add方法后,把鼠标移上去,提示信息又能够跑出来了。

这时候跑回pathList后点方法,智能提示才跑出来,但对于编程人员来说已经没有用了,因为整个方法都已经写完了。

但当你再次写pathList还是判断成未知类型,无语。

2. 类型推断令人费解

在foreach语句前写 f ,VS的智能提示是正确的,即 Action>

到了foreach里面写 f ,你猜猜变成了什么,竟然是 Func>

由于以上例子递归调用是放在foreach里面,所以必须在foreach里面写f,于是再次硬着头皮写完整句代码,提示信息再一次“回个神来”。

(注:我的编程环境是win7(中文)+VS2008(英文)+SP1)

这莫非是VS2008的一个bug?有意思吧,大家不妨把以上代码放到自己的VS里试试,看看是否只有我的VS才这样。

如果大家的VS对以上代码的智能提示都是乱糟的,那么我建议认识微软的朋友高举此文,游行到微软的大门,嘿嘿。

末了说一句,以上代码在VS2010中的智能提示是Perfect的。VS2010真是很好很强大,唯一不爽的就是逼得我要换机器,可怜我的NoteBook刚买不久 TT。

 

结语

其实我还想兴致勃勃的看看 x => f(Fix(f), x) 在没有 Lambda 表达式和匿名函数的支持会是什么模样,以一窥其真谛帮助理解,但用Reflector 反编译以后得到的是以下代码,... 不是我能看懂的东西,作罢...

public static Action Fix(Action, T> f)
{
    <>c__DisplayClass7 CS$<>8__locals8;
    Action CS$1$0000;
    CS$<>8__locals8 = new <>c__DisplayClass7();
    CS$<>8__locals8.f = f;
    CS$1$0000 = new Action(CS$<>8__locals8.b__6);
Label_001D:
    return CS$1$0000;
}

请懂得以上代码含义的朋友说说。

至于较早关于Lambda表达式和递归编程结合的博文可能要追溯到这位老外的文章了:

Recursive lambda expressions (从Post时间来看是2007年5月11日)

				
时间: 2024-09-20 19:33:33

艾伟_转载:使用Lambda表达式编写递归函数的相关文章

使用Lambda表达式编写递归函数

前言 著名的牛顿同学曾经说过:如果说我比别人看得更远些,那是因为我站在了巨人的肩上. 原文:If I have been able to see further, it was only because I stood on the shoulders of giants. What's Lambda表达式? 请参考msdn:Lambda 表达式(C# 编程指南) Lambda表达式编写递归函数? How? 建议没有看过老赵的<使用Lambda表达式编写递归函数>这篇文章的朋友,请先前往围观,

艾伟_转载:老赵谈IL(3):IL可以看到的东西,其实大都也可以用C#来发现

在上一篇文章中,我们通过一些示例谈论了IL与CLR中的一些特性.IL与C#等高级语言的作用类似,主要用于表示程序的逻辑.由于它同样了解太多CLR中的高级特性,因此它在大部分情况下依旧无法展现出比那些高级语言更多的CLR细节.因此,如果您想要通过学习IL来了解CLR,那么这个过程很可能会"事倍功半".因此,从这个角度来说,老赵并不倾向于学习IL.不过严格说来,即使IL无法看出CLR的细节,也不足以说明"IL无用"--这里说"无用"自然有些夸张.但是

艾伟_转载:ASP.NET MVC 2博客系列之一:强类型HTML辅助方法

这是我针对即将发布的ASP.NET MVC 2所撰写的贴子系列的第一篇,这个博客贴子将讨论 ASP.NET MVC 2中新加的强类型HTML辅助方法. 现有的HTML辅助方法 ASP.NET MVC 1中发布了一套HTML辅助方法,可以用来在视图模板中帮助生成HTML界面.例如,要输出一个文本框,你可以在你的.aspx视图模板中使用Html.TextBox()辅助方法编写下列代码: 上面辅助方法的第一个参数提供了文本框的名称及id,第二个参数指定了它该有的值,然后上面的辅助方法会显示象下面这样的

艾伟_转载:把委托说透(4):委托与设计模式

委托与很多设计模式都有着千丝万缕的联系,在前面的随笔中已经介绍了委托与策略模式的联系,本节主要来讨论委托与其他两个模式:观察者模式和模板方法模式. 委托与观察者模式 在.NET中,很多设计模式得到了广泛应用,如foreach关键字实现了迭代器模式.同样的,.NET中也内置了观察者模式的实现方式,这种方式就是委托. 观察者模式的一般实现 网上可以找到很多资料介绍观察者模式的实现,我这里介绍一种简单的退化后的观察者模式,即Subject类为具体类,在其之上不再进行抽象. public class S

艾伟_转载:把委托说透(1):开始委托之旅 委托与接口

委托,本是一个非常基础的.NET概念,但前一阵子在园子里却引起轩然大波.先是Michael Tao的随笔让人们将委托的写法与茴香豆联系到了一起,接着老赵又用一系列文章分析委托写法的演变,并告诫"嘲笑孔乙己的朋友们,你们在一味鄙视"茴"的四种写法的同时,说不定也失去了一个了解中国传统文化的机会呢!". 在我个人看来,委托是.NET Framework中一个非常炫的特性,绝不会向有些评论里说的那样,根本没有机会接触.恰恰相反,我们几乎每天都会接触委托,使用委托. 其实园

艾伟_转载:使用LINQ to SQL更新数据库(中):几种解决方案

在前一篇文章中,我提出了在使用LINQ to SQL进行更新操作时可能会遇到的几种问题.其实这并不是我一个人遇到的问题,当我在互联网上寻找答案时,我发现很多人都对这个话题发表过类似文章.但另我无法满足的是,他们尽管提出了问题,却没有进行详细的剖析,只给出了解决方案(如添加RowVersion列.去除关联等),但却没有说明为什么必须这么做.这也是我写上篇的初衷,希望通过对LINQ to SQL源代码的分析,来一步一步找出解决问题的办法.本文将对这些方法一一进行讨论. 方案一:重新赋值 在Terry

艾伟_转载:WinForm二三事(二)

监视消息循环 在上一篇文章中,我们讨论了消息循环是响应用户输入的根本,还提到了在WinForm中执行耗时操作是因为这个耗时操作与消息循环在同一个UI Thread上,导致不能处理用户的后续响应,造成程序假死.除此之外,还说到了Form中的WndProc方法,说这个方法就是Win32时代那个处理消息的方法的.Net版. 那么今天这篇文章我们就来编个小程序来模拟一下这个耗时操作,看看是不是如上一篇所说:耗时操作造成消息循环的临时中断不能响应用户后续输入. 程序很简单,就是一个简单的窗体,上面放置一个

艾伟_转载:基于.NET平台的Windows编程实战(四)—— 数据库操作类的编写

本系列文章导航 基于.NET平台的Windows编程实战(一)--前言 基于.NET平台的Windows编程实战(二)-- 需求分析与数据库设计 基于.NET平台的Windows编程实战(四)-- 数据库操作类的编写 基于.NET平台的Windows编程实战(五)-- 问卷管理功能的实现 基于.NET平台的Windows编程实战(六)-- 题目管理功能的实现 大家都知道本系统的正常运行少不了数据库操作这一块,且其在本系统中具有决定性作用,可以说没有它的操作系统将无法运行,故在本节课程中,专门把针

艾伟_转载:编写自文档化的代码

文所以载道也.  -- 宋·周敦颐<通书·文辞> 对于我们程序员来说,我们的工作也是写作--几乎每天都要写代码:而且还要载"道",不仅仅要满足客户的需求,还要让代码具有高度的可读性,这样其他的程序员可以更容易地对代码进行修改和扩展. 按这样的要求,我们需要为代码编写足够的文档,也就是将代码"文档化".常见的做法有两种,外部文档和注释. 外部文档 外部文档指的是在代码文件之外编写的附加文档,比如在Word文档中采用大量的篇幅(如UML图.表格)来设计或记录