Talk:Introduction

Added the quote by Graham Klyne.

Over the years I've received numerous complaints about the quicksort example. But none of the complainers sent me anything better so it's still here. Anyone want to come up with a better example?

--John Peterson 00:39, 26 January 2006 (UTC)

Perhaps an in-place quicksort? —Ashley Y 04:24, 26 January 2006 (UTC)

If you want to offer "proof" that functional programming is a good idea, starting out with an invalid example pretty much wipes out your credibility. Taking the quicksort example offered, you are saying that if memory and CPU use do not matter ... but they very often do (certainly for large sort operations). Reading up on Haskell looks too much like a waste of time. Why the equivalent quicksort code in Haskell is larger than the C code requires an explanation as to why this is a good idea - and is not suitable material for the introduction. --PrestonBannister 01:51, 12 August 2008 (UTC)

The good idea here is that the algorithm becomes rather obvious when presented in Haskell. dons 04:45, 12 August 2008 (UTC)

That's because the C quicksort and the Haskell "quicksort" use two different algorithms. A naive bubblesort implementation in C is rather obvious, too.

Change the C to mergesort? Because that really is what the Haskell code does. (Okay, sure, it's a funny 3-way, bottom-up, lazy mergesort. Still.) -- AaronDenney 19:55, 10 July 2007 (UTC)

Eh? The defining property of quicksort is that the diving phase is elaborate (filter < and >) but that the conquer phase is simple (list concatenation). For mergesort, it's the other way round. apfeλmus 10:51, 11 December 2007 (UTC)

What is this about Haskell being in 2nd place behind C (gcc) in the computer language shootout, the link provided shows it to be 13th (and 12th on the previous benchmark, even though it does proportionally worst). You're right about functional languages doing well though: Clean, OCaml and MLton indeed occupy positions 6,9,11. --Noegenesis 12:01, 28 August 2007 (UTC)

It was in 2nd place when the article was written, since then benchmarks and programs have changed. dons 00:17, 12 December 2007 (UTC)

Update, mid-2008, the rankings have stabilised with Haskell in 8th, behind C, C++, D and friends. The shootout continues to be a moving target. dons 04:45, 12 August 2008 (UTC)

Most functional languages, and Haskell in particular, are strongly typed, eliminating a huge class of easy-to-make errors at compile time. This sentence confuses strong and static typing. MichalPalka 00:11, 2 December 2007 (UTC)

I created a login account to specifically complain about the qsort example.

All it proves is that you can write your own, or use the standard c lib implementation. So, any programmer who knows c reading this sees it as a Steve Jobs style sales pitch. Developers don't like being lied to, I'd suggest you dump that sales approach for one that is honest, you've lost me.

--Tsingi 11:08, 28 June 2010 (UTC)

Although visually appealing, the Haskell quicksort code has the unfortunate property of doubly traversing the input list. This can be remedied with Bird's proposed

qsort []     = [] 
qsort (x:xs) = part xs ([],[])
  where
    part []     (a,b) = qsort a ++ x : qsort b
    part (y:ys) (a,b) = part ys $ if y<x then (y:a,b) else (a,y:b)

Or, to keep it stable,

qsort (x:xs) = part xs (\(a,b)-> qsort a ++ x : qsort b)
  where
    part []     k = k ([],[])
    part (y:ys) k = part ys $ if y<x then (k.first(y:)) else (k.second(y:))

But that's besides the point, so I removed it from the main page to here. WillNess 00:56, 26 September 2010 (UTC)

I have a simple complaint about the qsort: as I come from a C background, that part makes sense. Since you didn't bother to use the same variable names, or add comments, the Haskell is line noise, save for the symbols qsort and filter. I can't intuit whatever you might be expecting me to learn, so all I see is a long learning curve.

Of course, everyone who knows Haskell already isn't going to offer you a new one, they aren't reading your beginning tutorial.

--Hacksaw 08:56, 21 February 2011 (UTC)

some explanations for Haskell syntax added to the main page per your request. Can't use same names in C and Haskell versions, as C has an array and Haskell version works with lists. Thanks for the suggestion btw. WillNess 01:32, 7 March 2011 (UTC)

Intuitively understanding the "quicksort" implementation

You should be able to understand the program without any previous knowledge of either Haskell or quicksort.

I can assure you that this is not the case. Sure, it might seem that way if you already know a little bit of Haskell, but that's not the target audience of this page now, is it?

Oh, and please stop comparing apples to oranges: that piece of Haskell is not a quicksort implementation, so don't compare it to a real quicksort implementation. – AdrianW 10:52, 3 August 2011 (UTC)

Made some changes which hopefully address your concerns.

Yes, much better. Well done!

As for the second issue, could you please explain? Do you mean it's not a "real" efficient in-place algorithm? Presumably quicksort is a general algorithm which may have extremely inefficient as well as efficient implementations? Is efficiency one of its defining features? WillNess 17:48, 3 August 2011 (UTC)

Well, one might argue that (1) being in-place and (2) selecting a good pivot are crucial properties of the quicksort algorithm, and then again one might argue that divide & conquer alone is the defining concept of quicksort. In my opinion, the clever way of partitioning the list in-place is the most recognizable trait of this algorithm, but that might just be a subjective perception.

However, what's more important is that someone with an imperative background, coming here to be seduced by Haskell's elegance, feels cheated: the C version is longer, more complicated, and not as easy to comprehend as the Haskell version, sure, but it also does the job "better", i.e. in a more efficient way (that's why I spoke of comparing apples and oranges).

An example to illustrate my point: say someone implements a matrix multiplication using Strassen's algorithm; then someone else comes along and says "Dude, why so complicated? I can do the same in 4-5 lines, using 3 simple nested for-loops." – AdrianW 06:14, 4 August 2011 (UTC)

Thanks. Yes I guess more clarifications could be added along those lines, about the tradeoffs of brevity vs efficiency, and Haskell's being able to concisely express a less-efficent, less-tuned-up version of an algorithm, with ease - an "executable specification" kind of thing, a first step in a progression of code developement (of course next, more complicated steps can also be expressed in Haskell, it'll just not be that short). Go ahead, write some yourself, it's a wiki after all! Cheers, WillNess 08:57, 5 August 2011 (UTC)