是否有可能实现快速排序算法的尾部递归版本(通过延续模式)?如果是,又该如何实现呢?
正常(未优化)版本:
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)
与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
最后,我为eval_cont
选择了function .. fun
风格,以表明这些只是来自CPS版本的代码片段,但下面的版本可能通过提高字体进行了更好的优化:
and eval_cont cont accu = match cont with
| Left (left, pivot, cont) ->
quicksort left (pivot :: accu) cont
| Return -> accu
快速尝试,似乎有效:
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写了一篇关于它的博客文章)。
Continuation monad(从这里偷来的)也可以使用(通常使代码更具可读性):
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])