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) 

는 비주얼 스튜디오는 특히 여기, 나에 "IndexOutOfRangeException"를 던졌다 :

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

를이 경우, chunkA 비었지만 chunkB에 하나의 숫자가있었습니다. 따라서 청크 A와 B의 길이가 같지 않기 때문에 F #이이 사례를 반환하려고 시도한 이유가 무엇인지 확신 할 수 없습니다.하지만 빈 배열에 색인 오류가 발생하는 이유에 대해 혼란 스럽습니다. .

또한 F # 및 함수 프로그래밍 전반에 대해 다소 새로운 점이 있습니다. 내 코드의 구조 또는 방법론이 동등하지 않은 경우에도이 점에 대해 자유롭게 의견을 말하십시오.

또한 두께가 두꺼울 경우 나에게도 알려주세요. 표도르 Soikin는 지적

많은 덕분에, 누가 복음

Answer 1

, 당신의 예외의 원인이 라인 :

| 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 그것을 적용하는 뜻에만 경우에 적용되도록,이 두 케이스를 분리해야합니다. 중복 된 코드가 한 줄짜리 코드이기 때문에이 경우 큰 문제는 아니지만 이처럼 두 가지 사례를 나눠야하기 때문에 중복 된 코드가 상당하다면 (두 사례가 공유하면 안되는 부분) 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이 정확히 1보다 큰 경우 middle 일 때 array.[middle .. array.Length - 1] 표현은 입니다. 정확히 [| array.[middle] |]과 같습니다.

따라서 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의 두 경우를 통합 할 수 있습니다 : 간단히과 같이, 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 

이 절의 버전에는 원래 버전의 미묘한 버그가 없습니다. 빈 배열의 경우를 잊어 버렸습니다. 빈 배열에 원래 mergesort을 호출하면 무한 루프가 생성됩니다. 어떻게 설명하는지 직접 설명하는 것보다 더 많은 도움이 될 것입니다. F # for i in 0 .. -1에서 오류는 아니지만 for 루프를 0 번 반복합니다 (즉, for 루프의 본문은 실행되지 않음). 마찬가지로 array.[0..-1]은 오류가 아니지만 빈 배열을 생성합니다. 그 세부 지식으로 무장하면 원래 mergesort 함수의 코드를 처리하고 빈 문자열을 전달하면 루프가 무한 루프 할 수 있어야합니다. (무한 루프를 호출하면 mergesort이 꼬리 위치에 있지 않기 때문에 꼬리 호출이 아니기 때문에 스택이 결국 오버플로되어 "실제"무한 루프를 방지 할 수 있습니다.)