学了那么久的函数式编程语言，一直想写一些相关的文章。经过一段时间的考虑，我决定开这个坑。

至于为什么选择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就是一个典型的把函数当第一公民的例子。在函数式编程中，我们将深挖函数作为第一公民的价值。