Haskell/Higherorder functions and Currying
Higherorder functions are functions that take other functions as arguments. We have already met some of them, such as map
, so there isn't anything really frightening or unfamiliar about them. They offer a form of abstraction that is unique to the functional programming style. In functional programming languages like Haskell, functions are just like any other value, so it doesn't get any harder to deal with higherorder functions.
Higher order functions have a separate section in this book, not because they are particularly difficult – we've already worked with them, after all – but because they are powerful enough to draw special attention to them. We will see in this section how much we can do if we can pass around functions as values. Generally speaking, it is a good idea to abstract over a functionality whenever we can. Besides, Haskell without higher order functions wouldn't be quite as much fun.
The Quickest Sorting Algorithm In Town[edit]
Don't get too excited, but quickSort
is certainly one of the quickest. Have you heard of it? If so, you can skip the following subsection and go straight to the next one.
The Idea Behind quickSort
[edit]
The idea is very simple. For a big list, we pick an element, and divide the whole list into three parts.
The first part has all elements that should go before that element, the second part consists of all of the elements that are equal to the picked element, the third has the elements that ought to go after that element. And then, of course, we are supposed to concatenate these. What we get is somewhat better, right?
The trick is to note that only the first and the third are yet to be sorted, and for the second, sorting doesn't really make sense (they are all equal!). How to go about sorting the yettobesorted sublists? Why... apply the same algorithm on them again! By the time the whole process is finished, you get a completely sorted list.
So Let's Get Down To It![edit]
 if the list is empty, we do nothing  note that this is the base case for the recursion quickSort [] = []  if there's only one element, no need to sort it  actually, the third case takes care of this one pretty well  I just wanted you to take it step by step quickSort [x] = [x]  this is the gist of the process  we pick the first element as our "pivot", the rest is to be sorted  don't forget to include the pivot in the middle part! quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more) where less = filter (< x) xs equal = filter (== x) xs more = filter (> x) xs
And we are done! Even if you have met quickSort
before, perhaps you thought recursion was a neat trick but difficult to implement.
Now, How Do We Use It?[edit]
With quickSort
at our disposal, sorting any list is a piece of cake. Suppose we have a list of String
, maybe from a dictionary, and we want to sort them; we just apply quickSort
to the list. For the rest of this chapter, we will use a pseudodictionary of words (but a 25,000 word dictionary should do the trick as well):
dictionary = ["I", "have", "a", "thing", "for", "Linux"]
We get, for quickSort dictionary
,
["I", "Linux", "a", "for", "have", "thing"]
But, what if we wanted to sort them in the descending order? Easy, just reverse the list, reverse (quickSort dictionary)
gives us what we want.
But wait! We didn't really sort in the descending order, we sorted (in the ascending order) and reversed it. They may have the same effect, but they are not the same thing!
Besides, you might object that the list you got isn't what you wanted. "a" should certainly be placed before "I". "Linux" should be placed between "have" and "thing". What's the problem here?
The problem is, the way String
s are represented in a typical programming settings is by a list of Unicode characters. Unicode (and almost all other encodings of characters) specifies that the character code for capital letters are less than the small letters. Bummer. So "Z" is less than "a". We should do something about it. Looks like we need a case insensitive quickSort
as well. It might come handy some day.
But, there's no way you can blend that into quickSort
as it stands. We have work to do.
Tweaking What We Already Have[edit]
What we need to do is to factor out the comparisons quickSort
makes. We need to provide quickSort
with a function that compares two elements, and gives an Ordering
, and as you can imagine, an Ordering
is any of LT, EQ, GT
.
To sort in the descending order, we supply quickSort
with a function that returns the opposite of the usual Ordering
. For the caseinsensitive sort, we may need to define the function ourselves. By all means, we want to make quickSort
applicable to all such functions so that we don't end up writing it over and over again, each time with only minor changes.
quickSort
, Take Two[edit]
Our quickSort
will take two things this time: first, the comparison function, and second, the list to sort.
A comparison function will be a function that takes two things, say, x
and y
, and compares them. If x
is less than y
(according to the criteria we want to implement by this function), then the value will be LT
. If they are equal (well, equal with respect to the comparison, we want "Linux" and "linux" to be equal when we are dealing with the insensitive case), we will have EQ
. The remaining case gives us GT
(pronounced: greater than, for obvious reasons).
 no matter how we compare two things  the first two equations should not change  they need to accept the comparison function though  but the result doesn't need it quickSort _ [] = [] quickSort _ [x] = [x]  we are in a more general setting now  but the changes are worth it!  c is the comparison function quickSort c (x : xs) = (quickSort c less) ++ (x : equal) ++ (quickSort c more) where less = filter (\y > y `c` x == LT) xs equal = filter (\y > y `c` x == EQ) xs more = filter (\y > y `c` x == GT) xs
