Quick Sort in Shen

Mon, Apr 2, 2012

A Shen type-checked implementation of Quick Sort is even more elegant/terse compared with the CL version posted previously.
Pattern-matching and currying make this possible.

(tc +)
(define filter
  {(A --> boolean) --> (list A) --> (list A)}
  _  []      -> []
  T? [A | B] -> (append [A] (filter T? B)) where (T? A)
  T? [_ | B] -> (filter T? B))
(define quick-sort-generic
  {(list A) --> (A --> A --> boolean) --> (A --> A --> boolean) --> (list A)}
  [] _ _ -> []
  [A | B] L? R? -> (append (quick-sort-generic (filter (R? A) B) L? R?)
			   [A]
			   (quick-sort-generic (filter (L? A) B) L? R?)))
\* descending with duplicates *\
* (quick-sort-generic [3 1 2 7 9 6 6 3 0] >= <)
* [9 7 6 6 3 3 2 1 0] : (list number)

The complete code can be found here. Based on this numeric version.