Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!psuvax1!news
From: schwartz@groucho.cs.psu.edu (Scott Schwartz)
Newsgroups: comp.lang.misc
Subject: Re: Optional static typing limits
Message-ID: <b58G8yru1@cs.psu.edu>
Date: 21 Apr 91 04:07:12 GMT
References: <LIBERTE.91Apr16164831@babbage.ncsa.uiuc.edu>
	<8493:Apr1719:30:0791@kramden.acf.nyu.edu>
	<1991Apr19.144812.5958@maths.nott.ac.uk>
Sender: news@cs.psu.edu (Usenet)
Organization: PSU CS
Lines: 30
In-Reply-To: anw@maths.nott.ac.uk's message of 19 Apr 91 14:48:12 GMT
Nntp-Posting-Host: groucho.cs.psu.edu


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.