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 

を、私は一連のを変更したいです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には1つの数字が入っていた。このように、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＃は、に適用されるwhen句を0ケースまたは_のいずれかに適用することを意味すると理解しています。 （これはもちろん冗長です）。

これは例外の原因です：F＃は、0ケースを見ても、when chunkB.[0] < chunkA.[0]テストを適用します。chunkAは空ですので、常に例外をスローします。

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

残念ながら、これはコードの一部重複を意味している。これを修正するには、whenはそれを適用するためにあなたが意味する場合のみに適用されるように、これらの2つの場合を分離する必要があります。この場合、重複したコードは1つのライナーであるため大したことではありませんが、このような2つのケースを分割する必要があるため重複してしまうコードの重要な部分があるとします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＃が配列をスライスするために非常に便利な構文を持っている：startとendはスライスあなたの包括的指標であるarray.[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を超える場合、array.[middle .. array.Length - 1]の式はになります。これは正確に[| array.[middle] |]に相当します。

したがって、mergesortへの呼び出しでなければ、これらの2つの式を統合できます。そして、実際にそうするための非常に簡単な方法があります！

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の2例を統合することができます：

を単純にそうように、 mergesortの上部に長さチェックを動かします一緒にこのすべてを置く

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ループ0回（すなわち、forループのボディ実行されない）。同様に、array.[0..-1]はエラーではありませんが、空の配列が生成されます。その詳細を知っていれば、元のmergesort関数のコードを処理し、空の文字列を渡すと無限ループすることがわかります。 （無限ループのあなたのmergesortコールがテールポジションではないので、テールコールではないので、スタックは最終的にオーバーフローし、あなたを「真の」無限ループから守ります）。