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

- Yet Another Geek

---

第二种情况并非必需，因为第三种情况会对其进行正确处理。我不会认为通过使用continuations使快速排序成为尾递归是一种“优化”。你必须意识到，除了在堆栈中分配的内容外，所有其他内容都将放入堆中。 - Pascal Cuoq

你有的不是一个快速排序算法 —— 必须随机选择轴点。你现在的实现会对已排序或近似已排序的输入表现出最坏 O(n^2) 的行为。可以使用以下策略获得更快的排序速度：1）使用归并排序；2）将列表转换为数组进行排序，然后再转换回列表。最后一点，list1 @ [x] @ list2 的速度较慢，请改用 list1 @ x::list2。 - Juliet

@Juliet：这个算法不是真正的快速排序，因为它没有使用原地分区来减少IO，因此它非常慢。 - J D

@Jon 我认为List.partition被优化了，因为它是标准库的一部分。当然，通常做法是将列表转换为数组并进行原地编辑，但这似乎不是非常“函数式”的方式。另外，我使用它不是为了速度，而是为了学习更多关于CPS的知识。 - Yet Another Geek

@Geek：快速排序算法是一种本质上不纯的算法，因为它基于原地分区以最小化IO，所以创建一个类似但牺牲效率的纯算法并仍然称其为“快速排序”是没有意义的。尽管可以使用它来了解CPS，但我要警告的是将其称为“快速排序”是具有误导性的。 - J D

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的版本非常相似，只是排版有些不规则，以突出表明使用continuations的调用实际上是一种绑定：

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函数具有在每个分支中仅一次并且仅在尾部位置线性使用续体的属性。可以轻松检查没有忘记这样的调用。

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

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

- gasche

---

为什么分配数据结构比分配闭包更高效？它应该几乎相同，不是吗？ - Laurent

我已经尝试了你的最新函数，它比“朴素翻译”稍微快一点，但并没有太大的差别。两个版本仍然是极慢的排序函数（就像原始版本一样）。不管怎样，这仍然是一个有趣的练习。 - Laurent

@Laurent，我更感兴趣的是直接使用累加器的函数与最简单的函数之间的比较。 - gasche

@Laurent，雷诺兹去函数化是将高阶函数式语言编译成不需要实现闭包所需机制的代码的最后一步。这实际上使得编译像Scheme这样的具有一级延续的语言到C或汇编语言变得容易。 - user593999

Answer 2

快速尝试，似乎有效:

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）。如果你想进一步尝试，可以编写一个续延单子（Brian写了一篇关于它的博客文章）。

- Laurent

Answer 3

延续单子（从这里借来）也可以使用（通常可以使代码更易读）：

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

- Ed'ka

---

我知道 (>=) 运算符来自 Haskell，但它是做什么的？ - Yet Another Geek

这是普通的 F# "大于或等于" 算术运算符（与 Haskell 的 (>>=) 运算符无关，该运算符在此通过 this.Bind 方法表示）。 - Ed'ka

啊，也许我应该更注重函数调用的语义而不是语法。 - Yet Another Geek