(:), (++), and concat

Since (:) is one of the data constructors of the list type, we can use it to build lists:

GHCi

>>> 1 : [2,3,4]
[1,2,3,4]
>>> 1 : 2 : 3 : 4 : []
[1,2,3,4]

We can build lists like this without parentheses because the (:) operator is right-associative: 1 : 2 : 3 : 4 : [] = 1 : (2 : (3 : (4 : []))).

We also have the list concatenation operator (++) that I mentioned in an earlier exercise:

GHCi

>>> [1,2] ++ [3] ++ [4,5]
[1,2,3,4,5]

The associativity of this operator does not matter much for its semantics, but for its efficiency, it is important that it is also right-associative. Here is its implementation:

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

If we want to concatenate more than two lists, we can of course use the ++ operator more than once, as I did in the example above. For concatenating many or an unknown number of lists, we have concat:

GHCi

>>> concat [[1],[2,3],[],[4,5]]
[1,2,3,4,5]

The input is a list of lists. concat concatenates all the lists in this list:

concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

Using the foldr function discussed shortly, we can obtain a more succinct implementation:

concat = foldr (++) []

Exercise

The standard library has a function

partition :: (a -> Bool) -> [a] -> ([a], [a])

The invocation partition pred xs produces a pair of lists (ys, ns). ys contains all elements of xs for which pred is true. ns contains all elements of xs for which pred is false:

GHCi

>>> import Data.List
>>> partition even [1,2,3,4,5]
([2,4],[1,3,5])

Pretend that this function doesn't exist and implement it yourself.

Solution

partition :: (a -> Bool) -> [a] -> ([a], [a])
partition pred = go
  where
    go [] = ([], [])
    go (x:xs)
        | pred x    = (x : ys,     ns)
        | otherwise = (    ys, x : ns)
      where
        (ys, ns) = go xs

Exercise

With partition in hand (from the previous exercise), we can try our hand at implementing another sorting algorithm: Quicksort.

quickSort :: [Int] -> [Int]

Let's review how Quicksort works. For an empty input list, Quicksort produces an empty list. That's clearly the sorted version of the empty list. To sort a non-empty list xs, we pick some element p in xs as a pivot. We then split xs into three lists lts, eqs, and gts containing all elements that less than, equal to, an d greater than p, respectively. To sort xs, we sort lts and gts recursively and then concatenate the sorted version of lts with eqs and the sorted version of gts.

Where different implementations of Quicksort differ is in how they choose the pivot p. A really good choice is to pick p randomly. That's not easy to do in Haskell because we expect a function that picks a random element from a list to return different results if we call this function multiple times on the same list. Such a function cannot be pure—it must involve side effects—because the result of a pure function is completely determined by its arguments. The Haskell standard library does provide random number generators, but using them requires the IO monad, which we haven't talked about yet. There also exist implementations of Quicksort that carefully pick the pivot so that it is guaranteed that neither lts nor gts contains more than a constant fraction of the elements in xs. This guarantees that such an implementation of Quicksort runs in \(O(n \lg n)\) time. In practice, these implementations are fairly slow, because picking a pivot that is guaranteed to split xs fairly evenly is a lot of work. The simplest implementation simply picks the first element of xs as pivot. This is easy to do and requires no randomness. So that's the implementation we opt for here.

Implement quickSort.

Solution

quickSort :: [Int] -> [Int]
quickSort []       = []
quickSort xs@(p:_) = quickSort lts ++ eqs ++ quickSort gts
  where
    (lts, ges) = partition (< p) xs
    (gts, eqs) = partition (> p) ges