F# 与 C# 对比：排序

内容导航

一个函数式风格的 C# 实现
正确性
后记

在接下来的例子中，我们将实现一个类快排的算法来对列表进行排序，并且对比 F# 实现与 C# 实现的差异。

下面是一个简化版的快排算法描述：

如果列表是空的，那么啥也不干
否则
	1. 取出列表中的第一个元素
    2. 在剩余元素中找出所有小于第一个元素的元素，然后对它们排序
    3. 在剩余元素中找出所有大于等于第一个元素的元素，然后对它们排序
    4. 将这三个部分组合起来得到最终的结果：
    	有序的较小元素 + 第一个元素 + 有序的较大元素

为了方便说明，这里给出的是个非常简化的算法，没有进行任何优化（而且与真正的快排不同，它并不是在原地排序）

先来看看 F# 实现：

let rec quicksort list =
   match list with
   | [] ->                            // 如果列表是空的
        []                            // 直接返回空列表
   | firstElem::otherElements ->      // 如果列表不是空的
        let smallerElements =         // 找出较小的元素
            otherElements
            |> List.filter (fun e -> e < firstElem)
            |> quicksort              // 然后对它们排序
        let largerElements =          // 找出较大的元素
            otherElements
            |> List.filter (fun e -> e >= firstElem)
            |> quicksort              // 然后对它们排序
        // 将这三部分组成新的列表，然后返回出去
        List.concat [smallerElements; [firstElem]; largerElements]

//test
printfn "%A" (quicksort [1;5;23;18;9;1;3])

再次注意，这是一个完全没有优化的实现，是为了更准确地说明这个算法而设计的。

现在让我们过一遍这份代码：

任何地方都没有类型声明。这个函数可以处理任何包含可比较元素的列表（几乎所有的 F# 类型都实现了默认的比较函数）。
使用了 rec 关键字来声明函数，告诉编译器这个函数是可以递归调用的。
match .. with 类似与 switch/case 语句。每个分支都使用一个竖线来表示，例如：

match x with
| caseA -> something
| caseB -> somethingElse

match 跟 [] 匹配空的列表，并且返回空的列表
match 跟 firstElem::otherElements 做了两件事。
- 第一，它只匹配非空的列表
- 第二，它自动的创建了两个新的值。一个表示列表中的第一个元素，也就是 firstElem，另一个值表示列表中剩余的元素，也就是 otherElements。从 C# 的角度看，这就像是 switch 语句不仅仅支持分支，还可以同时用来声明变量并对其赋值。
→ 类似 C# 中的 lambda （⇒）。与之等价的 C# 代码长这样：
```
(firstElem, otherElements) => do something
```
smallerElements 代码块首先将列表的剩余部分通过一个内联的 lambda 进行过滤，这个 lambda 将每个元素使用 < 运算符跟第一个元素进行比较。接着将过滤结果通过管道传递给快排函数本身，实现了递归调用。
largerElements 代码块也做了类似的事情，只不过将 < 换成了 >=。
最终的结果列表由列表拼接函数 List.concat 拼接而成。为了满足参数类型要求，第一个元素被单独的扔进了一个列表中（[firstElem]）。
再次注意，没有 return 关键字，最后一个表达式的值就是函数返回值。在 [] 分支中，返回值就是空列表，另一个分支中，返回值就是刚刚创建出来的列表。

这里是作为对比的传统的 C# 实现。

public class QuickSortHelper
{
   public static List<T> QuickSort<T>(List<T> values)
      where T : IComparable
   {
      if (values.Count == 0)
      {
         return new List<T>();
      }

      // 获取第一个元素
      T firstElement = values[0];

      // 获取较小与较大的元素
      var smallerElements = new List<T>();
      var largerElements = new List<T>();
      for (int i = 1; i < values.Count; i++)  // i 从 1 而不是从 0 开始
      {
		var elem = values[i];
		if (elem.CompareTo(firstElement) < 0)
        {
           smallerElements.Add(elem);
        }
        else
        {
           largerElements.Add(elem);
        }
      }

      // 返回结果
      var result = new List<T>();
      result.AddRange(QuickSort(smallerElements.ToList()));
      result.Add(firstElement);
      result.AddRange(QuickSort(largerElements.ToList()));
      return result;
   }
}

比较这两段代码，你就会再次发现 F# 代码更加的简洁，没有多余的语法噪音以及类型声明。

除此之外，F# 代码读起来更像我们一开始所写的算法描述，这就是 F# 另一个关键优势 —— 代码更偏向声明式（要做什么）而不是想 C# 一样的命令式（怎么去做），因此代码本身看起来就更像是文档。

一个函数式风格的 C# 实现

这里给出一个更加现在的函数式风格的 C# 代码实现，同样地使用到了 LINQ 拓展：

public static class QuickSortExtension
{
    /// <summary>
    /// Implement as an extension method for IEnumerable
    /// </summary>
    public static IEnumerable<T> QuickSort<T>(
        this IEnumerable<T> values) where T : IComparable
    {
        if (values == null || !values.Any())
        {
            return new List<T>();
        }

        // 将列表分割成第一个元素与剩余元素两个部分
        var firstElement = values.First();
        var rest = values.Skip(1);

        // 获取较小以及较大的元素
        var smallerElements = rest
                .Where(i => i.CompareTo(firstElement) < 0)
                .QuickSort();

        var largerElements = rest
                .Where(i => i.CompareTo(firstElement) >= 0)
                .QuickSort();

        // 返回结果
        return smallerElements
            .Concat(new List<T>{firstElement})
            .Concat(largerElements);
    }
}

这个实现看起来更加的清晰明了，读起来也更加接近 F# 版本。但不幸的是仍然没有办法来避免函数签名中的语法噪音。

正确性

最后，这种简洁明了带来的一个有益的副作用是 F# 代码通常在一开始就能正常工作，而 C# 代码可能需要我们花更多的时间去 debug。

事实上，当编写这些样例的时候，传统风格的 C# 代码一开始就被写错了。特别是在 for 循环设置 i 的初始值以及确定 CompareTo 参数顺序的时候（我在这里弄反了比较顺序），而且输入的列表还会很容易地被我们意外地修改。在第二个函数式的 C# 实现中，不仅代码更加明了，而且这些易错的地方也不复存在。

不过就算是函数式的 C# 跟 F# 比起来还是有一些弊端。举个例子，F# 使用了模式匹配来避免空列表被处理非空列表的分支处理。而在 C# 实现中，如果我们忘了这个条件：

if (values == null || !values.Any()) ...

那么当我们尝试取第一个元素的时候：

var firstElement = values.First();

就会抛出异常，编译器在这方面帮不了你的忙。你想想，在你的代码中，你有多少次使用 FirstOrDefault 而不是 First 来进行防御式编程。下面这个例子通常会出现在 C# 代码中，但在 F# 中非常少见：

var item = values.FirstOrDefault();  // instead of .First()
if (item != null)
{
   // do something if item is valid
}

在 F# 中，模式匹配将这些动作一步到位，避免这种代码在你的项目中出现。

后记

其实前面例子中提供的 F# 实现相对于标准的 F# 代码来说还是太冗余了！下面是一个更加典型的简明版本（只是为了想秀一下）：

let rec quicksort2 = function
   | [] -> []
   | first::rest ->
        let smaller,larger = List.partition ((>=) first) rest
        List.concat [quicksort2 smaller; [first]; quicksort2 larger]

// test code
printfn "%A" (quicksort2 [1;5;23;18;9;1;3])

仅需 4 行代码，如果你熟悉了 F# 语法，这样的写法仍然具有一定的可读性。