一直以来，我以为 LINQ 是专门用来对不同数据源进行查询的工具，直到我看了这篇十多年前的文章，才发现 LINQ 的功能远不止 Query。这篇文章的内容比较高级，主要写了用 C# 3.0 推出的 LINQ 语法实现了一套“解析器组合子（Parser Combinator）”的过程。那么这个组合子是用来干什么的呢？简单来说，就是把一个个小型的语法解析器组装成一个大的语法解析器。当然了，我本身水平有限，暂时还写不出来这么高级的代码，不过这篇文章中的一段话引起了我的注意：

Any type which implements Select, SelectMany and Where methods supports (part of) the “query pattern” which means we can write C#3.0 queries including multiple froms, an optional where clause and a select clause to process objects of this type.

大意就是，任何实现了 Select，SelectMany 等方法的类型，都是支持类似于 from x in y select x.z 这样的 LINQ 语法的。比如说，如果我们为 Task 类型实现了上面提到的两个方法，那么我们就可以不借助 async/await 来对 Task 进行操作：

  1. // 请在 Xamarin WorkBook 中执行
  2. var taskA = Task.FromResult(12);
  3. var taskB = Task.FromResult(12);
  5. // 使用 async/await 计算 taskA 跟 taskB 的和
  6. var a = await taskA;
  7. var b = await taskB;
  8. var r = a + b;
  10. // 如果为 Task 实现了 LINQ 拓展方法，就可以这么写：
  11. var r = from a in taskA
  12.         from b in taskB
  13.         select a + b;

那么我们就来看看如何实现一个非常简单的 LINQ to Task 吧。

首先我们要定义一个 Select 拓展方法，用来实现通过一个 Func<TValue, TResult> 将 Task<TValue> 转换成 Task<TResult> 的功能。

  1. static async Task<TR> Select<TV,TR>(this Task<TV> task, Func<TV, TR> selector) {
  2.     var value = await task;    // 取出 task 中的值
  3.     return selector(value);    // 使用 selector 对取出的值进行变换
  4. }

这个函数非常简单，甚至可以简化为一行代码，不过仅仅这是这样就可以让我们写出一个非常简单的 LINQ 语句了：

  1. var taskA = Task.FromResult(12);
  2. var r = from a in taskA select a * a;

那么实际上 C# 编译器是如何工作的呢？我们可以借助下面这个有趣的函数来一探究竟：

  1. void PrintExpr<T1,T2>(Expression<Func<T1, T2>> expr) {
  2.     Console.WriteLine(expr.ToString());
  3. }

熟悉 LINQ 的人肯定对 Expression 不陌生，Expressing 给了我们在运行时解析代码结构的能力。在 C# 里面，我们可以非常轻松地把一个 Lambda 转换成一个 Expression，然后调用转换后的 Expression 对象的 ToString() 方法，我们就可以在运行时以字符串的形式获取到 Lambda 的源码。例如：

  1. var taskA = Task.FromResult(12);
  2. PrintExpr((int _) => from a in taskA select a * a);
  3. // 输出： _ => taskA.Select(a => (a * a))

可以看到，Expression 把这段 LINQ 的真面目给我们揭示出来了。那么，更加复杂一点的 LINQ 呢？

  1. var taskA = Task.FromResult(12);
  2. var taskB = Task.FromResult(12);
  3. PrintExpr((int _) =>
  4.     from a in taskA
  5.     from b in taskB
  6.     select a * b
  7.     );

如果你尝试运行这段代码，你应该会遇到一个错误——缺少对应的 SelectMany 方法，下面给出的就是这个 SelectMany 方法的实现：

  1. static async Task<TR> SelectMany<TV, TS, TR>(this Task<TV> task, Func<TV, Task<TS>> selector, Func<TV,TS, TR> projector){
  2.     var value = await task;
  3.     var selected = await selector(value);
  4.     return projector(value, selected);
  5. }

