Quicksort in shen

I've been playing with shen language last time. It leaves very positive impressions. Being a lisp it introduces pattern matching and powerful type system to the language.

Just a simple quickstort algorithm for starters:

(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 q-sort
  {(list number) --> (list number)}
  [] -> []
  [A | B] -> (append (q-sort (filter (> A) [A|B]))
                     [A]
                     (q-sort (filter (< A) [A|B]))))

Yeah you're right. That's just a naive quick-sort. Generate left and right partitions of list by the first element and then recursively apply algorithm to the left partition and to the right one.

The standard library is not yet ready and that's the reason for filter function which doesn't belong to the core language.

Let's see what shen features are present in this program.

Pattern matching   

T?  [A | B]  -> (append [A] (filter T? B)) where (T? A)

This rule says: return element A glued with the resulte filter function applied to the tail of list called B, if (T? A) is satisfied.

Function signatures 
   

{(A --> boolean) --> (list A)--> (list A)}

This function signature says that function takes two arguments:

1. The function from the type A to boolean (the predicate in other words).
2. A list with elements of type A.

And returns a list with elements of type A. In this particular example A is the number type.

The filter function is used like this:

 (filter (> 5) [5 3 5 91 42 1 2])
 [3 1 2] : (list number)

It generates a list of all elements less than 5. 

Notice the (> 5). That's the notation for writing partial application functions.
It is equavalent to the following lambda function in lisp:
(lambda(x) (> 5 x))

After you load the program to the evaluator (I use emacs and shen-mode for that) you can run it like this:

(16+) (q-sort [5 3 5 91 42 1 2])
[1 2 3 5 42 91] : (list number)