8 ms·

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]

• emillon 13y ago
  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
  • danieldk 13y ago
    I think you are missing the recursive calls ;).
    • emillon 13y ago
      Indeed! Hey, who said that static typing caught all bugs ? :)
      • axman6 13y ago
        Sure it does, you just need Quickcheck property based testing: forall $ \xs -> sorted (qsort xs :: [Int])
        • wnoise 13y ago
          That's not static.
        • dangirsh 13y ago
          Or typing
          • axman6 13y ago
            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.
• thetwiceler 13y ago
  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_accumulator http://en.literateprograms.org/Quicksort_(Haskell)#Using_an_...
  • ww2 13y ago
    This is a typical pitfall of many FP code chuck examples. trading efficiency for superficial succinctness.
    • tel 13y ago
      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.
• th0114nd 13y ago
  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.
  • dllthomas 13y ago
    Unless you consider part of the definition of quicksort to be "in place".
• nbouscal 13y ago
  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 https://github.com/xmonad/xmonad This post may also be useful: http://blog.ezyang.com/2011/11/how-to-read-haskell/ http://blog.ezyang.com/2011/11/how-to-read-haskell/
• marcosdumay 13y ago
  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.
• probably_wrong 13y ago
  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".
  • iaskwhy 13y ago
    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)?
    • mhitza 13y ago
      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.
    • delluminatus 13y ago
      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 https://en.wikibooks.org/wiki/Haskell/Pattern_matching
• danpalmer 13y ago
  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.
• tel 13y ago
  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/Data-List.html#sort 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/Data-Complex.html http://hackage.haskell.org/package/base-4.6.0.1/docs/src/Dat...