目录:网上冲浪指南

F# 与 C# 对比:排序

2020/03/18

在接下来的例子中,我们将实现一个类快排的算法来对列表进行排序,并且对比 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])

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

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

  1. 任何地方都没有类型声明。这个函数可以处理任何包含可比较元素的列表(几乎所有的 F# 类型都实现了默认的比较函数)。

  2. 使用了 rec 关键字来声明函数,告诉编译器这个函数是可以递归调用的。

  3. match .. with 类似与 switch/case 语句。每个分支都使用一个竖线来表示,例如:

match x with
| caseA -> something
| caseB -> somethingElse
  • match[] 匹配空的列表,并且返回空的列表

  • matchfirstElem::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# 语法,这样的写法仍然具有一定的可读性。