在F＃/ OCaML中實現尾部遞歸版本的類快速排序功能

Question

是否可以實現快速排序算法的尾部遞歸版本（通過延續模式）？如果是這樣，那麼如何實現呢？

標準（未優化）版本：

let rec quicksort list = 
match list with 
| [] -> [] 
| element::[] -> [element] 
| pivot::rest -> let ``elements smaller than pivot``, ``elements larger or equal to pivot``= 
        rest |> List.partition(fun element -> element < pivot) 
        quicksort ``elements smaller than pivot`` @ [pivot] @ quicksort ``elements larger or equal to pivot`` 

Answer 1

直接的風格：

let rec quicksort list = 
    match list with 
    | [] -> [] 
    | [element] -> [element] 
    | pivot::rest -> 
     let left, right = List.partition (fun element -> element < pivot) rest in 
     let sorted_left = quicksort left in 
     let sorted_right = quicksort right in 
     sorted_left @ [pivot] @ sorted_right 

我的第一個，天真的翻譯是非常相似的Laurent的版本，除了縮進有點古怪，使與延續呼籲顯然是真正的一種結合：

let rec quicksort list cont = 
    match list with 
    | [] -> cont [] 
    | element::[] -> cont [element] 
    | pivot::rest -> 
     let left, right = List.partition (fun element -> element < pivot) rest in 
     quicksort left (fun sorted_left -> 
     quicksort right (fun sorted_right -> 
     cont (sorted_left @ [pivot] @ sorted_right))) 
let qsort li = quicksort li (fun x -> x) 

與Laurent相反，我發現很容易檢查到cont沒有被遺忘：從直接類型轉換的CPS函數具有連續線性使用的性質，在每個分支中只有一次，在尾部位置。很容易檢查，沒有這樣的電話被遺忘。但事實上，對於大多數quicksort運行（假設您因爲您不是倒黴或您首先對輸入進行了混洗而獲得粗略的對數行爲），調用堆棧並不是問題，因爲它只是以對數形式增長。更令人擔憂的是經常調用@，它的左邊參數是線性的。一個常見的優化技術是定義函數不爲返回清單，但作爲「添加輸入到累加器列表」：

let rec quicksort list accu = 
    match list with 
    | [] -> accu 
    | element::[] -> element::accu 
    | pivot::rest -> 
     let left, right = List.partition (fun element -> element < pivot) rest in 
     let sorted_right = quicksort right accu in 
     quicksort left (pivot :: sorted_right) 
let qsort li = quicksort li [] 

當然，這可以再次變成CPS：

let rec quicksort list accu cont = 
    match list with 
    | [] -> cont accu 
    | element::[] -> cont (element::accu) 
    | pivot::rest -> 
     let left, right = List.partition (fun element -> element < pivot) rest in 
     quicksort right accu (fun sorted_right -> 
     quicksort left (pivot :: sorted_right) cont) 
let qsort li = quicksort li [] (fun x -> x)  

現在最後關鍵是要通過把它們變成數據結構「defunctionalize」的延續（假設數據結構的分配略小於封閉的分配更有效）：

type 'a cont = 
    | Left of 'a list * 'a * 'a cont 
    | Return 
let rec quicksort list accu cont = 
    match list with 
    | [] -> eval_cont cont accu 
    | element::[] -> eval_cont cont (element::accu) 
    | pivot::rest -> 
     let left, right = List.partition (fun element -> element < pivot) rest in 
     quicksort right accu (Left (left, pivot, cont)) 
and eval_cont = function 
    | Left (left, pivot, cont) -> 
    (fun sorted_right -> quicksort left (pivot :: sorted_right) cont) 
    | Return -> (fun x -> x) 
let qsort li = quicksort li [] Return 

最後，我選擇了function .. fun風格eval_cont，使之明顯，這些只是從CPS版本的代碼段，但以下版本可能是更好的元數籌措優化：

and eval_cont cont accu = match cont with 
    | Left (left, pivot, cont) -> 
    quicksort left (pivot :: accu) cont 
    | Return -> accu 

Answer 2

快速嘗試，seeems工作：

let rec quicksort list cont = 
    match list with 
    | [] -> cont [] 
    | element::[] -> cont [element] 
    | pivot::rest -> 
     let ``elements smaller than pivot``, ``elements larger or equal to pivot`` = 
      rest |> List.partition (fun element -> element < pivot) 
     quicksort ``elements smaller than pivot`` 
      (fun x -> quicksort ``elements larger or equal to pivot`` (fun y -> cont (x @ [pivot] @ y))) 

> quicksort [2; 6; 3; 8; 5; 1; 9; 4] id;; 
val it : int list = [1; 2; 3; 4; 5; 6; 8; 9] 

編輯：

當然，這個代碼是非常低效的。我希望沒有人會用真實的代碼來使用它。 代碼不難寫，但延續可能難以閱讀，並且容易出錯（很容易忘記對cont的調用）。如果你想玩更多，你可以寫一個延續monad（Brian寫道a blog post about it）。

Answer 3

延續單子（stolen from here ）也可以使用（通常使代碼更具可讀性）：

type ContinuationMonad() = 
    // ma -> (a -> mb) -> mb 
    member this.Bind (m, f) = fun c -> m (fun a -> f a c) 
    // a -> ma 
    member this.Return x = fun k -> k x 
    // ma -> ma 
    member this.ReturnFrom m = m 
let cont = ContinuationMonad() 

// Monadic definition of QuickSort 
// it's shame F# doesn't allow us to use generic monad code 
// (we need to use 'cont' monad here) 
// otherwise we could run the same code as Identity monad, for instance 
// producing direct (non-cont) behavior 
let rec qsm = function 
    |[] -> cont.Return [] 
    |x::xs -> cont { 
     let l,r = List.partition ((>=)x) xs 
     let! ls = qsm l 
     let! rs = qsm r 
     return (ls @ x :: rs) } 

// Here we run our cont with id 
let qs xs = qsm xs id  

printf "%A" (qs [2;6;3;8;5;1;9;4])