Explain this 'Merge' Function in Haskell

Question

I am learning Haskell and I am having trouble understanding this function. I am implementing mergesort. I have the mergesort recursive function implemented, but I don't understand what this 'merge' function is doing. I understand merge sort in an imperative language, but I don't understand the syntax here.

merge []         ys                   = ys
merge xs         []                   = xs
merge xs@(x:xt) ys@(y:yt) | x <= y    = x : merge xt ys
                          | otherwise = y : merge xs yt

Answer 1

merge []         ys                   = ys

If the first argument is empty, give the second argument.

merge xs         []                   = xs

If the second argument is empty, give the first argument.

merge xs@(x:xt) ys@(y:yt) | x <= y    = x : merge xt ys
                          | otherwise = y : merge xs yt

If x is smaller than or equal to y, cons (add to the front) x to the result of merging the rest of xs (which is xt) with ys. Otherwise y was smaller, so cons it to the result of merging xs with the rest of ys (which is yt).

xs@(x:xt) is parameter destructuring using a "placeholder". The result is that xs will refer to the entire first argument, while x is the head and xt is the tail.

Since merge is recursively defined, it will continue to cons elements from xs and ys until at least one is empty and then simply return it.

The bars (|) signify "guards", which let you define conditions in a nice and succinct manner.

Answer 2

Let's break this down line by line:

1. merge [] ys = ys

   This line pattern matches on the first list. If the first list is an empty list (i.e. []), then return the second list.

2. merge xs [] = xs

   Same as before, only with the lists role reversed.

3. merge xs@(x:xt) ys@(y:yt)

   A pattern match like (x:xt) matches only if the list element is non-empty. If it matches x is set to the first element, and xt is set to the rest of a list. Remember that : is the list constructor operator (i.e., 1 : [2, 3] == [1, 2, 3]). The xs@... prefix means that whole list is set to xs. This is useful if you need refer to the whole list as well as to its head and tail, at the same time.