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