F＃合并排序 - 试图实现与结构

Question

我归并排序总码匹配时IndexOutOfRangeException，看起来是这样的：

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 

此代码工作得很好，但我想改变系列if语句中的merge函数为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＃甚至试图返回这种情况，因为块A和B的长度不一样，但我也很困惑，为什么这会抛出索引错误，特别是在空数组上。

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

另外，如果我很厚，请随时告诉我。

非常感谢， 卢克

Answer 1

正如陀Soikin指出的那样，你的异常的来源是这一行：

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

但为什么多数民众赞成抛出一个异常，它可能不是很明显你。 As I learned last week to my surprise,when子句中的匹配表达式适用于全部以前的案例->。换句话说，当你写上面的线，F＃理解你的意思，你要应用到要么的0情况或的_情况when条款。 （当然这是多余的）。

这就是你例外的原因：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条件在这两种情况下，实际处理完全相同的阵列片作为_条件;唯一的区别是，如果中间值为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 

作为奖励，这款v mergesort的版本没有您原始版本的微妙错误：您忘记考虑空数组的情况。在空数组上调用原始mergesort会产生无限循环。你可能会从中得到更多的好处，而不是从我这里解释如何，所以我只想提到在F＃for i in 0 .. -1不是错误，而是会通过for循环零次（即for循环的主体将会不被执行）。同样，array.[0..-1]不是错误，但会产生一个空数组。掌握了这些细节的知识后，您应该能够完成原始mergesort函数的代码，并且如果您传递了空字符串，它将无限循环。 （虽然你的mergesort这个无限循环中的调用不是尾部调用，但它不会是尾部调用，所以栈最终会溢出，从而避免出现“真正的”无限循环）。