Python Ugliness

UPDATED: The code I posted initially had a slight bug in it, this has since been fixed. There is another bug in this code, which is addressed at the end of the post.

This is part two in a continuing (maybe) series about writing Perverse sorting algorithm implementations in Python — part one can be found via this link

After discovering the three-line Quicksort, and showing it to a friend of mine, I was challenged to come up with an implementation of Merge Sort in a similar length of time. I was fairly certain that it couldn’t be done, until I discovered some really nasty features of Python that probably aren’t meant to be exploited in the way that I’ve done so. And so here’s the result (reformatted for line-length issues), followed by a commentary on why this is as damn-awful as I say it is:

 def msort2( L ): a,b = ((len( L ) > 1 and (msort2(L[:len( L )/2]), msort2(L[len( L )/2:]))) or (list( L ), [])) return ([(lambda m,n: ((len( n ) == 0 and m.pop( 0 )) or (len( m ) == 0 and n.pop( 0 )) or (m[0] < n[0] and m.pop(0)) or (n.pop(0))))(a,b) for i in xrange(len( a )+len( b ))]) 

There you have it -- merge sort in three lines of Python. Though, in my opinion, it looks a lot more like something a chronic Perl obfuscator would be proud of. So let's investigate the language "features" that I've employed in order to get the code so compact:

The boolean operators

Python's boolean operators are weird. Instead of returning boolean literals, and and or return one of their operands, in the following way:

A B A and B
True ANYTHING B
False ANYTHING A
A B A or B
True ANYTHING A
False ANYTHING B

It's easy to convince yourself that this behaviour is correct, if esoteric. Making use of this feature, a and b or c behaves very similarly to C/C++/Java's ternary operator (enough for our purposes). The fact that these operators are shortcircuited allows us our next abuse (although it prevents the sort from being general -- the code can't quite handle lists with zeroes in them).

list.pop() returns the value it removes

Due to Python not allowing arbitrary assignments as expressions, we need a convenient method of both incrementing a list, and getting the front of that same list at the same time. Happily, pop will return the list element that you pop from the list, which provides us with a value to insert into our comprehended list. C++'s queue template from the STL has both a front() method, as well as a pop() method, probably just to avoid travesties like this (pop does not return a value).

List comprehensions are sequential

For this code to work, it absolutely depends on the list comprehension getting evaluated like a for loop -- and thankfully that is the case. If it weren't, then all of the pop() side-effects would fall apart quite terribly.

lambda

Need I say more?

And there you have it -- a strictly non-Pythonic implementation of Merge Sort. Hate mail to the usual address, or if you think you can better it, feel free to comment. Everyone else, take this as an educational exercise in writing readable code.

Small disclaimer: This version is not quite general -- it can't handle lists with zeroes in them: I do have a version which makes use of Python 2.5's ternary operator, but the code was a lot more readable.

2 thoughts on “Python Ugliness

  1. The title of your post is quite misleading. I came here expecting to read about the ugliness of or in the Python language, but found that it is an attempt to write ugly, non-Pythonic code, in Python. :-)

    Cool, now we can give Scala, Perl, and Ruby bloggers the run for their money, and show them how much more obfuscated Python code can be. :-)

    Most people don’t realize that it is clever and intelligent people who can write obfuscated code. The only problem is that people with such intellect forms a very small minority. It is the majority of the ordinary programmers who have to read, maintain, and debug the code, while the intelligent ones who wrote that code moves on to more intelligent projects.

  2. In that case, I’ll try to give my posts a bit more of a specific title — this one was intended to complement the previous post I wrote: Python Pretiness.

    And yes, I certainly agree about giving Perl people a run for their money — in fact certain people I know refuse to switch to Python simply because they can’t do such grand obfuscation :)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>