Implémentation du tri par insertion avec une fonction récursive et une fonction foldBack

Question

Je suis en train d'examiner les implémentations pour certaines structures de données de base et les algorithmes qui les utilisent. Je suppose que le code idiomatiques F # pour insertion Trier est très semblable:

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 

résultat val: int list = [-6; -3; 0; 1; 2; 3; 3; 4; 5; 8]

Alors que j'essayais de l'implémenter avec List.foldBack et une seule fonction récursive, comme ci-dessous, et ne pouvait pas me donner le résultat correct? Tout le monde peut comprendre où se situe le problème?

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

Un-golfed de cfern's code:

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

Comme je l'ai dit dans mon commentaire, le problème est que vous êtes tomber x dans votre branche else. Voici une façon de le réparer:

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

Cela dit, j'aime mieux l'approche de Daniel.