在F＃/ OCaML中实现一个类似quicksort函数的尾递归版本 [英] Implementing a tail recursive version of quicksort-like function in F#/OCaML

问题描述

是否可以实现快速排序算法的尾递归版本（通过延续模式）？如果是这样，一个人会怎么实现它？

正常（未优化）版本：

 让rec quicksort list = 
匹配列表中的
 | []  - > [] 
 | element :: []  - > [元素] 
 | pivot :: rest  - >让``元素小于pivot``，``元素大于或等于pivot`` = 
 rest |> 
 quicksort``元素小于pivot`` @ [pivot] @ quicksort``元素大于或等于pivot`` 
  
解决方案
直接样式： 
 
 
 使用
 |让rec quicksort list = 
匹配列表[]  - > [] 
 | [元素]  - > [元素] 
 | pivot :: rest  - > 
让left，right = List.partition（fun元素 - >元素<数据透视表）休息在
 let sorted_left = quicksort留在
 let sorted_right = quicksort right在
 sorted_left @第一次，天真的翻译与洛朗的版本非常相似，只是缩进了一个有点奇怪地表明，连续调用实际上是一种绑定： 
 
 
  let rec quicksort list cont = 
与
 |匹配的列表[]  - > cont [] 
 | element :: []  - > cont [element] 
 | pivot :: rest  - > 
 let left，right = List.partition（fun元素 - >元素< pivot）休息在
 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列表accu = 
与
 |匹配的列表[]  - > accu 
 | element :: []  - > element :: accu 
 | pivot :: rest  - > 
让left，right = List.partition（fun元素 - >元素<数据透视）在
中休息let sorted_right = quicksort right accu in 
 quicksort left（pivot :: sorted_right）
 let qsort li = quicksort li [] 
  
当然，这可以再次变成CPS：
 让rec quicksort list accu cont = 
与
匹配的列表| []  - >续准
 | element :: []  - > cont（element :: accu）
 | pivot :: rest  - > 
 let left，right = List.partition（fun元素 - >元素< pivot）休息在
 quicksort right accu（fun sorted_right  - > 
 quicksort left（pivot :: sorted_right）续）
 let qsort li = quicksort li []（fun x  - > x）
  
现在最后一个技巧是通过将它们转换为数据结构来去功能化连续性（假设数据结构的分配比分配闭包稍微更有效）： 
 
 
 键入'a cont = 
 | '列表*'a *'a cont 
 |的左边返回
让rec快速排序列表accu cont = 
与
匹配的列表[]  - > eval_cont续accu 
 | element :: []  - > eval_cont cont（element :: accu）
 | pivot :: rest  - > 
 let left，right = List.partition（fun元素 - >元素< pivot）休息在
 quicksort right accu（Left（left，pivot，cont））
和eval_cont = function 
 |左（左，枢轴，续） - > 
（fun sorted_right  - > quicksort left（pivot :: sorted_right）cont）
 |返回 - > （fun x  - > x）
 let qsort li = quicksort li []返回
  
最后，我为 eval_cont 选择了函数。fun  style，以显而易见，这些只是从CPS版本，但是下面的版本可能会更好地通过arity-raising优化：
 和eval_cont cont accu =与cont续约
 |左（左，枢轴，续） - > 
 quicksort left（pivot :: accu）cont 
 |返回 - > accu 
  
 
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?


Normal (not optimized) version:
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``

解决方案
Direct style:
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
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)
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 []
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
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中实现一个类似quicksort函数的尾递归版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！