在 F#/OCaml 中实现类快速排序函数的尾递归版本

是否可以实现快速排序算法的尾递归版本（通过延续模式）？如果是的话，将如何实施？

普通（未优化）版本：

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

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)

与洛朗相反，我发现很容易检查cont不要忘记：从直接风格翻译的 CPS 函数具有线性使用延续的属性，在每个分支中，在尾部位置一次且仅一次。很容易检查没有忘记这样的调用。

但事实上，对于大多数快速排序运行（假设您得到了大致对数行为，因为您不走运或者您首先对输入进行了洗牌），调用堆栈不是问题，因为它仅以对数方式增长。更令人担心的是频繁的电话@它的左侧参数是线性的。一种常见的优化技术是将函数定义为“将输入添加到累加器列表”，而不是返回列表：

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)    

现在最后一个技巧是通过将延续转换为数据结构来“去功能化”（假设数据结构的分配比闭包的分配稍微更有效）：

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