I think that's a bit extreme for an example - I'd go for the following version, which is less concise but easier to read:

  quicksort :: Ord a => [a] -> [a]
  quicksort []     = []
  quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
      where
          lesser  = filter (< p) xs
          greater = filter (>= p) xs

So, what's going on here? First you have the declaration of the function - in this case, you have a list of items of type A which can be compared to another one (Ord means "I can use <, <= and so on over this element"), and you'll return a list of type A.

Then you have the base case - if the list is empty, you'll return an empty list.

After that you have the case "item++[list of items]" (note that the second one can be an empty list), where you return [list of smaller items]++item++[list of larger items] (the two lists are defined under the "where" - filter removes elements from a list).

Note however that, instead of "(lesser) ++ item ++ (larger)" you have "(quicksort lesser) ++ item ++ (quicksort larger)" - this will call the algorithm recursively over smaller lists, but I bet you already knew that.

Both pieces of code do the same thing, but I think mine is what you'd expect from a typical piece of Haskell code - the one you have is closer to "see how small I can make this function".

This is a nice example what Haskell can do, but the sort itself is quite inefficient and it's not a true quicksort.

It's absolutely a true quicksort.

Is it in place? If not, then it is not a true quicksort.

Interesting question -- in Haskell that means something else (some would say "nothing"). The language is designed around making sure that you only specify the function that the code is supposed to accomplish, and all implementation decisions are left to the compiler -- just as it would be for the RHS of a statement like `x = 3 + 4*(5 + 1);` in C.

In this case, as in all others, the Haskell compiler would decide what is the optimal way to implement it, given whatever other constraints you've placed on the program.

You can add additional constraints that ensure the compiled code turns out to be in-place, at a cost of verbosity.

If there is an example where such an optimization has actually been implemented and correctly chosen, that is news to me.

I mean, to a very large extent, this is the reason why classical imperative languages are so easy to understand and reason about. The programmers directions are much more straight forwardly executed than in examples like these hypotheticals.

Oh, I just got to your last sentence. Basically, that this would be a lot more verbose if written in such a way that it would be in place. Which is kind of the point of this criticism. Isn't it?

Don't get me wrong, the power of Haskell is not really in question. Just that example.

Your criticisms are all from the perspective of "it keeps me from telling it how to implement the functionality", which is true, but not what Haskell's design (or pure FP language design in general) optimizes for.

Sometimes, you really do want to make commands to the bare metal regarding exactly how you want the program implemented. For general use, however, you don't: compilers are (at least these days) a lot better at finding optimizations than the typical user.

It comes down to abstraction levels: pick the one that matches the problem you're working on. The FP philosophy is "speaking about specific memory cells is way too low" in most cases, like telling it you want a sorted list.

In fact, it would probably be even better (from that selfsame philosophy) to define a sort in terms of the conditions the final list would meet (as opposed to nested, recursing conditions like in the example). Something like, "return a list where every element is <= the one after it, and where every element is also in the original list, as many times as it occurs there".

If you want to see the examples of quicksort in Haskell to enforce in-place and other requirements, see this discussion here, with links:

http://www.haskell.org/haskellwiki/Introduction/Direct_Trans...

tl;dr: Yeah, Haskell is worse at letting you force the sort to be in-place, but that can be a very good thing.

I understand what you are saying. I'm arguing that when quick sort was first contrived, the speed aspect that you can achieve with the in place variant was not just a lucky by product. It was the bloody point. To such an extent that if you are lucky enough -- which most of us are -- to be in a place where that is not a consideration, then sure, go for the higher level abstractions.

That said, it is highly telling that none of the actual implementations of quick sort in any of these languages are that succinct. To the point that it is still a truism to "use a library" for something such as sorting. Because that isn't easy. Do not be fooled by such a quaint example.

Haskell:

http://www.haskell.org/pipermail/haskell-cafe/2009-August/06...

Twice as slow as C but without also in-place like C and extremely similar (see the sort function here):

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sortin...

It's interesting to see is how very similar Haskel and C sources fundamentally become once they really solve the same problem and not the different ones.

The "direct compare" in Haskell isn't. The Ord constraint effectively passes a dictionary, and even if that were inlined in a particular case you could always apply a newtype for a different ordering.

