在 F#/OCaml 中实现类似快速排序的函数的尾递归版本 [英] Implementing a tail recursive version of quicksort-like function in F#/OCaml

问题描述

是否可以实现快速排序算法的尾递归版本(通过延续模式)?如果是，人们将如何实施它?

Is it possible to implement a tail recursive version of the quick sort algorithm (via the continuation pattern)? And if it is, how would one implement it?

普通(未优化)版本:

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``

推荐答案

直接风格:

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 的版本非常相似，只是缩进有点奇怪，以表明带有延续的调用实际上是一种绑定:

My first, naive translation is very similar to Laurent's version, except indented a bit weirdly to make apparent that calls with continuations are really a kind of binding:

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函数具有线性使用延续的特性，在每个分支中一次且仅一次，在尾部位置.很容易检查是否没有忘记此类调用.

Contrarily to Laurent, I find it easy to check that cont is not forgotten: CPS functions translated from direct style have the property that the continuation is used linearily, once and only once in each branch, in tail position. It is easy to check that no such call was forgotten.

但事实上，对于大多数快速排序的运行(假设你得到一个大致对数的行为，因为你不是运气不好，或者你先打乱了输入)，调用堆栈不是问题，因为它只会对数增长.更令人担忧的是对 @ 的频繁调用，它的左参数是线性的.一种常见的优化技术是将函数定义为将输入添加到累加器列表"而不是返回列表:

But in fact, for most runs of quicksort (supposing you get a roughly logarithmic behavior because you're not unlucky or you shuffled the input first), the call stack is not an issue, as it only grows logarithmically. Much more worrying are the frequent calls to @ wich is linear in its left parameter. A common optimization technique is to define functions not as returning a list but as "adding input to an accumulator list":

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:

Of course this can be turned into CPS again:

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)    

现在最后一个技巧是通过将延续转换为数据结构来去功能化"它们(假设数据结构的分配比闭包的分配稍微更有效):

Now a last trick is to "defunctionalize" the continuations by turning them into data structure (supposing the allocation of data structures is slightly more efficient than the allocation of a closure):

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

最后，我为 eval_cont 选择了 function .. fun 样式，以表明那些只是来自 CPS 版本的代码片段，但以下版本是可能通过 arity-rising 得到更好的优化:

Finally, I chose the function .. fun style for eval_cont to make it apparent that those were just pieces of code from the CPS version, but the following version is probably better optimized by arity-raising:

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

这篇关于在 F#/OCaml 中实现类似快速排序的函数的尾递归版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！