4.5. Generalising Comparison-Based Sorting¶
- File:
GeneralisedSorting.ml
So far we have seen a number of sorting algorithms that were useful on arrays of particular shape, such as filled with just integers, or pairs having integers as their first components. However, the only operation we required of a data inhabiting the array to provide is the ability to compare its elements with each other. Such an ability has been provided by means of comparing integers, but the very same algorithms can be used, e.g., for sorting arrays of lists (ordered via length) or strings (ordered lexicographically), or even arrays of arrays.
Let us generalise the latest introduced sorting algorithm, namely, Quicksort via two different mechanisms OCaml provides.
4.5.1. Comparator as a parameter¶
The following implementation of generic_quick_sort
takes a named parameter comp
(hence the syntax with ~
). It serves as a comparator — a function that takes an element of an array and returns an integer. The contract the implementation follows is that if comp x y
returns a negative integer, it is interpreted as x < y
, a positive integer means x > y
and zero means x = y
:
let generic_quick_sort arr ~comp =
let partition arr lo hi =
if hi <= lo then lo
else
let pivot = arr.(hi - 1) in
let i = ref lo in
for j = lo to hi - 2 do
if comp arr.(j) pivot <= 0
then
(swap arr !i j;
i := !i + 1)
done;
swap arr !i (hi - 1);
!i
in
let rec sort arr lo hi =
if hi - lo <= 1 then ()
else
let mid = partition arr lo hi in
sort arr lo mid;
sort arr mid hi
in
sort arr 0 (Array.length arr)
Notice that nothing else is known about the elements of an array, only the fact that they can be passed to comp
getting an integer in return.
We can now instantiate generic_quick_sort
with different comparators, sorting arrays of arbitrary elements, which we know how to compare, in an ascending or a descending order. For instance, the following comparator restores the familiar logic of sorting an array of integers:
let int_order_asc =
fun x y -> if
x < y then -1
else if x = y then 0
else 1
We can test it with success:
let%test _ =
random_sorting_test_int
(generic_quick_sort ~comp:int_order_asc) 500
4.5.2. A functor for sorting¶
Another way to define generic sorting is by using OCaml’s mechanisms of modules as a way to bundle several dependent definitions together, and functors — modules that take other modules as parameters.
The following code defines a module signature — an abstract interface that postulates that the modules satisfying this signature will feature a concrete type t
and a function comp
of type t -> t -> int
:
module type Comparable = sig
type t
val comp : t -> t -> int
end
Intuitively, you can think of the module signature Comparable
as of a “promise” to give a data type t
, whose elements we will know how to compare via comp
that comes “bundled” with it.
Without even having specific instances of this signature, we can go ahead and describe a higher-order module (functor) Sorting
, which, if given an instance Comp
of a signature Comparable
, will provide a function to sort arrays, whose elements are of type Comp.t
:
module Sorting (Comp: Comparable) = struct
include Comp
let sort arr =
let partition arr lo hi =
if hi <= lo then lo
else
let pivot = arr.(hi - 1) in
let i = ref lo in
for j = lo to hi - 2 do
if comp arr.(j) pivot <= 0
then
(swap arr !i j;
i := !i + 1)
done;
swap arr !i (hi - 1);
!i
in
let rec sort_aux arr lo hi =
if hi - lo <= 1 then ()
else
let mid = partition arr lo hi in
sort_aux arr lo mid;
sort_aux arr mid hi
in
sort_aux arr 0 (Array.length arr)
end
As you can notice, Sorting
imports all definitions from Comp
, i.e., its concrete t
and implementation of comp
to be provided, and uses the latter in its implementation of Quicksort.
Now, in order to obtain procedures for sorting particular elements (e.g., integers), we need to provide the corresponding concrete modules, whose “shape” satisfies the constraints imposed by the signature Comparable
:
module IntAsc = struct
type t = int
let comp = int_order_asc
end
Notice that both modules above have their members named in the same
way as per the signature Comparable
, and the type of comp
is
both corresponds to the one in Comparable
, module the concrete
nature of t
, which in IntAsc
is taken to be int
.
We can now create an instance of the sorting module by providing a comparator module to our sorting functor:
module AscIntSorting = Sorting(IntAsc)
Finally, we can export the corresponding sorting function:
let int_sort_asc = AscIntSorting.sort
and test it:
let%test _ = random_sorting_test_int int_sort_asc 500
At the beginning, the machinery of modules and functors might seem much more heavy-weight that that of simply passing comparators. However, it will pay off to be familiar with it, once we will start working with abstract data types that provide a rich vocabulary of useful procedures to work with certain data, should they be given a small corresponding module instance with basic operations on that data.
In this sense, signatures, modules and functors in OCaml are similar to interfaces and classes in languages such as Java and C#, but provide somewhat more succinct way to parameterise libraries by client-defined primitive operations. That said, OCaml features an object model as well (similar to Java), which we won’t be using very actively in this class.