• Choose a category
• All
• Classic-Fiction

zip

zip is another function for working with lists that we’ve met in Chapter 1. It takes two lists and zips them together. For instance, calling zip [1,2,3] [7,8] returns [(1,7),(2,8)] (the function truncates the longer list to match the length of the shorter one).

Zipping something with an empty list just returns an empty list, which gives us our base case. However, zip takes two lists as parameters, so there are actually two base cases:

zip' :: [a] -> [b] -> [(a,b)]

zip' _ [] = []

zip' [] _ = []

zip' (x:xs) (y:ys) = (x,y):zip' xs ys

The first two patterns are our base cases: If the first or second list is empty, we return an empty list. The third pattern says that zipping two lists together is equivalent to pairing up their heads, then appending their zipped tails to that.

For example, if we call zip' with [1,2,3] and ['a','b'], the function will form (1,'a') as the first element of the result, then zip together [2,3] and [b] to obtain the rest of the result. After one more recursive call, the function will try to zip [3] with [], which matches one of the base case patterns. The final result is then computed directly as (1,'a'):((2,'b'):[]), which is just [(1,'a'),(2,'b')].

elem

Let’s implement one more standard library function: elem. This function takes a value and a list, and checks whether the value is a member of the list. Once again, the empty list is a base case—an empty list contains no values, so it certainly can’t have the one we’re looking for. In general, the value we’re looking for might be at the head of the list if we’re lucky; otherwise, we have to check whether it’s in the tail. Here’s the code:

elem' :: (Eq a) => a -> [a] -> Bool

elem' a [] = False

elem' a (x:xs)

| a == x = True

| otherwise = a `elem'` xs

Quick, Sort!

The problem of sorting a list containing elements that can be put in order (like numbers) naturally lends itself to a recursive solution. There are many approaches to recursively sorting lists, but we’ll look at one of the coolest ones: quicksort. First we’ll go over how the algorithm works, and then we’ll implement it in Haskell.

The Algorithm

The quicksort algorithm works like this. You have a list that you want to sort, say [5,1,9,4,6,7,3]. You select the first element, which is 5, and put all the other list elements that are less than or equal to 5 on its left side. Then you take the ones that are greater than 5 and put them on its right side. If you did this, you’d have a list that looks like this: [1,4,3,5,9,6,7]. In this example, 5 is called the pivot, because we chose to compare the other elements to it and move them to its left and right sides. The only reason we chose the first element as the pivot is because it will be easy to snag using pattern matching. But really, any element can be the pivot.

Now, we recursively sort all the elements that are on the left and right sides of the pivot by calling the same function on them. The final result is a completely sorted list!

The above diagram illustrates how quicksort works on our example. When we want to sort [5,1,9,4,6,7,3], we decide that the first element is our pivot. Then we sandwich it in between [1,4,3] and [9,6,7]. Once we’ve done that, we sort [1,4,3] and [9,6,7] by using the same approach.

To sort [1,4,3], we choose the first element, 1, as the pivot and we make a list of elements that are less than or equal to 1. That turns out to be the empty list, [], because 1 is the smallest element in [1,4,3]. The elements larger than 1 go to its right, so that’s [4,3]. Again, [4,3] is sorted in the same way. It too will eventually be broken up into empty lists and put back together.

The algorithm then returns to the right side of 1, which has the empty list on its left side. Suddenly, we have [1,3,4], which is sorted. This is kept on the left side of the 5.

Once the elements on the right side of the 5 are sorted in the same way, we will have a completely sorted list: [1,3,4,5,6,7,9].

The Code

Now that we’re familiar with the quicksort algorithm, let’s dive into its implementation