SML# - Resources/ProgrammingExamples/Qsort Diff

  • Added parts are displayed like this.
  • Deleted parts are displayed like this.

C library function '''QSORT(3)''' is also polymorphic similar to '''FREAD(3)'''.
It has the following functionality.
  void qsort(void *base, size_t nmemb, size_t size,
             int(*compar)(const void *, const void *));
where
voild *base : the array to be sorted.
size_t nmemb : the number of array elements
size_t size : the size of each element data
int(*compar)(const void *, const void *) : a compare function that takes two data pointers.
As a statically typed polymoprhic language, ML should be able to
represent this as the following polymorphic function.
qsort : 'a array * ('a ptr * 'a ptr -> int) -> unit
In SML#, this is easily done by using SML#'s mechnisms to use
[[C functions with callbacks|Resorces/ProgrammingExamples/CallBack]]
and
[[polymorphic C functions|Resorces/ProgrammingExamples/PolyC]].
  val libc = DynamicLink.dlopen "/lib/libc.so.6"
  val c_qsort = DynamicLink.dlsym (libc, "qsort")
  fun qsort (a, f) =
      _ffiapply c_qsort (a : 'a array,
                         Array.length a : int,
                         _sizeof('a),
                         f : ('a ptr, 'a ptr) -> int) : unit
SML# evaluates this code to produce the following binding.
val qsort = fn : ['a .'a Array.array * ('a ptr * 'a ptr  -> int)  -> unit]
To use this function, one need to write a comparison function that
takes C pointers and return an integer.
For this purpose, SML# provide the following overloaded operators.
!! : ['a::{int, real, word, byte, char}.'a ptr -> 'a]
Using this, sort can be used as follows.
  fun compareReal (p1, p2) =
      let
        val n1 = !!p1 : real
        val n2 = !!p2
      in
        if n1 > n2 then 1 else if n1 < n2 then ~1 else 0
      end
  val _ = qsort (aRealArray, compareReal)