Cool!
Note
Almost all the basic data types in Haskell are members of the Ord
class. This class defines an ordering, the "natural" one. The functions (or, operators, in this case) (<)
, (==)
or (>)
provide shortcuts to the compare
function each type defines. When we want to use the natural ordering as defined by the types themselves, the above code can be written using those operators, as we did last time. In fact, that makes for much clearer style; however, we wrote it the long way just to make the relationship between sorting and comparing more evident.
But What Did We Gain?[edit]
Reuse. We can reuse quickSort
to serve different purposes.
 the usual ordering  uses the compare function from the Ord class usual = compare  the descending ordering, note we flip the order of the arguments to compare descending x y = compare y x  the caseinsensitive version is left as an exercise! insensitive = ...  can you think of anything without making a very big list of all possible cases?
And we are done!
quickSort usual dictionary
should, then, give
["I", "Linux", "a", "for", "have", "thing"]
The comparison is just compare
from the Ord
class. This was our quickSort
, before the tweaking.
quickSort descending dictionary
now gives
["thing", "have", "for", "a", "Linux", "I"]
And finally,
quickSort insensitive dictionary
gives
["a", "for", "have", "I", "Linux", "thing"]
Exactly what we wanted!
Exercises 

Write insensitive , such that quickSort insensitive dictionary gives ["a", "for", "have", "I", "Linux", "thing"] . 
HigherOrder Functions and Types[edit]
Our quickSort
has type (a > a > Ordering) > [a] > [a]
.
Most of the time, the type of a higherorder function provides a good guideline about how to use it. A straightforward way of reading the type signature would be, "quickSort
takes a function that gives an ordering of a
s, and a list of a
s, to give a list of a
s". It is then natural to guess that the function sorts the list respecting the given ordering function.
Note that the parentheses surrounding a > a > Ordering
is mandatory. It says that a > a > Ordering
altogether form a single argument, an argument that happens to be a function. What happens if we omit the parentheses? We would get a function of type a > a > Ordering > [a] > [a]
, which accepts four arguments instead of the desired two (a > a > Ordering
and [a]
). Furthermore none of the four arguments, neither a
nor Ordering
nor [a]
are functions, so omitting the parentheses would give us something that isn't a higher order function.
Furthermore, it's worth noting that the >
operator is rightassociative, which means that a > a > Ordering > [a] > [a]
means the same thing as a > (a > (Ordering > ([a] > [a])))
. We really must insist that the a > a > Ordering
be clumped together by writing those parentheses... but wait... if >
is rightassociative, wouldn't that mean that the correct signature (a > a > Ordering) > [a] > [a]
actually means... (a > a > Ordering) > ([a] > [a])
?
Is that really what we want?
If you think about it, we're trying to build a function that takes two arguments, a function and a list, returning a list. Instead, what this type signature is telling us is that our function takes one argument (a function) and returns another function. That is profoundly odd... but if you're lucky, it might also strike you as being profoundly beautiful. Functions in multiple arguments are fundamentally the same thing as functions that take one argument and give another function back. It's OK if you're not entirely convinced. We'll go into a little bit more detail below and then show how something like this can be turned to our advantage.
Exercises 

The following exercise combines what you have learned about higher order functions, recursion and IO. We are going to recreate what programmers from more popular languages call a "for loop". Implement a function for :: a > (a>Bool) > (a>a) > (a> IO ()) > IO () for i p f job =  ??? An example of how this function would be used might be for 1 (<10) (+1) (print) which prints the numbers 1 to 9 on the screen. Starting from an initial value
Some more challenging exercises you could try

