4 ms·

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

• 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'.