I don't realize why q's type is Ord t => [t] -> [a] and not Ord a => [a] -> [a]
q [] = []
q (x:xs) = q us ++ q ws
where us = filter (<=x) xs
ws = filter (>=x) xs
Under which circumstances the input type could differ from the output?
Thanks,
Sebastián.
Under any circumstances, which here implies: the function is never useful.
This is actually a nice example of "theorems for free". Obviously, the type Ord t => [t] -> [a] doesn't make much sense, because the only list you can produce of a type [a] (you know nothing about a!) is the empty list. So this proves that q can do only two things:
[]⟂)And indeed the former is what happens: in each recursion step, you pop off an element from the input list, but you never actually include any of these elements in the result. So you always end up with [].
If you'd correctly implemented the quicksort, you'd of course bring x back between the two sublists, i.e.
q (x:xs) = q us ++ [x] ++ q ws