Credit: Nathaniel Gray, Raymond Hettinger, Christophe Delord, Jeremy Zucker
You need to show that Python's support for the functional programming paradigm is better than it might seem at first sight.
Functional programming languages, of which Haskell is a great example, are splendid animals, but Python can hold its own in such company:
def qsort(L): if len(L) <= 1: return L return qsort([lt for lt in L[1:] if lt < L]) + L[0:1] + \ qsort([ge for ge in L[1:] if ge >= L])
In my humble opinion, this code is almost as pretty as the Haskell version from http://www.haskell.org:
qsort [ ] = [ ] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x where elts_lt_x = [y | y <- xs, y < x] elts_greq_x = [y | y <- xs, y >= x]
Here's a test function for the Python version:
def qs_test(length): import random joe = range(length) random.shuffle(joe) qsJoe = qsort(joe) for i in range(len(qsJoe)): assert qsJoe[i] == i, 'qsort is broken at %d!' %i
This rather naive implementation of quicksort
illustrates the expressive power of list comprehensions. Do not use
this approach in real code! Python lists have an in-place
sort method that is much faster and should
always be preferred; in Python 2.4, the new built-in function
sorted accepts any finite sequence and returns a new sorted list with the sequence's items. The only proper use of this recipe is for impressing friends, particularly ones who (quite understandably) are enthusiastic ...