I'd really like to learn, can you please explain where the Ord constraint is, and where the dictionary is passed in the link I've given (with the STUArray -- isn't that really an array in a C sense)? To give you an idea how little I know: I understand the basic ideas of Haskell (that is, what I as a C programmer who made some compilers understand as basic: the type inference and the illusion of the infinite memory by not doing things in place but lazily with the GC unless unsafe or when it is possible to optimize the laziness out) but I don't really know the language. Thanks in advance.

Ah, my bad, the STUArray example is specialized and probably does not pass an Ord around (though there's implicitly one present because of the less-then). Certainly, the function does not meaningfully allow the user to pick it.

Has anyone ever bothered to ask Tony Hoare what he thinks on this topic? I know SPJ and him both work for MS Research, maybe he can get on that and settle this for us.

I would be curious to know the answer. Though, I should have added in my original post that I am far from the originator of this view. I see a sibling post elaborated. I think the crux is simply that without the "in place" nature, it loses a lot of its speed advantage. Cache localities and such.

Quicksort can be implemented in an in-place fashion, but that's not a requirement by any means.

If I understand correctly, this code has a bug.

The list is the sorted list of lesser items, then the pivot, then the sorted list of greater items. But since the list of greater items is defined with ">=" rather than just ">", the list of greater items will also contain the pivot. That will put the pivot in the sorted list twice (for each recursive call).

Note that the argument, the list to be sorted, is pattern matched as

    (p:xs)

which means that p is the first element of the list, and xs is the rest of the elements (i.e., xs does not contain p). In the definition of "greater":

    greater = filter (>= p) xs

, the filter is applied to xs, which means that p will not be included.

Ah, I see. Thanks!

If I'm reading the code correctly: given the list [5,5,2,3] and the match (p:xs), p will match to the first 5 and xs will match to [5,2,3].

Once the matching is done, the pivot is no longer in the list xs, and therefore it won't be included twice.

Thanks for the insightful reply! I can understand most of the code but I still do not understand how should I know what "p" and "xs" is. Is it something you get when you declare the function as being "possible" to order (I believe that's what "Ord" means based on your explanation)?

One last thing I'll add to the other replies, the example shown is a bit unusual, like indexing a for loop with "q" instead of "i". The traditional pattern is this:

    (x:xs)

And that reads "x and the rest of the x-es", that is, the "xs" is not "ex ess", but "plural x", whatever remainder remains of the list of "things" in that list. (p:xs) is a bit weird, but if I saw (p:ps) I'd understand.

Also, Haskellers often use "x" here because they write a lot of functions that operate on "anything"; for instance, in this case, you don't really know what you're sorting, so, call it x because what other name is any better? There's a set of about 10 of these conventional one-letter variable names. (A few more than conventional imperative languages, but not obscenely so; imperative has i, j, and k for iteration, a and b in sorting, sometimes f for function, and p for pointer.)

I assume here it's p for pivot, xs because the rest of the list is just items, not pivots (as ps would imply). I'm not sure I love the naming choice, but it has a logic to it.

Those are pattern matches [1]. In Haskell, you have a very powerful pattern matching system for describing and deconstructing function arguments. So quicksort here is defined as

    quicksort [] = []
    quicksort (p:xs) = ...

The first pattern, [], matches an empty list. The second pattern, (p:xs), matches a list of length 1 or greater, and binds the first element of the list to the variable p, and the rest of the list to the variable xs. In other words, p is the head, xs is the tail. Note that in the case of a 1-element list, the tail will be empty.

This is a valid pattern match because AFAIK the colon (:) is a type constructor in Haskell, and it's used to create lists. For instance, 1 : [] == [1], and 1 : 2 : [3, 4] = [1, 2, 3, 4].

Because (:) is a type constructor, and not an operator (unlike (+) for instance), you can use it in pattern matching expressions to deconstruct lists. This is quite useful for many things, as you might imagine.

[1]: https://en.wikibooks.org/wiki/Haskell/Pattern_matching

(:) is a data constructor, not a type constructor, and its type is a -> [a] -> [a]. Examples of type constructors: [], Maybe, Either.

To be clear: [] can refer to two different entities, a data constructor (empty list) and a type constructor (the list type).

Thanks for the clarification. You might be able to tell, that I am only in the first stages of trying to learn Haskell.

No, it's pattern matching (it's a bit warty because that's the only case I can think of where the pattern matching part doesn't look like the way you build the data structure).

Normal pattern matching:

   -- a Foo record, with a data constructor Foo and a single field
   data Foo = Foo { bar :: String }

   -- takes an instance of Foo, returns "prefix:" + the value of the bar field
   prefixBarInFoo :: Foo -> String
   -- Pattern matches on Foo, tells Haskell to bind 'valueOfBar' to the 'bar' field of the instance of Foo
  prefixBarInFoo (Foo valueOfBar) = "prefix:" ++ valueOfBar

List pattern matching:

    myList = [1,2,3,4,5]

    addOne :: [Integer] -> [Integer]
    addOne [] = []
    -- when called with 'myList', binds x to 1 and xs to [2,3,4,5] (the rest of the list)
    addOne (x:xs) = (x+1) : (addOne xs)

As dllthomas commented, 'p' would be better named "pivot".

xs is just convention. A variable containing an arbitrary number is often called 'x', right? Well, a list of such things is plural, so xs.

So pattern match a list, say the first item is the pivot, the remainder is just a list of arbitrary numbers, 'xs'.

That is how you destructure the list, with the syntax (x:xs) where x is the first element of the list, and xs is the remainder of the list.

Absolutely not. I'm actually very frustrated that they give that code as an example. First of all, it misses the most important of quicksort - the fact that it can be implemented in place (and yes, you can write an pure in-place quicksort using STArrays).

Second of all, it's bad because it runs through the list xs twice. Instead, they should use the partition function to get both the left-hand and right-hand sides at once.

And thirdly, it's inefficient by use of the (++) operator, which takes time proportional to the length of the left-hand list. A better (out-of-place) implementation of quicksort would use an accumulator so this wouldn't happen (and actually, this means that we should do the partitioning ourselves rather than using the partition function as mentioned above).

Here is an example that makes these improvements with quicksort [1].

[1] http://en.literateprograms.org/Quicksort_(Haskell)#Using_an_...

This is a typical pitfall of many FP code chuck examples. trading efficiency for superficial succinctness.

Eh, a lot of FP is used for teaching. I don't think this example is as much about succinctness as it is about clarity. The idea of partitioning on a pivot and recursing is definitely key to quicksort, if not its totality.

It indeeds looks a bit magical, like the infamous fibonacci example that uses lazy lists.

I don't think that list comprehensions are very idiomatic in Haskell, one would probably use Data.List.partition instead:

    qsort [] = []
    qsort (p:xs) = low ++ [p] ++ high
        where (low, high) = partition (< p) xs

I think you are missing the recursive calls ;).

Indeed!

Hey, who said that static typing caught all bugs ? :)

