Hacker News Reader

Comment by iaskwhy | Hacker News Reader

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

View on HN

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.

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

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

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.

Reply on news.ycombinator.com