Quick Sort in Shen

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>