这个 SelectMany 实现的功能就是，通过一个 Func<TValue, Task<TResult>> 将 Task<TValue> 转换成 Task<TResult>。有了这个之后，你就可以看到上面的那个较为复杂的 LINQ to Task 语句编译后的结果：

  1. _ => taskA.SelectMany(a => taskB, (a, b) => (a * b))

可以看到，当出现了两个 Task 之后，LINQ 就会使用 SelectMany 来代替 Select。可是我想为什么 LINQ 不像之前那样，用两个 Select 分别处理两个 Task 呢？为了弄清楚这个问题，我试着推导了一番：

  1. // 首先简单粗暴的用两个 Select 来实现这个功能
  2. Task<Task<int>> r = taskA.Select(a => b.Select(b => a + b));
  4. // r 被包裹了两层 Task，我们可以用 SelectMany 来去掉一层 Task 包装
  5. // 这时 TValue 是 Task<int>, TResult 是 int
  6. //
  7. // 那么 Task<Task<int>>
  8. // 将通过 Func<Task<int>, Task<int>>
  9. // 转换成 Task<int>
  11. Task<int> result = r.SelectMany(x => x, (_, x) => x);

结果比 LINQ 还多调用了两次 Select。仔细看的话，就会发现，我们所写的第二个 Select 其实就是 SelectMany，的第二个参数，而对于第一个 Select 来说，因为 b 是一个 Task，所以 b.Select(xxx) 的返回值肯定是一个 Task，而这又恰好符合 SelectMany 函数的第一个参数的特征。

有了上面的经验，我们不难推断出，当 from x in y 语句的个数超过 2 个的时候，LINQ 仍然会只使用 SelectMany 来进行翻译。因为 SelectMany 可以被看作为把两层 Task 转换成单层 Task，例如：

  1. var taskA = Task.FromResult(12);
  2. var taskB = Task.FromResult(12);
  3. var taskC = Task.FromResult(12);
  4. PrintExpr((int _) =>
  5.     from a in taskA
  6.     from b in taskB
  7.     from c in taskC
  8.     select a * b + c
  9.     );
  11. // 我的推断：
  12. var r = taskA.SelectMany(a => taskB, (a, b) => new {a, b}).SelectMany(temp => taskC, (temp, c) => temp.a * temp.b + c);
  14. // 实际的输出：
  15. // _ => taskA.SelectMany(a => taskB, (a, b) => new <>f__AnonymousType0#1`2(a = a, b = b)).SelectMany(<>h__TransparentIdentifier0 => taskC, (<>h__TransparentIdentifier0, c) => ((<>h__TransparentIdentifier0.a * <>h__TransparentIdentifier0.b) + c))

这里 LINQ 为第一个 SelectMany 的结果生成了一个匿名的中间类型，将 taskA 跟 taskB 的结果组合成了 Task<{a, b}>，方便在第二个 SelectMany 中使用。

至此，一个非常简单的 LINQ to Task 就完成了，通过这个小工具，我们可以实现不使用 async/await 就对类型进行操作。然而这并没有什么卵用，因为 async/await 确实要比 from x in y 这种语法要来的更加简单。不过举一反三，我们可以根据上面的经验来实现一个更加使用的小功能。

在一些比较函数式的语言（如 F#，Rust）中，会使用一种叫做 Result<TValue, TError> 的类型来进行异常处理。这个类型通常用来描述一个操作结果以及错误信息，帮助我们远离 Exception 的同时，还能保证我们全面的处理可能出现的错误。如果使用 C# 实现的话，一个 Result 类型可以被这么来定义：

  1. class Result<TValue, TError>
  2. {
  3.     public TValue Value {get; private set;}
  4.     public TError ErrorMsg {get; private set;}
  5.     public bool IsSuccess {get; private set;}
  6.     public override string ToString()
  7.     {
  8.         if(this.IsSuccess)
  9.             return "Success: " + Value.ToString();
  10.         return "Error: " + ErrorMsg.ToString();
  11.     }
  13.     public static Result<TValue, TError> OK(TValue value)
  14.     {
  15.         return new Result<TValue, TError> {Value = value, ErrorMsg = default(TError), IsSuccess = true};
  16.     }
  18.     public static Result<TValue, TError> Error(TError error)
  19.     {
  20.         return new Result<TValue, TError> {Value = default(TValue), ErrorMsg = error, IsSuccess = false};
  21.     }
  22. }

