有人可以帮忙解释一下这个归并排序算法是如何工作的吗？

Question

我昨天开始学习 F#，但对所有新的函数式编程都有些吃力。

我试图理解使用拆分函数的合并排序的实现。拆分函数定义为：

let rec split = function
    | [] -> ([], [])
    | [a] -> ([a], [])
    | a :: b :: cs -> let (r, s) = split cs
                      in (a :: r, b :: s)

按照我的理解，我们采用一个列表和 return 一个列表元组，将列表分成两半。如果我们在空列表上进行模式匹配，我们 return 一个空列表的元组，如果我们在一个包含一个元素的列表上匹配，我们 return 一个包含列表和空列表的元组，但是递归情况是躲着我。

a :: b :: cs 意思是a prepended to b prepended to cs，对吧？所以这是列表至少有 3 个元素的情况？如果是这样，我们 return 两个值，r 和 s，但我以前没有看到使用过这个“in”关键字。据我所知，我们将第一个元素 a 添加到 r，将第二个元素 b 添加到 s，然后拆分列表的其余部分 cs。但这对我来说似乎并没有把列表分成两半。

谁能帮忙解释一下递归案例是如何工作的？非常感谢。

Answer 1

当列表中只有两项时，cs 为 []。当列表中有 3 个或更多项时，它会递归，其中 cs 是没有前两项的列表。当只有一项时 returns [a],[] 列表为空时 returns [],[] .

Answer 2

在这种情况下，您可以忽略 in 关键字，因此您可以将最后一种情况解读为：

| a :: b :: cs ->
    let (r, s) = split cs
    (a :: r, b :: s)

请注意，这将匹配任何长度为 2 或更大的列表，而不是您最初认为的 3。当列表恰好有两个元素时，cs 将是空列表。

所以在这种情况下发生的事情是：

如果列表至少有 2 个元素：
- 命名第一个元素a
- 命名第二个元素b
- 为列表的其余部分命名 cs（即使它是空的）
- 递归拆分cs，这给了我们两个新列表，r和s
- 再创建两个新列表：
  - r前面有a的一个
  - 另一个s
- Return 两个新列表

你 can see this in operation 如果你这样调用函数:

split [] |> printfn "%A"                // [],[]
split [1] |> printfn "%A"               // [1],[]
split [1; 2] |> printfn "%A"            // [1],[2]
split [1; 2; 3] |> printfn "%A"         // [1; 3],[2]
split [1; 2; 3; 4] |> printfn "%A"      // [1; 3],[2; 4]
split [1; 2; 3; 4; 5] |> printfn "%A"   // [1; 3; 5],[2; 4]

更新：in到底是做什么的？

in 关键字只是一种将 let 绑定放入表达式中的方法。因此，例如，我们可以编写 let x = 5 in x + x，这是一个具有值 10 的表达式。这种语法继承自 OCaml，当您想将整个表达式写在一行时仍然有用。

在现代 F# 中，我们可以使用 whitespace/indentation，方法是将 in 关键字替换为换行符。所以现在，我们通常会这样写这个表达式：

let x = 5
x + x

这两种形式在语义上是等价的。更多详情 here.

有人可以帮忙解释一下这个归并排序算法是如何工作的吗？

Can someone please help explain how this merge sort algorithm works?

sorting

f#

functional-programming