F# 合并排序 - 尝试实现与结构的匹配时出现 IndexOutOfRangeException

Question

我的合并排序的整体代码看起来像这样：

   let remove array = 
    Array.sub array 1 (array.Length - 1)

let rec merge (chunkA : int[]) (chunkB : int[]) =
    if chunkA.Length = 0 && chunkB.Length = 0 then [||]
    else if chunkA.Length = 0 || chunkB.[0] < chunkA.[0] then Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
    else Array.append [| chunkA.[0] |] (merge (remove chunkA) chunkB)

let rec mergesort (array : int[]) =
    let middle = array.Length / 2
    let chunkA = match middle with
                    | 1 -> [| array.[0] |]
                    | _ -> mergesort  [| for i in 0 .. middle - 1 -> array.[i]|]
    let chunkB = match array.Length - middle with
                    | 1 -> [| array.[array.Length - 1] |]
                    | _ -> mergesort [| for i in middle .. array.Length - 1 -> array.[i]|]
    merge chunkA chunkB

此代码运行良好，但我想将 merge 函数中的一系列 if 语句更改为 match with 语句。

然后我尝试实现以下代码：

let rec merge (chunkA : int[]) (chunkB : int[]) =
match chunkA.Length with
| 0 when chunkA.Length = chunkB.Length -> [||]
| 0 | _ when chunkB.[0] < chunkA.[0] -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
| _ -> Array.append [| chunkA.[0] |] (merge (remove chunkA) chunkB)

当我运行我的代码时，Visual Studio 向我扔了一个 "IndexOutOfRangeException"，特别是这里：

| 0 when chunkA.Length = chunkB.Length -> [||]

在这种情况下，chunkA 是空的，但 chunkB 中只有一个数字。因此，我不完全确定为什么 F# 甚至尝试 return 这种情况，因为块 A 和 B 的长度不一样，但我也很困惑为什么这会引发索引错误，特别是在空数组上。

此外，我对 F# 和一般的函数式编程还比较陌生。如果我的代码中的结构或方法不符合标准，那么也请随时对此发表评论。

另外，如果我脸皮厚，也请尽管告诉我。

非常感谢，卢克

Answer 1

正如 Fyodor Soikin 所指出的，异常的来源是这一行：

| 0 | _ when chunkB.[0] < chunkA.[0] -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))

但您可能不太清楚为什么会抛出异常。，匹配表达式中的 when 子句适用于所有自上一个 -> 以来的情况。换句话说，当您编写上面的行时，F# 理解您的意思是您希望将 when 子句应用于或者 0 案例或 _ 案例。（这当然是多余的）。

这就是你的异常的原因：F# 看到了 0 的情况，但仍然应用 when chunkB.[0] < chunkA.[0] 测试——因为 chunkA 是空的，所以总是会抛出异常.要解决此问题，您必须将这两种情况分开，以便 when 仅适用于您要适用的情况：

| 0 -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
| _ when chunkB.[0] < chunkA.[0] -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))

不幸的是，这确实意味着一些重复代码。在这种情况下，这没什么大不了的，因为重复的代码是单行代码，但是如果您有大量代码最终因为必须拆分成这样的两种情况而重复（这两种情况不应该共享） when 条件），那么你可以将重复的块变成一个函数，这样它就不再重复了。

编辑： 我刚刚注意到您的代码中有一部分可以更简单。您的原始代码包括：

let chunkA = match middle with
                | 1 -> [| array.[0] |]
                | _ -> mergesort  [| for i in 0 .. middle - 1 -> array.[i]|]
let chunkB = match array.Length - middle with
                | 1 -> [| array.[array.Length - 1] |]
                | _ -> mergesort [| for i in middle .. array.Length - 1 -> array.[i]|]

您在这里所做的是获取数组的一部分，但是 F# 有一个非常方便的切片数组语法：array.[start..end] 其中 start 和 end 是包含值你想要的切片的索引。所以表达式 [| for i in 0 .. middle - 1 -> array.[i]|] 可以简化为 array.[0 .. middle - 1]，表达式 [| for i in middle .. array.Length - 1 -> array.[i]|] 可以简化为 array.[middle .. array.Length - 1]。让我们替换您的代码中的这些表达式，看看我们得到什么：

let chunkA = match middle with
                | 1 -> [| array.[0] |]
                | _ -> mergesort  array.[0 .. middle - 1]
let chunkB = match array.Length - middle with
                | 1 -> [| array.[array.Length - 1] |]
                | _ -> mergesort array.[middle .. array.Length - 1]

现在，看看这个，我注意到两种情况下的 1 条件实际上处理的是与 _ 条件完全相同的数组切片；唯一的区别是，如果 middle 为 1，则不会调用 mergesort。我怎么知道它是完全相同的数组切片？好吧，如果 middle 是 1，那么 array.[0 .. middle-1] 表达式将变成 array.[0..0]，它是数组中从索引 0 开始的长度为 1 的切片，正好等同于 [| array.[0] |] .如果 array.Length 正好比 middle 多 1，那么 array.[middle .. array.Length - 1] 表达式将是 array.[middle .. middle]，这正好等同于 [| array.[middle] |].

所以如果不是调用mergesort，我们可以合并这两个表达式。事实上，有一种非常简单的方法可以做到这一点！只需将长度检查移动到 mergesort 的顶部，如下所示：

let rec mergesort (array : int[]) =
    if array.Length < 2 then
        array  // Arrays of length 0 or 1 are already sorted
    else
        // rest of mergesort function goes here

现在您可以安全地合并 match 的两个案例，知道您不会遇到无限递归循环：

let middle = array.Length / 2
let chunkA = mergesort array.[0 .. middle - 1]
let chunkB = mergesort array.[middle .. array.Length - 1]
merge chunkA chunkB

将所有这些放在一起，我建议的原始 mergesort 函数版本如下所示：

let rec mergesort (array : int[]) =
    if array.Length < 2 then
        array  // Arrays of length 0 or 1 are already sorted
    else
        let middle = array.Length / 2
        let chunkA = mergesort array.[0 .. middle - 1]
        let chunkB = mergesort array.[middle .. array.Length - 1]
        merge chunkA chunkB

作为奖励，此版本的 mergesort 没有原始版本的细微错误：您忘记考虑空数组的情况。在空数组上调用原始 mergesort 会产生无限循环。与我解释方法相比，您自己解决问题可能会受益更多，所以我只提一下，在 F# 中 for i in 0 .. -1 不是错误，但会经历 for 循环零次（即，for 循环体不会被执行）。同样，array.[0..-1] 不是错误，但会产生一个空数组。了解该细节后，您应该能够处理原始 mergesort 函数的代码，并发现如果您向它传递一个空字符串，它会无限循环。（尽管由于你在那个无限循环中的 mergesort 调用不在尾部位置，所以它不会是尾部调用。因此堆栈最终会溢出，从而使你免于 "true" 无限循环）。

F# 合并排序 - 尝试实现与结构的匹配时出现 IndexOutOfRangeException

F# Merge Sort - IndexOutOfRangeException when attempting to implement a match with structure

arrays

recursion

mergesort

f#

outofrangeexception