接着仿照上面为 Task 定义 LINQ 拓展方法，为了 Result 设计 Select 跟 SelectMany：

  1. static Result<TR, TE> Select<TV,TR, TE>(this Result<TV, TE> result, Func<TV, TR> selector) =>
  2.     result.IsSuccess
  3.     ? Result<TR, TE>.OK(selector(result.Value))
  4.     : Result<TR, TE>.Error(result.ErrorMsg);
  6. static Result<TR, TE> SelectMany<TV, TS, TR, TE>(this Result<TV, TE> result, Func<TV, Result<TS, TE>> selector, Func<TV, TS, TR> projector){
  7.     if (result.IsSuccess)
  8.     {
  9.         var tempResult = selector(result.Value);
  10.         if (tempResult.IsSuccess)
  11.         {
  12.             return Result<TR, TE>.OK(projector(tempResult.Value, tempResult.Value));
  13.         }
  14.         return Result<TR, TE>.Error(tempResult.ErrorMsg);
  15.     }
  16.     return Result<TR, TE>.Error(result.ErrorMsg);
  17. }

那么 LINQ to Result 在实际中的应用是什么样子的呢，接下来我用一个小例子来说明：
某公司为感谢广大新老用户对 “5 元 30 M”流量包的支持，准备给余额在 350 元用户的以上的用户送 10% 话费。但是呢，如果用户在收到赠送的话费后余额会超出 600 元，就不送话费了。

  1. using Money = Result<double, string>;
  3. // 查找指定 Id 的用户是否存在
  4. Result<int, string> GetUserById(int id)
  5. {
  6.     if(id % 7 == 0)
  7.     {
  8.         // 正常的用户
  9.         return Result<int,string>.OK(id);
  10.     }
  11.     if(id % 2 == 0)
  12.     {
  13.         return Result<int, string>.Error("用户已被冻结");
  14.     }
  15.     return Result<int, string>.Error("用户不存在");
  16. }
  18. // 查找指定用户的余额
  19. Money GetMoneyFromUser(int id)
  20. {
  21.     if (id >= 35)
  22.     {
  23.         return Money.OK(id * 10);
  24.     }
  25.     return Money.Error("穷逼用户不参与这次活动");
  26. }
  28. // 给用户转账
  29. Money Transfer(double money, double amount)
  30. {
  31.     return  from canTransfer in CheckForTransfer(money, amount)
  32.             select canTransfer ? money + amount : money;
  33. }
  35. // 检查用户是否满足转账条件，如果转账后的余额超过了 600 元，则终止转账
  36. Result<bool, string> CheckForTransfer(double a, double b)
  37. {
  38.     if (a + b >= 600) {
  39.         return Result<bool,string>.Error("超出余额限制");
  40.     }
  41.     return Result<bool,string>.OK(true);
  42. }
  44. Money SendGift(int userId)
  45. {
  46.     return  // 查询用户信息
  47.             from user in GetUserById(userId)
  48.             // 获取该用户的余额
  49.             from money in GetMoneyFromUser(user)
  50.             // 给这个用户转账
  51.             from transfer in Transfer(money, money * 0.1)
  52.             // 获取结果
  53.             select transfer;
  54. }
  56. SendGift(42)
  57. // Success: 462
  59. SendGift(56)
  60. // Error: 超出余额限制
  62. SendGift(1)
  63. // Error: 用户不存在
  65. SendGift(14)
  66. // Error: 穷逼用户不参与这次活动
  68. SendGift(16)
  69. // Error: 用户已被冻结

