하나의 재귀 함수와 foldBack 함수로 삽입 정렬 구현

Question

일부 기본 데이터 구조와 해당 알고리즘에서 작동하는 알고리즘에 대한 구현을 검토 중입니다.

let rec insert x = function 
    | [] -> [x] 
    | y::ys -> if x<=y then x::y::ys 
      else y::(insert x ys) 

and insertionSort = function 
    | [] -> [] 
    | x::xs -> insert x (insertionSort xs) 

let myLst = [8;3;3;5;-6;0;1;4;-3;2] 
let result = myLst |> insertionSort 

발 결과 : 나는 삽입에 대한 관용적 F # 코드 정렬 매우 같은 추측 INT 목록 = [-6; -삼; 0; 1; 2; 삼; 삼; 4; 5; 8]

아래와 같이 List.foldBack 및 단 하나의 재귀 함수로 구현하려고했지만 올바른 결과를 얻을 수 없었습니다. 누구든지 문제가있는 곳을 파악할 수 있습니까?

let rec anotherInsertionSort lst = 
    List.foldBack(fun x (ys:list<_>) -> 
        if ys.IsEmpty then [x] 
        elif x <= ys.Head then x::ys 
        else ys.Head::x::anotherInsertionSort ys.Tail) lst [] 

Answer 1

가 cfern's code에서 취소가-golfed :

let rec insert i = function 
    | h::t -> min h i::(insert (max h i) t) 
    | _ -> [i] 

let insertionSort l = List.foldBack insert l [] 

Answer 2

내 의견에 말했듯이, 문제는 당신이 당신의 else 지점에 x을 떨어 뜨리고있는 것입니다. 문제를 해결하는 방법은 다음과 같습니다.

let rec anotherInsertionSort lst = 
    List.foldBack(fun x ys -> 
        match ys with 
        | [] -> [x] 
        | y::_ when x <= y -> x::ys 
        | y::ys -> y::(anotherInsertionSort (x::ys))) lst [] 

다니엘의 접근 방식이 더 좋았습니다.