C#中的函數式編程：序言（一）

學了那麼久的函數式編程語言，一直想寫一些相關的文章。經過一段時間的考慮，我決定開這個坑。

至於為什麼選擇C#，在我看來，編程語言分三類：一類是難以進行函數式編程的語言，這類語言包括Java6、C語言等。這類語言由於不支持匿名函數等特性，進行函數式編程會比較困難；一類是自稱“函數式編程語言”的語言，包括Scala、Clojure、F#、Haskell等。這類語言比較重視函數式編程，它的教學資料通常會包含函數式編程知識，因此這些語言的使用者大多也都已經掌握了函數式編程技巧；還有一類編程語言，它們不被稱作函數式編程語言，卻可以進行函數式編程。這些語言的使用者中懂得函數式編程的人相對較少，學習資料也較少提及函數式編程。這些語言包括Java8、C++11、C#、Rust、Kotlin、TypeScript、Python、Ruby等。

既然我的文章是要介紹函數式編程，首先我肯定不能選第一類，它們無法使用；而第二類編程語言的使用者已經掌握了函數式編程的技能。考慮到受眾面，我的選擇範圍定在第三類語言內。最終我通過隨機數選中了C#，如果我有精力我也會嘗試一下其他語言。

說了這麼多，那究竟什麼是函數式編程呢？根據Scala之父Martin Odersky的說法，函數式編程有狹義和廣義之分：狹義的函數式編程指的是表達式沒有副作用的編程，滿足這一特性的編程語言有Pure Lisp和不包含IO Monad與Unsafe operations的Haskell子集；而廣義的函數式編程指的是函數是第一公民的語言，這個範圍就大了很多，前面提到的第二類與第三類語言都屬於廣義的函數式編程。

而函數式編程的核心，就和這兩個定義相關：沒有副作用、函數是第一公民。

我們先來看副作用。我記得以前學C語言時有人喜歡用x++ + ++x為例去黑某個人寫的臭名昭著的C語言的書。這個表達式實際上是一種未定義行為。但是，如果我們把它換成(x + 1) + (x + 2)，這個語句就毫無歧義。問題在於x++、++x是有副作用的。如果一個表達式是無副作用的，我們就可以用這個表達式的值替換成它，而程式的行為不會發生改變。我們稱這個性質為引用透明（Referential transparency）。就剛纔的例子，假設x的值是3，那麼對於(x + 1) + (x + 2)而言，我們可以把x + 1替換成它的值4，則表達式改寫成4 + (x + 2)，或者把x + 2替換成5而改寫成(x + 1) + 5，這樣的改寫不會改變表達式的值。但是x++ + ++x就不可以，如果我們把x++換成3，那麼表達式的值就會變。所以x++和++x不是引用透明的。

引用透明的一大特性是，我們可以改變引用透明的表達式的執行次序，而不用擔心程式行為的變化。之所以x++ + ++x是未定義行為，是因為x++和++x不是引用透明的，從而導致x++和++x執行的先後順序會影響整個表達式的值。而x + 1和x + 2的先後順序則對錶達式的值沒有影響。這個特性在後面我們會用到。

下麵再給一個例子，考慮這段C#代碼

 1 class Program
 2 {
 3     static void Main()
 4     {
 5         for (int i = 0; i < 10; ++i)
 6         {
 7             System.Threading.Tasks.Task.Factory.StartNew(() =>
 8             {
 9                 System.Threading.Thread.Sleep(100);
10                 System.Console.WriteLine(i);
11             });
12         }
13         System.Console.ReadLine();
14     }
15 }

這段代碼會輸出什麼？

你可能會以為它會以某種次序輸出數字0到9，但實際輸出是10個數字10.

為了能讓程式輸出數字0到9，我們需要這樣修改程式：

 1 class Program
 2 {
 3     static void Main()
 4     {
 5         for (int i = 0; i < 10; ++i)
 6         {
 7             int _i = i;
 8             System.Threading.Tasks.Task.Factory.StartNew(() =>
 9             {
10                 System.Threading.Thread.Sleep(100);
11                 System.Console.WriteLine(_i);
12             });
13         }
14         System.Console.ReadLine();
15     }
16 }

如果你是JavaScript程式員，你可能會對這個策略有所熟悉。這是在迴圈中創建閉包（即使用了外部變數的匿名函數）時常遇到的坑。對於前一個程式，由於迴圈變數的i是變化的，因此i不滿足引用透明，我們不能在創建閉包時就用i的值替換掉i，而由於Sleep語句存在，最終輸出的時候i的值是10。而第二個程式輸出的不是i，而是_i，_i滿足一經初始化後不再被重新賦值，這是一個變數滿足引用透明的重要特征。此時我們就可以用_i的值替換掉_i，從而程式能輸出數字0~9.

從上面的例子可以看出，使用副作用可能會產生不經意的bug。因此，在函數式編程中，我們會儘量的少產生副作用。比如上面這段代碼，最完美的方案是用我們後面會提到的尾遞歸。

函數式編程的另一個特點是函數是第一公民。在很多傳統的編程語言中，函數有很多限制，比如我們不能在函數內部定義函數，我們不能創建一個函數類型的變數（註意：C語言的函數指針嚴格來講不算。因為函數指針無法指向帶閉包的函數）、我們不能將函數當成參數傳給一個函數、不能創建一個沒有名字的函數字面量等等。“函數是第一公民”的意思是，函數不應該受這些“歧視”。函數應該和其他類型擁有同等地位。當然，嚴格的滿足函數是第一公民的語言也並不多。C#也是到了7才支持在函數內部創建函數。但對於函數式編程而言，函數至少要有的“權力”包括：創建沒有名字的函數字面量（即匿名函數或Lambda表達式）、將函數作為參數傳給其他參數。

我相信大家都用過Linq吧。Linq就是一個典型的把函數當第一公民的例子。在函數式編程中，我們將深挖函數作為第一公民的價值。