可以看到，使用 Result 能够让我们更加清晰地用代码描述业务逻辑，而且如果我们需要向现有流程中添加新的验证逻辑，只需要在合适地地方插入 from result in validate(xxx) 就可以了，换句话说，我们的代码变得更加“声明式”了。

细心的你可能已经发现了，不管是 LINQ to Task 还是 LINQ to Result，我们都使用了某种特殊的类型（如：Task，Result）对值进行了包装，然后编写了特定的拓展方法 —— SelectMany，为这种类型定义了一个重要的基本操作。在函数式编程的里面，我们把这种特殊的类型统称为“Monad”，所谓“Monad”，不过是自函子范畴上的半幺群而已。

在高中数学，我们学习了一个概念——集合，这是范畴的一种。

对于我们程序员来说，int 类型的全部实例构成了一个集合（范畴），如果我们为其定义了一些函数，而且它们之间的复合运算满足结合律的话，我们就可以把这种函数叫做 int 类型范畴上的“态射”，态射讲的是范畴内部元素间的映射关系，例如：

  1. // f(x) = x * 2
  2. Func<int, int> f = (int x) => x * 2;
  3. // g(x) = x + 1
  4. Func<int, int> g = (int x) => x + 1;
  5. // h(x) = x + 10
  6. Func<int, int> h = (int x) => x + 10;
  8. // 将函数 g 与 f 复合，(g ∘ f)(x) = g(f(x))
  9. Func<X, Z> Compose<X, Y, Z>(Func<Y, Z> g, Func<X, Y> f) => (X x) => g(f(x));
  11. Compose(h, Compose(g, f))(42) == Compose(Compose(h, g), f)(42)
  12. // true

f，g，h 都是 int 类型范畴上的态射，因为函数的复合运算是满足结合律的。

我们还可以定义一种范畴间进行元素映射的函数，例如：

  1. Func<int, double> ToDouble = x => Convert.ToDouble(x);

这里的函数 Select 实现了 int 范畴到 double 范畴的一个映射，不过光映射元素是不够的，要是有一种方法能够帮我们把 int 中的态射（f，g，h），映射到 double 范畴中，那该多好。那么下面的函数 F 就帮助我们实现了这了功能。

  1. // 为了方便使用 Compose 进行演示，故定义了一个比较函数式的 ToInt 函数
  2. Func<double, int> ToInt = x => Convert.ToInt32(x);
  3. // 一个将 int -> int 转换为 double -> double 的函数
  4. Func<double, double> F(Func<int, int> selector) => x => Compose(Compose(ToDouble, selector), ToInt)(x);
  6. // 在范畴间映射 f
  7. var Ff = F(f);
  8. Ff(42.0);
  9. // 84.00
  11. // 在范畴间映射 g
  12. var Fg = F(g);
  13. Fg(42.0);
  14. // 43.00
  16. // 在范畴间映射 h
  17. var Fh = F(h);
  18. Fh(42.0);
  19. // 52.00
  21. // Ff, Fg, Fh 之间仍然保持结合律，因为他们是 `double` 范畴上的态射
  22. Compose(Fh, Compose(Fg, Ff))(42) == Compose(Compose(Fh, Fg), Ff)(42)

因为 F 能够将一个范畴内的态射映射为另一个范畴内的态射，ToDouble 可以将一个范畴内的元素映射为另一个范畴内的元素，所以，我们可以把 F 与 ToDouble 的组合称作“函子”。函子体现了两个范畴间元素的抽象结构上的相似性。

相信看到这里你应该对范畴跟函子这两个概念有了一定的了解，现在让我们更进一步，看看 C# 中泛型与范畴之间的关系。

