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

Question

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

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

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

按照我的理解，我们获取一个列表并返回一个列表元组，将列表分成两半。如果我们在空列表上进行模式匹配，我们会返回一个空列表的元组，如果我们在一个包含一个元素的列表上进行匹配，我们会返回一个包含该列表和一个空列表的元组，但递归情况让我难以理解。

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

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

Answer 1

在这种情况下，您可以忽略 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的前面带有b
  • 返回两个新列表

你 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 绑定(bind)到表达式中的方法。因此，例如，我们可以编写 let x = 5 in x + x，这是一个值为 10 的表达式。这种语法继承自 OCaml，当您想将整个表达式写在一行时仍然有用。

在现代 F# 中，我们可以改用空格/缩进，方法是将 in 关键字替换为换行符。所以现在，我们通常会这样写这个表达式:

let x = 5
x + x

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