在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])