Standard sorting functions in SML?

There is no sorting functionality defined in the SML Basis Library, but most implementations extend the basis library and add extra functionality.

As such MosML has both an ArraySort and a Listsort module, and SML/NJ has a LIST_SORT signature with a ListMergeSort implementation. It also features some other sorting features on arrays as MosML. See the toc of the SML/NJ Library Manual, for a full list.

As Jesper Reenberg points out, Standard ML compilers have each their own (non-standard, ironically) sorting libraries. Since the documentation for these lacks examples, here is how to sort a list of strings in ascending order using the various modules:

In SML/NJ and MLton, using the ListMergeSort.sort function:

- fun sortStrings ss = ListMergeSort.sort (fn (s : string, t) => s > t) ss;
[autoloading]
[library $SMLNJ-LIB/Util/smlnj-lib.cm is stable]
[autoloading done]
val sortStrings = fn : string list -> string list
- sortStrings ["World","Hello"];
val it = ["Hello","World"] : string list

The quirk with this library function is that it takes a "greater than" boolean predicate. Since Standard ML's > operator is overloaded, but defaults to int, I have to somehow explicitly annotate that I'm comparing strings.

In Moscow ML, using the Listsort.sort function:
```
- load "Listsort";
> val it = () : unit
- fun sortStrings ss = Listsort.sort String.compare ss;
> val sortStrings = fn : string list -> string list
- sortStrings ["World", "Hello"];
> val it = ["Hello", "World"] : string list
```
The quirk with this library is that Moscow ML's interactive REPL does not auto-load Listsort. Typing load "Listsort"; is only necessary in the interactive REPL; when compiling programs, load is not used.
In Poly/ML, there is no library for sorting, so you have to define your own sorting function.

If neither of these sorting functions are sufficient, here is a number of other sorting functions written in Standard ML:

True QuickSort in Standard ML compares a naive QuickSort (that isn't really a QuickSort) with an implementation of Hoare's algorithm by John Coleman.

Rosetta Code's MergeSort in Standard ML:

fun merge cmp ([], ys) = ys
  | merge cmp (xs, []) = xs
  | merge cmp (xs as x::xs', ys as y::ys') =
      case cmp (x, y) of
           GREATER => y :: merge cmp (xs, ys')
         | _       => x :: merge cmp (xs', ys)

fun sort cmp [] = []
  | sort cmp [x] = [x]
  | sort cmp xs =
    let
      val ys = List.take (xs, length xs div 2)
      val zs = List.drop (xs, length xs div 2)
    in
      merge cmp (sort cmp ys, sort cmp zs)
    end

Here is a standard quicksort

fun qsort(func) =
    let fun sort [] = []
          | sort (lhd :: ltl) =
                sort (List.filter (fn x => func (x, lhd)) ltl)
              @ [lhd]
              @ sort (List.filter (fn x => not (func(x, lhd)) ltl)
    in sort
    end

Just throw in some comparator (function that takes two elements with same type and return boolean) and it will return a sort function for you If you got anymore question don't hesitate to ask. :)

Standard sorting functions in SML?

Tags:

Sml

Related

Recent Posts