Friday, 25 September 2009

Tail Recursive QuickSort using Continuation Passing Style

//val qsort: 'a list -> 'a list
let rec qsort = function
| [] -> []
| x::xs' -> let (l, r) = List.partition ((>) x) xs'
List.concat [(qsort l);[x];(qsort r)]

//val qsortCPS: 'a list -> 'a list
let qsortCPS xs =
let rec loop xs cont =
match xs with
| [] -> cont []
| x::xs' -> let (l, r) = List.partition ((>) x) xs'
loop l (fun lacc ->
loop r (fun racc -> cont (lacc @ x :: racc)))
loop xs (fun x -> x)

2 comments:

Ben said...
This comment has been removed by the author.
Anonymous said...

Can you translate,please, it into C# LINQ?