functional programming - Implementing a tail recursive version of quicksort-like function in F#/OCaML -

is possible implement tail recursive version of quick sort algorithm (via continuation pattern)? , if is, how 1 implement it?

normal (not optimized) version:

let rec quicksort list =  match list  | [] -> []  | element::[] -> [element]  | pivot::rest -> let ``elements smaller pivot``, ``elements larger or equal pivot``=                      rest |> list.partition(fun element -> element < pivot)                   quicksort ``elements smaller pivot`` @ [pivot] @ quicksort ``elements larger or equal pivot`` 

direct style:

let rec quicksort list =     match list     | [] -> []     | [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 similar laurent's version, except indented bit weirdly make apparent calls continuations kind of binding:

let rec quicksort list cont =     match list     | [] -> 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 laurent, find easy check cont not forgotten: cps functions translated direct style have property continuation used linearily, once , once in each branch, in tail position. easy check no such call forgotten.

but in fact, runs of quicksort (supposing logarithmic behavior because you're not unlucky or shuffled input first), call stack not issue, grows logarithmically. more worrying frequent calls @ wich linear in left parameter. common optimization technique define functions not returning list "adding input accumulator list":

let rec quicksort list accu =     match list     | [] -> 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 can turned cps again:

let rec quicksort list accu cont =     match list     | [] -> 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 last trick "defunctionalize" continuations turning them data structure (supposing allocation of data structures more efficient allocation of closure):

type 'a cont =   | left of 'a list * 'a * 'a cont   | return let rec quicksort list accu cont =     match list     | [] -> 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)) , 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, chose function .. fun style eval_cont make apparent pieces of code cps version, following version better optimized arity-raising:

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