Sure it does, you just need Quickcheck property based testing:

    forall $ \xs -> sorted (qsort xs :: [Int])

That's not static.

Or typing

No, it's not, but Haskell's type system is what allows quickcheck to work as well as it does. The implementations in other languages mostly lack a lot of the power provided by the type system.

It's fairly natural "teaching code". I'd say it's a concise example of one of the ideas behind quicksort, though, as many are quick to point out, it ignores a lot of other very important aspects.

That said, it's not very good practicing Haskell code. We can look at the Data.List module from the base package to see some optimized list operations with a well-designed module API [0] though some of the optimization methods will be non-obvious and kludgy looking. Data.Complex shows some fairly natural data structure work [1] if you factor out the CPP headers which are there so it'll compile on both GHC and Hugs while using all of the newest GHC features.

[0] http://hackage.haskell.org/package/base-4.6.0.1/docs/src/Dat...

[1] http://hackage.haskell.org/package/base-4.6.0.1/docs/src/Dat...

List comprehensions actually don't tend to get used very frequently, so I would not point to that as a good example of what Haskell code looks like. It's hard to point to one example, as different parts of the code look very different. That is, pure functions look very different from monadic functions, which both look very different from datatype declarations and typeclass instances. I would recommend poking around a whole codebase, one example of which can be found here: https://github.com/xmonad/xmonad

This post may also be useful: http://blog.ezyang.com/2011/11/how-to-read-haskell/

It's a good example of how quickly you can express an algorithm, but in terms or readability, some additional whitespace, and possibly some better naming would make it nicer.

Once you understand what bits like "p:xs", "++" and "[x|y,z]" mean though, it will make much more sense.

I'd say it's good in the sense that it is readable provided you are familiar with the syntax for list comprehensions and appendings, and obviously correct if you know quicksort.

Unless you consider part of the definition of quicksort to be "in place".

As good as sort is a good example of real world problem.

It does give you a broad idea, but does not in any way show what a complex program looks like.