🚀 go-pugleaf

anw@maths.nott.ac.uk (Dr A. N. Walker) writes:
| Re-implementing "sort" as a Quicksort or similar is left as an exercise!
| Apart from the actual sorting technique, this seems to me to be the same
| as C's "qsort" library routine, but type-safe in Dan's sense.  Any
| advances in the last 17 years?

This version of quicksort comes with the SML/NJ documentation:

% sml
- fun quick(le:'a*'a->bool) =
=   let fun sort [] = []
=	  | sort [x] = [x]
=	  | sort (a::rest) = (* the head "a" is the pivot *)
=	      let fun split(left,right,[]) = sort left @ (a::sort right)
=		    | split(left,right,x::l) =
=			if le(x,a) then split(x::left,right,l)
=				   else split(left,x::right,l)
=	      in split([],[],rest)
=	      end
=   in sort
= end;
val quick = fn : ('a * 'a -> bool) -> 'a list -> 'a list

- quick (op<) ["foo", "bar", "biff"];
val it = ["bar","biff","foo"] : string list
- quick (op>) [1,2,3,9,8,7];
val it = [9,8,7,3,2,1] : int list

The 17 year advance is type inference, I guess.