Probably Maybe Quicksort

[ghost]

On the last line of the first Hutton pwp, we get the following snippet of code:

mystery [] = []
mystery (x:xs) = mystery ys ++ [x] ++ mystery zs
  where
    ys = [a | a <- xs, a <= x]
    zs = [a | a <- xs, a > x]

Here's my understanding of the code, please correct me if I'm wrong:

• The mystery function takes a list as an input.
• If the list is empty, it returns an empty list (this acts as the base case of the recursive calls later).
• Else, it uses (x:xs) to select the first element of the list (x), and uses it as the pivot.
• It makes 2 new unsorted lists, ys and zs, which contain elements of xs which are <=x and x> respectively.
• It then recursively calls itself on ys and zs to sort them.

So if I remember correctly from ADS (which would be a miracle), this is Quicksort?

[wence-]

A miracle has occurred! This is indeed quicksort.

The non-empty list is partitioned around a pivot element (we just pick the head of the list) into elements <= the pivot or > the pivot. Then, we recurse to sort those bits.

[ghost]

Is there any advantage of selecting the head this way instead of head [list]?

[wence-]

It's more idiomatic to do this (the pattern match makes it clear that our recursion is operating by picking out the head element). We could write

mystery [] = []
mystery xs = mystery ys ++ [x] ++ mystery zs
  where
    x = head xs
    ys = [a | a <- tail xs, a <= x]
    zs = [a | a <- tail xs, a > x]

But it means we have to read more code to see where x comes from, and also need to explicitly ask for the tail of xs in the list comprehensions that populate ys and zs.

Edit: fixed bug in code example (I had forgotten to call tail).