在之前，我们是以数值为基础来理解范畴这个概念的，那么现在我们从类型的层面来理解范畴。

泛型是我们非常熟悉的 C# 语言特性了，泛型类型与普通类型不一样，泛型类型可以接受一个类型参数，看起来就像是类型的函数。我们把接受函数作为参数的函数称为高阶函数，依此类推，我们就把接受类型作为参数的类型叫做高阶类型吧。这样，我们就可以从这个层面把 C# 的类型分为两类：普通类型（非泛型）和高阶类型（泛型）。

前面的例子中，我列出的 f，g，h 能够完成 int -> int 的转换，因为它们是 int 范畴内的态射。而 ToDouble 能够完成 int -> double 的转换，那我们就可以将他看作是普通类型范畴的态射，类似的，我们还可以定义出 ToInt32，ToString 这样的函数，它们都能完成两个普通类型之间的转换，所以也都可以看作是普通类型范畴的态射。

那么对于高阶类型（也就是泛型）范畴来说，是不是也存在态射这样的东西呢？答案是肯定的，举个例子，用 LINQ 把 List<int> 转换成 List<double> ：

  1. Func<List<int>, List<double>> ToDoubleList = x => x.Select(ToDouble).ToList();

不难发现，这里的 ToDoubleList 是 List<T> 类型范畴内的一个态射。不过你可能已经注意到了我们使用的 ToDouble 函数，它是普通类型范畴内的一个态射，我们仅仅通过一个 Select 函数就把普通类型范畴内的一个态射映射成了 List<T> 范畴内的一个态射（上面的例子中，是把 (int -> double) 转换成了 (List<int> -> List<double>)），而且 List<T> 还提供了能够把 int 类型转换成 List<int> 类型（type）的方法：new List<int>{ intValue }，那么我们就可以把 List<T> 类（class）称为“函子”。事情变得有趣了起来。

List<T> 还有一个构造函数可以允许我们使用另一个 List 对象创建一个新的 List 对象：new List<T>(list)，这完成了 List<T> -> List<T> 转换，这看起来像是把 List<T> 范畴中的元素重新映射到了 List<T> 范畴中。有了这个构造函数的帮助，我们就可以试着使用 Select 来映射 List<T> 中的态射（比如，ToDoubleList）:

  1. // 这个映射后的 ToDoubleListAgain 仍然能够正常的工作
  2. Func<List<int>, List<List<double>>> ToDoubleListAgain = x => x.Select(e => ToDoubleList(new List<int>(){e})).ToList();

这里的返回值类型看起来有些奇怪，我们得到了一个嵌套两层的 List，如果你熟悉 LINQ 的话，马上就会想到 SelectMany 函数——它能够把嵌套的 List 拍扁：

  2. Func<List<TV>, List<TR>> FF<TV, TR>(Func<List<TV>, List<TR>> selector)
  3. {
  4.     return xl => xl.SelectMany(x => selector(new List<int>() {x})).ToList();
  5. }
  7. var ToDoubleListAgain = FF(ToDoubleList);
  8. ToDoubleListAgain(new List<int>{1})

这样，我们就实现了 (List<T1> -> List<T2>) -> (List<T1> -> List<T2>) 的映射，虽然功能上并没有什么卵用，但是却实现了把 List<T> 范畴中的态射映射到了 List<T> 范畴中的功能。现在看来，List<T> 类不仅是普通类型映射到 List<T> 的一个函子，它也是 List<T> 映射到 List<T> 的一个函子。这种能够把一个范畴映射到该范畴本畴上的函子也被称为“自函子”。

我们可以发现，C# 中大部分的自函子都通过 LINQ 拓展方法实现了 SelectMany 函数，其签名是：

  1. SomeType<TR> SelectMany<TV, TR>(SomeType<TV> source, Func<TV, SomeType<TR>> selector);