Currying[edit]
I hope you followed the reasoning of the preceding chapter closely enough. If you haven't, you should, so give it another try.
Currying is a technique^{[1]} that lets you partially apply a multiparameter function. When you do that, it remembers those given values, and waits for the remaining parameters.
Our quickSort
takes two parameters, the comparison function, and the list. We can, by currying, construct variations of quickSort
with a given comparison function. The variation just "remembers" the specific comparison, so you can apply it to the list, and it will sort the list using that comparison function.
descendingSort = quickSort descending
What is the type of descendingSort? quickSort
was (a > a > Ordering) > [a] > [a]
, and the comparison function descending
was a > a > Ordering
. Applying quickSort
to descending
(that is, applying it partially, we haven't specified the list in the definition) we get a function (our descendingSort
) for which the first parameter is already given, so you can scratch that type out from the type of quickSort
, and we are left with a simple [a] > [a]
. So we can apply this one to a list right away!
Note: This will not work in newer compilers without either applying a pragma or adding a definition: descendingSort :: Ord a => [a] > [a]
descendingSort dictionary
gives us
["thing", "have", "for", "a", "Linux", "I"]
It's rather neat. But is it useful? You bet it is. It is particularly useful as sections, you might notice. Currying often makes Haskell programs very concise. More than that, it often makes your intentions a lot clearer. Remember
less = filter (< x) xs
from the first version of quickSort
? You can read it aloud like "keep those in xs
that are less than x
". Although (< x)
is just a shorthand for (\y > y < x)
, try reading that aloud!
Function manipulation[edit]
We will close the chapter discussing a few examples of very common and very useful generalpurpose higherorder functions, beginning with flip
. flip
is a handy little Prelude function that has the following type:
flip :: (a > b > c) > b > a > c
It takes a function of two arguments and returns a version of the same function with the arguments swapped, so that:
Prelude> (flip (/)) 3 1 0.3333333333333333 Prelude> (flip map) [1,2,3] (*2) [2,4,6]
We could have used flip to write the descending
comparing function from the quickSort example pointfree, as simply:
descending = flip compare
flip
is particularly useful when we want to pass a function with two arguments of different types to another function and the arguments are in the wrong order with respect to the signature of the higherorder function.
The (.)
composition operator is, as should be clear by now, just another higherorder function. It has the signature:
(.) :: (b > c) > (a > b) > a > c
(.)
takes two functions as argument and returns a new function, which applies the second argument and then the first.
Composition and higherorder functions provide a range of powerful tricks. For a very small sample of that, first consider the inits
function, defined in the module Data.List
. Quoting the documentation, it "returns all initial segments of the argument, shortest first", so that:
Prelude Data.List> inits [1,2,3] [[],[1],[1,2],[1,2,3]]
With the higher order functions flip
, scanl
, (.)
and map
we can, using only functions in Prelude, provide the following one line implementation for inits
(written pointfree for extra dramatic effect):
myInits :: [a] > [[a]] myInits = map reverse . scanl (flip (:)) []
Swallowing a definition so condensed may look daunting at first; so slowly analyse it bit by bit, recalling what each function does and using the type signatures as a guide.
Note that the definition of myInits
is not only very concise but also clean, in particular with parentheses usage kept to a bare minimum. Naturally, if one goes overboard with composition by writing milelong (.)
chains things are bound to get confusing, but when deployed reasonably this is a very attractive style. Furthermore, the implementation is quite "high level": we do not deal explicitly at all with details like pattern matching or recursion; the functions we deployed  both the higherorder ones and their functional arguments  take care of such plumbing.
Finally, we will present a very curious higherorder operator, ($)
. Its type is:
($) :: (a > b) > a > b
It takes a function as its first argument, and all it does is to apply the function to the second argument, so that, for instance, (head $ "abc") == (head "abc")
.
By now, it would be entirely justified if you thought that ($)
was completely useless! However, there are two interesting points about it. First, ($)
has very low precedence^{[2]}, unlike regular function application which has very high precedence. In effect, that means we can write a nonpointfree version of myInits
without having to add any parentheses in spite of the intricate expression at the left of the argument:
myInits :: [a] > [[a]] myInits xs = map reverse . scanl (flip (:)) [] $ xs
Furthermore, as ($)
is just a function which happens to apply functions, and functions are just values, we can write intriguing expressions such as:
map ($ 2) [(2*), (4*), (8*)]
(Yes, that is a list of functions, and it is perfectly legal.)
Function manipulation through higherorder gives us a great deal of power. As we continue throughout this book we will see many examples of such power being harnessed.
Notes[edit]
 ↑ named after the outstanding logician Haskell Brooks Curry, the same guy after whom the language is named.
 ↑ Precedence here is meant in the sense that
+
has lower precedence than*
, and therefore2 + 3 * 4
equals 14 and not 20.