## Friday, March 6, 2015

### Heap sort

Given the existence of a priority queue data structure, the heap sort algorithm is trivially implemented by loading the unsorted sequence into a queue then successively pulling of the minimum element from the queue until the queue is exhausted.

There are many ways to implement a priority queue and so we seek an expression for a function for heap sorting that is polymorphic over those choices.

To begin, a module type for priority queues.

(**Priority queues over ordered types*)
module type PRIORITY_QUEUE = sig

(**Output signature of the functor [Make]*)
module type S = sig
exception Empty

type element (*Abstract type of elements of the queue*)
type t (*Abstract type of a queue*)

val empty : t (*The empty queue*)
val is_empty : t -> bool (*Check if queue is empty*)
val insert : t -> element -> t (*Insert item into queue*)
val delete_min : t -> t (*Delete the minimum element*)
val find_min : t -> element (*Return the minimum element*)
val of_list : element list -> t
end

(**Input signature of the functor [Make]*)
module type Ordered_type = sig
type t
val compare : t -> t -> int
end

(**Functor building an implementation of the priority queue structure
given a totally ordered type*)
module Make :
functor (Ord : Ordered_type) -> S with type element = Ord.t
end


An implementation of this signature using "leftist heaps" is described for the interested in this Caltech lab but such details are omitted here.

module Priority_queue : PRIORITY_QUEUE = struct
module type S = sig .. end
module type Ordered_type = sig .. end
module Make (Elt : Ordered_type) : (S with type element = Elt.t) = struct .. end
end


What I really want to show you is this. We start with the following module type abbreviation.

type 'a queue_impl = (module Priority_queue.S with type element = 'a)

Then, the heap_sort function can be written such that it takes a module as a first class value and uses a locally abstract type to connect it with the element type of the list to be sorted.
let heap_sort (type a) (queue : a queue_impl) (l : a list) : a list =
let module Queue =
(val queue : Priority_queue.S with type element = a) in
let rec loop acc h =
if Queue.is_empty h then acc
else
let p = Queue.find_min h in
loop (p :: acc) (Queue.delete_min h) in
List.rev (loop [] (Queue.of_list l))

There we have it. The objective has been achieved : we have written a heap sorting function that is polymorphic in the implementation of the priority queue with which it is implemented.

Usage (testing) proceeds as in this example.

(*Prepare an [Priority_queue.Ordered_type] module to pass as argument
to [Priority_queue.Make]*)
module Int : Priority_queue.Ordered_type with type t = int = struct
type t = int let compare = Pervasives.compare
end

(*Make a priority queue module*)
module Int_prioqueue : (Priority_queue.S with type element = int) = Priority_queue.Make (Int)

(*Make a first class value of the module by packing it*)
let queue = (module Int_prioqueue : Priority_queue.S with type element = int)

(*Now, pass the module to [heap_sort]*)
let sorted = heap_sort queue [-1; -2; 2] (*Produces the list [-2; -1; 2]*)


These ideas can be pushed a little further yielding a simpler syntax for the parametric heapsort algorithm.
(*Type abbreviations*)

type 'a order_impl = (module Priority_queue.Ordered_type with type t = 'a)
type 'a queue_impl = (module Priority_queue.S with type element = 'a)

(*Module factory functions*)

let mk_ord : 'a. unit -> 'a order_impl =
fun (type s) () ->
(module
struct
type t = s
let compare = Pervasives.compare
end : Priority_queue.Ordered_type with type t = s
)

let mk_queue : 'a. unit -> 'a queue_impl =
fun (type s) ord ->
let module Ord =
(val mk_ord () : Priority_queue.Ordered_type with type t = s) in
(module Priority_queue.Make (Ord) :
Priority_queue.S with type element = s)

For example, now we can write
# heap_sort (mk_queue ()) [-3; 1; 5] ;;
- : int list = [-3; 1; 5]