• Choose a category
• All
• Classic-Fiction

quicksort :: (Ord a) => [a] -> [a]

quicksort [] = []

quicksort (x:xs) =

let smallerOrEqual = [a | a <- xs, a <= x]

larger = [a | a <- xs, a > x]

in quicksort smallerOrEqual ++ [x] ++ quicksort larger

The type signature of our function is quicksort :: (Ord a) => [a] -> [a], and the empty list is the base case, as we just saw.

Remember, we’ll put all the elements less than or equal to x (our pivot) to its left. To retrieve those elements, we use the list comprehension [a | a <- xs, a <= x]. This list comprehension will draw from xs (all the elements that aren’t our pivot) and keep only those that satisfy the condition a <= x, meaning those elements that are less than or equal to x. We then get the list of elements larger than x in a similar fashion.

We use let bindings to give the two lists handy names: smallerOrEqual and larger. Finally, we use the list concatenation operator (++) and a recursive application of our quicksort function to express that we want our final list to be made of a sorted smallerOrEqual list, followed by our pivot, followed by a sorted larger list.

Let’s give our function a test drive to see if it behaves correctly:

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]

[1,2,2,3,3,4,4,5,6,7,8,9,10]

ghci> quicksort "the quick brown fox jumps over the lazy dog"

" abcdeeefghhijklmnoooopqrrsttuuvwxyz"

Now that’s what I’m talking about!

Thinking Recursively

We’ve used recursion quite a bit in this chapter, and as you’ve probably noticed, there’s a pattern to it. You start by defining a base case: simple, nonrecursive solution that holds when the input is trivial. For example, the result of sorting an empty list is the empty list, because—well, what else could it be?

Then, you break your problem down into one or many subproblems and recursively solve those by applying the same function to them. You then build up your final solution from those solved subproblems. For instance, when sorting, we broke our list into two lists, plus a pivot. We sorted each of those lists separately by applying the same function to them. When we got the results, we joined them into one big sorted list.

The best way to approach recursion is to identify base cases and think about how you can break the problem at hand into something similar, but smaller. If you’ve correctly chosen the base cases and subproblems, you don’t even have to think about the details of how everything will happen. You can just trust that the solutions of the subproblems are correct, and then you can just build up your final solutions from those smaller solutions.

Chapter 5. Higher-Order Functions

Haskell functions can take functions as parameters and return functions as return values. A function that does either of these things is called a higher-order function. Higher-order functions are a really powerful way of solving problems and thinking about programs, and they’re indispensable when using a functional programming language like Haskell.

Curried Functions

Every function in Haskell officially takes only one parameter. But we have defined and used several functions that take more than one parameter so far—how is that possible?

Well, it’s a clever trick! All the functions we’ve used so far that accepted multiple parameters have been curried functions. A curried function is a function that, instead of taking several parameters, always takes exactly one parameter. Then when it’s called with that parameter, it returns a function that takes the next parameter, and so on.

This is best explained with an example. Let’s take our good friend, the max function. It looks as if it takes two parameters and returns the one that’s bigger. For instance, consider the expression max 4 5. We call the function max with two parameters: 4 and 5. First, max is applied to the value 4. When we apply max to 4, the value that is returned is actually another function, which is then applied to the value 5. The act of applying this function to 5 finally returns a number value. As a consequence, the following two calls are equivalent:

ghci>