I didn't know what Haskell code looked like so I went to the official website and there was this code example[1]:
qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]
Is this a good example of good Haskell code?
qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]
Is this a good example of good Haskell code?
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
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".
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.
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.
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.
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.
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 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).
(p:xs)
greater = filter (>= p) xs
Once the matching is done, the pivot is no longer in the list xs, and therefore it won't be included twice.
(x:xs)
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.)
quicksort [] = []
quicksort (p:xs) = ...
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.
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
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)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'.
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_...
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) xsHey, who said that static typing caught all bugs ? :)
forall $ \xs -> sorted (qsort xs :: [Int])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...
This post may also be useful: http://blog.ezyang.com/2011/11/how-to-read-haskell/
Once you understand what bits like "p:xs", "++" and "[x|y,z]" mean though, it will make much more sense.
It does give you a broad idea, but does not in any way show what a complex program looks like.