1つの再帰関数と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。 -3; 0; 1; 2; 3; 3; 4; 5; 8]

私はList.foldBackで実装しようとしていましたが、以下のように再帰関数が1つしかなく、正しい結果を得られませんでしたか？問題がどこにあるのか誰でも分かりますか？

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を落としていることです。それを修正する方法が1つあります：

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 [] 

ダニエルのアプローチが好きです。