5 ms·

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]

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
  - hikarudo 13y ago
    (:) is a data constructor, not a type constructor, and its type is a -> [a] -> [a]. Examples of type constructors: [], Maybe, Either.
    - deleted 13y ago
      [deleted]
    - delluminatus 13y ago
      Thanks for the clarification. You might be able to tell, that I am only in the first stages of trying to learn Haskell.
    - sold 13y ago
      To be clear: [] can refer to two different entities, a data constructor (empty list) and a type constructor (the list type).
- deleted 13y ago
  [deleted]
- mercurial 13y ago
  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)
- jerf 13y ago
  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.)
  - dllthomas 13y ago
    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.
- lostcolony 13y ago
  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'.
funky_lambda 13y ago
This is a nice example what Haskell can do, but the sort itself is quite inefficient and it's not a true quicksort.
- theseoafs 13y ago
  It's absolutely a true quicksort.
  - taeric 13y ago
    Is it in place? If not, then it is not a true quicksort.
    - theseoafs 13y ago
      Quicksort can be implemented in an in-place fashion, but that's not a requirement by any means.
      - archgoon 13y ago
        http://www.informit.com/articles/article.aspx?p=1407357&seqNum=3 http://www.informit.com/articles/article.aspx?p=1407357&seqN...
    - SilasX 13y ago
      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.
      - taeric 13y ago
AnimalMuppet 13y ago
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).
- nemetroid 13y ago
  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.
  - AnimalMuppet 13y ago
    Ah, I see. Thanks!
- probably_wrong 13y ago
  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.

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
- hikarudo 13y ago
  (:) is a data constructor, not a type constructor, and its type is a -> [a] -> [a]. Examples of type constructors: [], Maybe, Either.
  - deleted 13y ago
    [deleted]
  - delluminatus 13y ago
    Thanks for the clarification. You might be able to tell, that I am only in the first stages of trying to learn Haskell.
  - sold 13y ago
    To be clear: [] can refer to two different entities, a data constructor (empty list) and a type constructor (the list type).
deleted 13y ago
[deleted]
mercurial 13y ago
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)
jerf 13y ago
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.)
- dllthomas 13y ago
  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.
lostcolony 13y ago
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'.

funky_lambda 13y ago

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

theseoafs 13y ago
It's absolutely a true quicksort.
- taeric 13y ago
  Is it in place? If not, then it is not a true quicksort.
  - theseoafs 13y ago
    Quicksort can be implemented in an in-place fashion, but that's not a requirement by any means.
    - archgoon 13y ago
      http://www.informit.com/articles/article.aspx?p=1407357&seqNum=3 http://www.informit.com/articles/article.aspx?p=1407357&seqN...
  - SilasX 13y ago
    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.
    - taeric 13y ago

AnimalMuppet 13y ago

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).

nemetroid 13y ago
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.
- AnimalMuppet 13y ago
  Ah, I see. Thanks!
probably_wrong 13y ago
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.