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

Я рассматриваю реализации некоторых базовых структур данных и алгоритмы, работающие с ними. Я предполагаю, что идиоматический код 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 []

list f# insertion-sort
person 1B4T    schedule 01.03.2012    source источник
comment
В вашей ветке else x не используется...   -  person kvb    schedule 01.03.2012
comment
@kvb, упс... понял. Большое спасибо! Я бы заметил это до публикации.   -  person 1B4T    schedule 01.03.2012
comment
@cfj FWIW, я всегда стараюсь протестировать любой пример кода, прежде чем публиковать его, чтобы убедиться, что он демонстрирует проблему, о которой я спрашиваю, и что я ничего не напутал. Экономит время. :-)   -  person Onorio Catenacci    schedule 01.03.2012

Ответы (2)


arrow_upward
3
arrow_downward

Un-golfed из кода cfern:

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

let insertionSort l = List.foldBack insert l []
person Daniel    schedule 01.03.2012

arrow_upward
2
arrow_downward

Как я сказал в своем комментарии, проблема в том, что вы отбрасываете 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 []

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

person kvb    schedule 01.03.2012
comment
Соглашаться. Подход Даниэля более элегантный. - person 1B4T; 01.03.2012