List<T> 还有一个不接受任何参数的构造函数，它会创建出一个空的列表，我们可以把这个函数称作 unit，因为它的返回值在 List<T> 相关的一些二元运算中起到了单位 1 的作用。比如，concat(unit(), someList) 与 concat(someList, unit()) 得到的列表，在结构上是等价的。拥有这种性质的元素被称为“单位元”。

在函数式编程中，我们把拥有 SelectMany（也被叫做 bind），unit 函数的自函子称为“Monad”。

但是 C# 中并不是所有的泛型类是自函子，例如 Task<T>，如果我们不为它添加 Select 拓展方法，它连函子都算不上。所以如果把 C# 中全部的自函子类型放在一个集合中，然后把这些自函子类型之间用来做类型转换的全部函数（例如，list.ToArray() 等）看作是态射，那么我们就构建出来了一个 C# 中的“自函子范畴”。在这个范畴上，我们只能对 Monad 类型使用 LINQ 语法进行复合运算，例如上面的：

  1. // 原版
  2. var result =
  3. from a in taskA
  4. from b in taskB
  5. from c in taskC
  6. select a * b + c;
  8. // 1. 满足结合律
  9. var left =
  10. from a in taskA
  11.     from t in (
  12.         from b in taskB
  13.         from c in taskC
  14.         select new {b, c}
  15.     )
  16. select a * t.b + t.c;
  18. var left =
  19. from t in (
  20.     from a in taskA
  21.     from b in taskB
  22.     select new {a, b}
  23. )
  24. from c in taskC
  25. select t.a * t.b + c;
  27. left == right
  28. // true
  30. // 2. 存在单位元
  32. var left =  from a in Task.FromException(null)
  33.             from b in taskB
  34.             select a + b;
  36. var right = from b in taskB
  37.             from a in Task.FromException(null)
  38.             select a + b;
  40. // 因为 left right 得到的都是 Task.FromException(null) 的返回值，故 Task.FromException(null) 是单位元

由于这种作用在两个 Monad 上面的二元运算满足交换律且 Monad 中存在单位元，与群论中幺半群的定义比较类似，所以，我们也把 Monad 称为“自函子范畴上的幺半群”。尽管这句话听起来十分的高大上，但是却并没有说明 Monad 的特征所在。就好比别人跟你介绍手机运营商，说这是一个提供短信、电话业务的公司，你肯定不知道他到底再说哪一家，不过他要是说，这是一个提供 5 元 30 M 流量包的手机运营商，那你就知道了他指的是中国移动。

其实我一开始想写的内容只有 LINQ to Result 跟 LINQ to Task 的，但是在编写代码的过程中，种种迹象都表明着 LINQ 跟函数式编程中的 Monad 有不少关系，所以就把剩下的函数式编程这一部分给写出来了。

Monad 作为函数式编程中一种重要的数据类型，可以用来表达计算中的每一小步的功能，通过 Monad 之间的复合运算，我们可以灵活的将这些小的功能片段以一种统一的方式重组、复用，除此之外，我们还可以针对特定的需求（异步、错误处理、懒惰计算）定义专门的 Monad 类型，帮助我们以一种统一的形式将这些特别的功能嵌入到代码之中。在传统的面向对象的编程语言中 Monad 这个概念确实是不太好表达的，不过有了 LINQ 的帮助，我们可以比较优雅地将各种 Monad 组合起来。

用 LINQ 来对 Monad 进行运算的缺点，主要就是除了 SelectMany 之外的，我们没办法定义其他的能在 Query 语法中使用的函数了，要解决这个问题，请关注我的下一篇文章：“F# 函数式编程：Computational Expression”（挖坑预备）。

  1. https://zh.wikipedia.org/zh-hans/函子
  2. https://en.wikipedia.org/wiki/Monad_(functional_programming)
  3. http://hongjiang.info/understand-monad-4-what-is-functor/

版权声明：本文为JacZhu原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/JacZhu/p/9729587.html