Fonctionnal languages let you run O(n log(n)) algorithms in O(n)

OK, not exactly. I’m currently trying to grasp the whole fuss about functional programming by learning Haskell (I know it is irrelevant as most functional languages, but at least it is not as slow or unreadable as the others). I’m doing that really seriously, reading this and even doing the exercises. One of them involves writing a Graham scan algorithm. It is a really nice exercise because it lets you manipulate most of what you have just learned in the previous chapters, but requires that you actually get a clue of what is it you are writing.

After struggling with the syntax, I quickly gave up and asked Google for an answer. The first hit for “graham scan haskell” was this. The person who wrote this post did all the first steps properly, but for the final step he just goes through the list of points and filters it somehow. Turns out this is what has been done since the beginning of the book.

Let’s run this code with this a special test case :

grahamScan [ (Point 0 0), (Point 1 0), (Point 0 1), (Point 1 1), (Point 2 1), (Point 0.5 0.5),
   (Point 0.2 0.6), (Point 0.3 0.6), (Point 0.2 0.7), (Point 0.4 0.6), (Point 0.2 0.5) ]
[Point 0.0 1.0,Point 0.2 0.7,Point 0.2 0.6,Point 0.3 0.6,Point 0.4 0.6,Point 1.0 1.0,
   Point 2.0 1.0,Point 1.0 0.0,Point 0.0 0.0]

Well, it doesn’t look too right, and indeed, it is completely off. Going through a list and removing elements as you go takes O(n). The real algorithm, as stated on Wikipedia takes O(n log n).

Turns out you have to wait for the fourth Google result to find someone who realizes this approach will not work (and he proposes no solutions yet), and most of the following hits are copies of a single message. I could not find any correct solution in Haskell in polynomial time, and had to write one on my own. I will try to clean it up and post it in the hope that at least there will be a not so wrong answer somewhere on the Internet, but it would be cool if somebody who actually knows what he his doing could point me to an elegant solution. Mine looks quite crude …

I found this situation quite funny, as I have heard quite a few functional programming advocates telling me how their code is so much more concise than with imperative programming. Yes, your code is concise. But it is also wrong.


2 thoughts on “Fonctionnal languages let you run O(n log(n)) algorithms in O(n)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s