|
|
前言
著名的牛頓同學(xué)曾經(jīng)說過：如果說我比別人看得更遠(yuǎn)些,那是因?yàn)槲艺驹诹司奕说募缟?
原文：If I have been able to see further, it was only because I stood on the shoulders of giants.
What's Lambda表達(dá)式?
請參考msdn：Lambda 表達(dá)式（C# 編程指南）
Lambda表達(dá)式編寫遞歸函數(shù)? How?
建議沒有看過老趙的《使用Lambda表達(dá)式編寫遞歸函數(shù)》這篇文章的朋友，請先前往圍觀，你會受益匪淺。
原文實(shí)現(xiàn)如下的遞歸效果：
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));
頗有意思，能夠把遞歸發(fā)揮到這種極致。更有意思的是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! 這是人類寫的代碼嗎？
據(jù)原文介紹，此得意之作是裝配腦袋的腦袋想出來的。至于有興趣且希望前往一窺究竟的朋友，我先給大家打個預(yù)防針——首先選擇你一天中最清醒的時候，最好帶上氧氣瓶，以防由于其大師級的文章而可能造成短暫性的腦缺氧...
（裝配腦袋的兩篇大師級文章：1. VS2008亮點(diǎn)：用Lambda表達(dá)式進(jìn)行函數(shù)式編程 和 2. 用Lambda表達(dá)式進(jìn)行函數(shù)式編程（續(xù)）：用C#實(shí)現(xiàn)Y組合子）
人在江湖，高手如云。葵花寶典，如來神掌，此乃上乘武功，高手行走江湖的必殺技。我等后輩，深知神功非一日可練就，日夜苦練。幸好鄙人天資聰慧，一日秋高氣爽，幸見兩位大師切磋比試，深得大師真?zhèn)鳎毦?ldquo;拋磚引玉”神功，我拋，我拋！——大家請接好 -.-!
拋的是什么磚？
前面由Lambda表達(dá)式使出的一招函數(shù)式編程，經(jīng)潤色成遞歸函數(shù)，猶如手握屠龍刀一般登峰造極；今日我略懂竅門，奉上倚天劍，與屠龍刀集一身，可謂無懈可擊。
大家發(fā)現(xiàn)前面實(shí)現(xiàn)的3個遞歸函數(shù)有什么共同點(diǎn)嗎？沒錯，都是有返回值的。因?yàn)?Fix 返回的是 Func 或 Func 類型，換句話說 TResult 就是遞歸結(jié)束后期望返回的類型。如果是無返回值的遞歸呢？好的，聰明的你此刻應(yīng)該知道又是Action 出場了。
沒錯，我們要做的事情就是讓 Fix 返回 Action 。當(dāng)然，和前面的不一般的 Func 一樣， Action 也不是等閑之輩。
x => f(Fix(f))(x)
是的，我一不小心寫了一個(實(shí)際上是照葫蘆畫瓢)：
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);}
好的，在你還沒被以上代碼弄暈之前，我先舉一個大家都熟悉的例子——二叉樹遍歷 （二叉樹是我大學(xué)時學(xué)數(shù)據(jù)結(jié)構(gòu)最感興趣的一部分，另一個感興趣的是教我數(shù)據(jù)結(jié)構(gòu)的女老師）
先來回顧一下二叉樹的一般遞歸算法，如中序遍歷算法可用經(jīng)典的C語言描述為：
void InOrder(BinTree T){ if(T)// 如果二叉樹非空 { InOrder(T->lchild)； printf("％c"，T->data)； // 訪問結(jié)點(diǎn) InOrder(T->rchild); }} // InOrder
（題外話：想當(dāng)年我用C語言費(fèi)了多少時間不斷寫二叉樹的結(jié)構(gòu)和遍歷，請注意不是照搬書本的代碼。多少次內(nèi)存溢出，多少次與指針作斗爭，了解，忘記，再了解，又忘記，... 現(xiàn)在如果讓我來用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; }}
老實(shí)說，在實(shí)現(xiàn)手動構(gòu)造二叉樹時，我不知道如何寫盡量少的代碼并且這些代碼還要能夠清晰反映樹的結(jié)構(gòu)。為此我唯一想到的是類似XElement那樣，它寫出的代碼是樹形的，讓人從代碼可以聯(lián)想到對象的結(jié)構(gòu)。
現(xiàn)在，我們試著用 Node 來構(gòu)造以下的二叉樹：
/* 建立一棵簡單的二叉樹： 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，期待更好的構(gòu)造二叉樹寫法）
請?jiān)徫規(guī)Т蠹叶盗艘蝗▓@，現(xiàn)在回到剛才的非人類寫的代碼：
public static Action Fix(Func<Action, Action> f){ return x => f(Fix(f))(x);}
結(jié)合剛才的二叉樹，現(xiàn)在裝配以上代碼來實(shí)現(xiàn)對二叉樹的三種遍歷——中序，先序和后序
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();
運(yùn)行后的效果：
（大家可以在腦里對結(jié)果進(jìn)行驗(yàn)證一下，或點(diǎn)此查看）
其實(shí)以上代碼的關(guān)鍵部分f => n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } } 跟我們的思維還是類似的。如果你不習(xí)慣這種寫法，也可以寫成多行的形式：
f => n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });f 是 Action 類型，可以理解為將要實(shí)現(xiàn)遞歸的委托；
n 是 T類型，在本文它是 Node<char> 類型，是當(dāng)前遍歷的節(jié)點(diǎn)。
f(n.Left) 和 f(n.Right) 也就很好理解了，就是訪問左右節(jié)點(diǎn)。
多參數(shù)
對于多參數(shù)的情況，如 f => (arg1, arg2) =>{ ... } ，雖然上述方法也可以“湊合”著用，例如可以改成單參數(shù)的形式：
object arg2; f => arg1 =>{use arg2 to do sth... }
但是這樣一來，其中一個弊端就是f => arg1 =>{use arg2 to do sth... }不能單獨(dú)抽取出來進(jìn)行復(fù)用，意味著它的使用范圍變窄了。因?yàn)槿鐒偛诺闹行虮闅v，并不一定在方法里構(gòu)造相應(yīng)的委托，大可“搬”到方法外面去。
例如：
var inorder = Fix<Node<char>>(...);
“搬”出去以后：
public static Action<Node<char>> inorder = Fix<Node<char>>(...);
因此，完全有必要重載 Fix 方法提供多參數(shù)的形式。
文章開端已經(jīng)列出了2個參數(shù)的重載方法：
public static Action Fix(Func<Action, Action> f){ return (x, y) => f(Fix(f))(x, y);}
現(xiàn)在使用上述方法來寫一個遞歸遍歷指定目錄的所有子目錄，并記錄這些目錄到一個List 對象里：
var traversal_help = Fix<string, List<string>>(f => (current, pathList) =>{ //添加當(dāng)前目錄到pathList pathList.Add(current); //訪問當(dāng)前目錄的文件夾 foreach (string path in Directory.GetDirectories(current)) { //遞歸調(diào)用 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);}
以上兩個方法已經(jīng)徹底見不到 Func 的蹤影了，我謂之為“純Action”版，跟前一個版本同樣是實(shí)現(xiàn)無返回值的遞歸調(diào)用。
使用上也極其簡單，這里還是拿二叉樹遍歷來說明：
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); } });
這種寫法其實(shí)跟前一種寫法只有很小的差別：
f => n => ... 寫成：(f, n) => ...
同理，多參數(shù)的情況:
f => (n1, n2) => ... 寫成：(f, n1, n2) => ...
沒錯，如此而已。這里我想問問大家更樂于使用哪種寫法呢？
性能比較
兩個版本在性能上區(qū)別會不會有很大區(qū)別？
使用計(jì)時器 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));});
測試代碼其實(shí)就是二叉樹中序遍歷，只是打印節(jié)點(diǎn)的語句被去掉（即去掉 Console.Write(n.Value) ）。
兩個版本分別執(zhí)行一萬，十萬及一百萬次，得到的測試結(jié)果是：
Fix v1 * 10000
Time Elapsed: 413ms
CPU Cycles: 897,224,108
Gen 0: 10
Gen 1: 0
Gen 2: 0Fix 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: 0Fix 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: 0Fix v2 * 1000000
Time Elapsed: 31,576ms
CPU Cycles: 68,836,391,613
Gen 0: 545
Gen 1: 3
Gen 2: 0
結(jié)果顯示兩個版本在速度上旗鼓相當(dāng)，而“純Action”版在GC上優(yōu)于前者。
多參數(shù)的VS智能提示問題
上述代碼從理論上和實(shí)際上來說都是沒問題的。但是作為這篇文章的作者，我必須要很負(fù)責(zé)任的告訴大家，無論哪個Fix版本，對于多參數(shù)的情況，VS智能提示令我感到很意外，甚至無法理解。 而且更令我抓不著頭腦的是，這些VS智能提示并不是完全“癱瘓”，而是時而行，時而丟失，好像在跟你玩捉迷藏那樣。我所見到的有以下兩種情況：
1. 類型推斷正確，但智能提示丟失
雖然 VS 對類型的推斷是正確的：
（看后面 f 的類型夠嚇人的）
但當(dāng)你接著編寫 pathList 時，VS就判斷成未知類型：
然后當(dāng)寫完整個pathList后，點(diǎn)不到任何方法出來。此時對于VS來說，這個pathList相當(dāng)于是憑空捏造的那樣。
于是硬著頭皮寫完Add方法后，把鼠標(biāo)移上去，提示信息又能夠跑出來了。
這時候跑回pathList后點(diǎn)方法，智能提示才跑出來，但對于編程人員來說已經(jīng)沒有用了，因?yàn)檎麄€方法都已經(jīng)寫完了。
但當(dāng)你再次寫pathList還是判斷成未知類型，無語。
2. 類型推斷令人費(fèi)解
在foreach語句前寫 f ，VS的智能提示是正確的，即 Action>
到了foreach里面寫 f ，你猜猜變成了什么，竟然是 Func>
由于以上例子遞歸調(diào)用是放在foreach里面，所以必須在foreach里面寫f，于是再次硬著頭皮寫完整句代碼，提示信息再一次“回個神來”。
（注：我的編程環(huán)境是win7（中文）+VS2008（英文）+SP1）
這莫非是VS2008的一個bug？有意思吧，大家不妨把以上代碼放到自己的VS里試試，看看是否只有我的VS才這樣。
如果大家的VS對以上代碼的智能提示都是亂糟的，那么我建議認(rèn)識微軟的朋友高舉此文，游行到微軟的大門，嘿嘿。
末了說一句，以上代碼在VS2010中的智能提示是Perfect的。VS2010真是很好很強(qiáng)大，唯一不爽的就是逼得我要換機(jī)器，可憐我的NoteBook剛買不久 TT。
結(jié)語
其實(shí)我還想興致勃勃的看看 x => f(Fix(f), x) 在沒有 Lambda 表達(dá)式和匿名函數(shù)的支持會是什么模樣，以一窺其真諦幫助理解，但用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;}
請懂得以上代碼含義的朋友說說。
至于較早關(guān)于Lambda表達(dá)式和遞歸編程結(jié)合的博文可能要追溯到這位老外的文章了：
Recursive lambda expressions (從Post時間來看是2007年5月11日)
NET技術(shù)：使用Lambda表達(dá)式編寫遞歸函數(shù)，轉(zhuǎn)載需保留來源！
鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。
