不確定遞歸排序功能？

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函數的輸出是多少與輸入？