Comparing F# with C#: Sorting

https://swlaschin.gitbooks.io/fsharpforfunandprofit/content/posts/fvsc-quicksort.html

在下一个示例中，我们将实现类似快速排序的算法来对列表进行排序，并将 F# 实现与 C# 实现进行比较。

以下是简化的类似快速排序算法的逻辑：

如果列表为空，则无事可做。
否则：
1. 取列表的第一个元素
2. 在列表的其余部分找到所有小于第一个元素的元素，并对它们进行排序。
3. 在列表的其余部分中找到所有大于等于第一个元素的元素，并对它们进行排序
4. 将三部分组合在一起得到最终结果：
（已排序的较小元素 + firstElement + 排序较大的元素）

请注意，这是一个简化的算法，没有经过优化（而且它没有像真正的quicksort那样进行原地排序）；我们现在要关注的是语法的清晰度。

这是 F# 中的代码：

let rec quicksort list =
   match list with
   | [] ->                            // If the list is empty
        []                            // return an empty list
   | firstElem::otherElements ->      // If the list is not empty     
        let smallerElements =         // extract the smaller ones    
            otherElements             
            |> List.filter (fun e -> e < firstElem) 
            |> quicksort              // and sort them
        let largerElements =          // extract the large ones
            otherElements 
            |> List.filter (fun e -> e >= firstElem)
            |> quicksort              // and sort them
        // Combine the 3 parts into a new list and return it
        List.concat [smallerElements; [firstElem]; largerElements]

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

再次注意，这不是优化的实现，而是旨在说明算法在语法上的密度。

让我们看一下这段代码：

• 任何地方都没有类型声明。此函数适用于任何具有可比较项的列表（几乎所有 F# 类型，因为它们自动具有默认比较函数）。

• 整个函数是递归的——这是使用“let rec quicksort list =”中的 rec 关键字向编译器发出信号。

• match..with 有点像 switch/case 语句。每个要测试的分支都用竖线表示，如下所示：

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

• [] “模式” 会“匹配”一个空列表，并返回一个空列表。

• 与 firstElem::otherElements 的“模式匹配”做了两件事。

  • 首先，它只匹配一个非空列表。

  • 第二，它自动创建两个新的值。一个用于第一个元素，称为 "firstElem"，另一个用于列表的其他部分，称为 "otherElements"。用C#的话说，这就像有一个 "switch"语句，它不仅是分支，而且同时进行变量声明和赋值。

• -> 有点像 C# 中的 lambda (=>)。等效的 C# lambda 看起来像 (firstElem, otherElements) => 函数体。

• “smallerElements”部分获取列表的其余部分，使用带有“<”运算符的内联 lambda 表达式针对第一个元素以外的其他元素，使用第一个元素进行过滤，然后将结果递归地传递到快速排序函数中。

• “largerElements”行做同样的事情，除了使用“>=”运算符

• 最后，使用列表连接函数“List.concat”构造结果列表。为此，需要将第一个元素放入列表中，这就是方括号的作用。

• 再次注意没有“return”关键字；最后一个值将被返回。在“[]”分支中，返回值为空列表，在主分支中，返回值为新构造的列表。【也就是这一切都是表达式的组合，没有显式return，中间看到的赋值啥的，也只是某个表达式的表达而已，实际上如果用lazy的方式来看，到实际发起求值以前，一切都只是符号系统的积累，只有到实际求值的时候才会出现真正的计算，当然，由于CLR本身式严格求值的，所以这个说法本身在F#里是不成立的，但是这么思考会有助于理解什么是表达式的组合这个概念】

为了进行比较，这里有一个旧式 C# 实现（不使用 LINQ）。

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

      //get the first element
      T firstElement = values[0];

      //get the smaller and larger elements
      var smallerElements = new List<T>();
      var largerElements = new List<T>();
      for (int i = 1; i < values.Count; i++)  // i starts at 1
      {                                       // not 0!
         var elem = values[i];
         if (elem.CompareTo(firstElement) < 0)
         {
            smallerElements.Add(elem);
         }
         else
         {
            largerElements.Add(elem);
         }
      }

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

比较两组代码，我们再次可以看到 F# 代码更紧凑，噪音更小，并且不需要类型声明。

此外，与 C# 代码不同，F# 代码读起来几乎与实际算法完全一样。这是 F# 的另一个关键优势——与 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>();
        }

        //split the list into the first element and the rest
        var firstElement = values.First();
        var rest = values.Skip(1);

        //get the smaller and larger elements
        var smallerElements = rest
                .Where(i => i.CompareTo(firstElement) < 0)
                .QuickSort();

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

        //return the result
        return smallerElements
            .Concat(new List<T>{firstElement})
            .Concat(largerElements);
    }
}

这更简洁，并且与 F# 版本几乎相同。但不幸的是，没有办法避免函数签名中的额外噪音。

Correctness 正确性

最后，这种紧凑性的一个有益的副作用是 F# 代码通常一次就能运行，而 C# 代码可能需要更多调试。

事实上，在编写这些示例时，旧式 C# 代码最初是不正确的，需要进行一些调试才能使其正确。特别棘手的地方是 for 循环（从 1 而不是零开始）和 CompareTo 比较（我弄错了方法），而且很容易意外修改原始列表。第二个 C# 示例中的函数式风格不仅更简洁，而且更容易正确编码。

但与 F# 版本相比，即使是函数式 C# 版本也有缺点。例如，因为 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# 中的一步“模式匹配和分支”使您在许多情况下可以避免这种情况。

Postscript 后记

按照 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行代码还挺好理解的，而且当你习惯了语法之后，还是很好读的。