不确定递归排序功能？

Question

我只想了解这个功能发生了什么，特别是第三种情况。谢谢！

let rec sort = function 
    | []   -> [] 
    | [x]  -> [x] 
//need help understanding line below 
    | x1::x2::xs -> if x1 <= x2 then x1 :: sort (x2::xs) 
            else x2 :: sort (x1::xs) 

Answer 1

的::运营商在F＃是一个列表操作符，通常是这样的：

head :: rest 

这里，head是列表的第一个项目，rest是列表的其余部分。即，

let rest = [2; 3; 4] 
let head = 1 
head :: rest // Has the value [1; 2; 3; 4] 

注意不同的类型：head是单个项目和rest是项目的列表。

现在，::运算符可用于模式匹配或作为运算符来实际构建列表。它具有相同的含义，但是在模式匹配中，你只是说“匹配如果列表具有这种形状”，而模式匹配语法之外，你说“使列表有这个形状”。因此，在模式匹配，你必须：

let describe lst = 
    match lst with 
    | [] -> "Empty list" 
    | head::rest -> sprintf "Head is %A and rest is %A" head rest 
describe [1; 2; 3; 4] 
// Result: "Head is 1 and rest is [2; 3; 4]" 

需要注意的是只有一个项目的名单是完全有效的匹配对head::rest模式，在这种情况下rest将只是一个空列表：

let describe lst = 
    match lst with 
    | [] -> "Empty list" 
    | head::rest -> sprintf "Head is %A and rest is %A" head rest 
describe [1] 
// Result: "Head is 1 and rest is []" 

的::操作者也可以多次应用：

let describe lst = 
    match lst with 
    | [] -> "Empty list" 
    | [x] -> sprintf "List of just one item, %A" x 
    | first::second::rest -> sprintf "First item is %A and second item is %A and rest is %A" first second rest 
describe [1; 2; 3; 4] 
// Result: "First item is 1 and second item is 2 and rest is [3; 4]" 

注意我如何加入的情况下，一个项目有一个列表？这是因为如果您将匹配的形状与first::second::rest相匹配，则只有与匹配，如果列表中至少有两个项目。只有一个项目的列表将不会将任何东西放入second，因此不会匹配。如果我在这个最新示例中忽略了[x]模式，编译器会警告我，我的匹配表达式不完整。

所以，现在我们可以看到你match表达的最后一行是这样做的：。

| x1::x2::xs -> if x1 <= x2 then x1 :: sort (x2::xs) 
          else x2 :: sort (x1::xs) 

的图案说：“比赛如果此列表中有至少两项产品调用的第一个项目x1，然后拨打第二个项目x2，然后拨打清单xs的其余部分。“然后它比较列表的第一项和第二项。两者中较小的一个作为函数输出的第一项，函数输出的“休息”是“取较大的项目，将其加到xs列表中，然后通过sort函数”。

顺便说一句，你能发现这个函数中的错误吗？如果没有，考虑一下它会与下面的列表做：

[3; 4; 2; 1] 

将这个sort函数的输出是多少与输入？