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_sortfunction 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]*)
Addendum :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]