# 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.