Skip to content

Instantly share code, notes, and snippets.

@eduardoleon
Last active August 29, 2015 09:11
Show Gist options
  • Save eduardoleon/e4bb776adf514a031cb9 to your computer and use it in GitHub Desktop.
Save eduardoleon/e4bb776adf514a031cb9 to your computer and use it in GitHub Desktop.
datatype 'a tree
= Leaf
| Node of 'a tree * 'a * 'a tree
fun build (op <) =
let
fun loop nil = Leaf
| loop (x :: xs) =
let
val (xs, ys) = List.partition (fn y => y < x) xs
in
Node (loop xs, x, loop ys)
end
in
loop
end
fun flatten t =
let
fun loop Leaf = (fn xs => xs)
| loop (Node (l,x,r)) = loop l o (fn xs => x :: xs) o loop r
in
loop t nil
end
fun qsort (op <) = flatten o build (op <)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment