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.

### Like this:

Like Loading...