I would suggest it's best to show (at least) 4 versions of the code to compare two language: the naive implementation in both languages, and the really optimised version in both languages (plus intermediate levels of optimisation if you feel dedicated). That gives a picture of how fast the typical code one would write will be, as well as the potential for optimisation if you are experiencing bottlenecks, and how much effort it takes to optimise the code.
[1] http://augustss.blogspot.co.uk/2007/08/quicksort-in-haskell-...
Haskell version is totally naïve. That's the point.
Once you start modifying code to make it run faster it's no longer a 'naive' implementation. No matter how nice or logical you think those transformations are.
I'm not saying you can't compare the stream-fusion version against other languages, just that it's highly disingenuous to optimise the Haskell code with some external libraries but then argue that optimisations of the C version are unfair.
The first version [1] is simple and slow. The second version [2] is complex and fast.
The third, fast version [3] is identical to the first, simple version, with list processing functions imported from the `stream-fusion` package. This is the entire point of this article.
The only transformation shown is purely mechanical (prepending symbol names with the qualified import prefix `S.`), and even this is not required (as `Prelude` could have been imported `hiding` the appropriate symbol names instead).
[1]: http://www.mit.edu/~mtikekar/posts/src/collatz.hs
There is also no benevolent dictator in charge of Haskell.
http://research.microsoft.com/en-us/um/people/simonpj/papers...
http://www.reddit.com/r/haskell/comments/1br0ls/haskell_beat...
Likewise, stream fusion isn't always a win! Stream fusion and its siblings are great for pointwise operations, but aren't always a good idea for computations with heavy reuse, like nested convolutions or performant matrix multipy
If you want to use fusion, the best place is the `vector` package.
What we can do, is measure complexity empirically and extrapolate something from there. I haven't done a lot of tests with this code but to me it seemed like it would scale the same as the original one but had a much lower constant.
So here is the code: http://lpaste.net/96397
Here are my measurements: