Реализация вставки Sort с одной рекурсивной функцией и функцией foldBack - PullRequest
Новая
       18

Реализация вставки Sort с одной рекурсивной функцией и функцией foldBack

2 голосов
/ 01 марта 2012

Я рассматриваю реализации некоторых базовых структур данных и алгоритмов, работающих на них.Я предполагаю, что идиоматический код F # для сортировки вставок очень похож на: 

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

val результат: int list = [-6;-3;0;1;2;3;3;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 []

Ответы [ 2 ]

3 голосов
/ 01 марта 2012

Без игры в гольф от Код Cfern : 

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

let insertionSort l = List.foldBack insert l []
2 голосов
/ 01 марта 2012

Как я уже сказал в своем комментарии, проблема в том, что вы добавляете x в свою ветку else.Вот один из способов исправить это: 

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

Сказав это, мне больше нравится подход Дэниела.

...