At the heart of functional programming is the idea that functions arejust like any other value. The power of functional style comes from handling functions themselves as regular values, i.e. by passing functions to other functions and returning them from functions. A function that takes another function (or several functions) as an argument is called ahigher-order function. They can be found pretty much anywhere in a Haskell program, and indeed we have already met some of them, such asmap and the various folds. We saw commonplace examples of higher-order functions when discussingmap inLists II. Now, we are going to explore some common ways of writing code that manipulates functions.

For a concrete example, we will consider the task of sorting a list.Quicksort is a well-known recursive sorting algorithm. To apply its sorting strategy to a list, we first choose one element and then divide the rest of the list into (A) those elements that should go before the chosen element, (B) those elements equal to the chosen one, and (C) those that should go after. Then, we apply the same algorithm to the unsorted (A) and (C) lists. After enough recursive sorting, we concatenate everything back together and have a final sorted list. That strategy can be translated into a Haskell implementation in a very simple way.

-- Type signature: any list with elements in the Ord class can be sorted.quickSort::(Orda)=>[a]->[a]-- Base case:-- If the list is empty, there is nothing to do.quickSort[]=[]-- The recursive case:-- We pick the first element as our "pivot", the rest is to be sorted.-- Note how the pivot itself ends up included in the middle part.quickSort(x:xs)=(quickSortless)++(x:equal)++(quickSortmore)whereless=filter(<x)xsequal=filter(==x)xsmore=filter(>x)xs

It should be pointed out that ourquickSort is rather naïve. A more efficient implementation would avoid the three passes throughfilter at each recursive step and not use(++) to build the sorted list. Furthermore, unlike our implementation, theoriginal quicksort algorithm does the sorting in-place using mutability.^[1] We will ignore such concerns for now, as we are more interested in the usage patterns of sorting functions, rather than in exact implementation.

Almost all the basic data types in Haskell are members of theOrd class, which is for ordering tests whatEq is for equality tests. TheOrd class defines which ordering is the "natural" one for a given type. It provides a function calledcompare, with type:

compare::(Orda)=>a->a->Ordering

compare takes two values and compares them, returning anOrdering value, which isLT if the first value isless than the second,EQ if it isequal andGT if it isgreater than. For anOrd type,(<),(==) fromEq and(>) can be seen as shortcuts tocompare that check for one of the three possibilities and return aBool to indicate whether the specified ordering is true according to theOrd specification for that type. Note that each of the tests we use withfilter in the definition ofquickSort corresponds to one of the possible results ofcompare, and so we might have written, for instance,less asless = filter (\y -> y `compare` x == LT) xs.

WithquickSort, sorting any list with elements in theOrd class is easy. Suppose we have a list ofString and we want to sort them; we just applyquickSort to the list. For the rest of this chapter, we will use a pseudo-dictionary of just a few words (but dictionaries with thousands of words would work just as well):

dictionary=["I","have","a","thing","for","Linux"]

quickSort dictionary returns:

["I","Linux","a","for","have","thing"]

As you can see, capitalization is considered for sorting by default. HaskellStrings are lists of Unicode characters. Unicode (and almost all other encodings of characters) specifies that the character code for capital letters are less than the lower case letters. So "Z" is less than "a".

To get a proper dictionary-like sorting, we need a case insensitivequickSort. To achieve that, we can take a hint from the discussion ofcompare just above. The recursive case ofquickSort can be rewritten as:

quickSortcompare(x:xs)=(quickSortcompareless)++(x:equal)++(quickSortcomparemore)whereless=filter(\y->y`compare`x==LT)xsequal=filter(\y->y`compare`x==EQ)xsmore=filter(\y->y`compare`x==GT)xs

While this version is less tidy than the original one, it makes it obvious that the ordering of the elements hinges entirely on thecompare function. That means we only need to replacecompare with an(Ord a) => a -> a -> Ordering function of our choice. Therefore, our updatedquickSort' is a higher-order function which takes a comparison function along with the list to sort.

quickSort'::(Orda)=>(a->a->Ordering)->[a]->[a]-- No matter how we compare two things the base case doesn't change,-- so we use the _ "wildcard" to ignore the comparison function.quickSort'_[]=[]-- c is our comparison functionquickSort'c(x:xs)=(quickSort'cless)++(x:equal)++(quickSort'cmore)whereless=filter(\y->y`c`x==LT)xsequal=filter(\y->y`c`x==EQ)xsmore=filter(\y->y`c`x==GT)xs

We can reuse ourquickSort' function to serve many different purposes.

If we wanted adescending order, we could just reverse our original sorted list withreverse (quickSort dictionary). Yet to actually do the initial sort descending, we could supplyquickSort' with a comparison function that returns the opposite of the usualOrdering.

-- the usual ordering uses the compare function from the Ord classusual=compare-- the descending ordering, note we flip the order of the arguments to comparedescendingxy=compareyx-- the case-insensitive version is left as an exercise!insensitive=...-- How can we do case-insensitive comparisons without making a big list of all possible cases?

A reader requests clarification of this page's material to reduce confusion. You can helpclarify material,request assistance, or viewcurrent progress.

The concept ofcurrying (the generating of intermediate functions on the way toward a final result) was first introduced in the earlier chapter "Lists II". This is a good place to revisit how currying works.

OurquickSort' has type(a -> a -> Ordering) -> [a] -> [a].

Most of the time, the type of a higher-order function provides a guideline about how to use it. A straightforward way of reading the type signature would be "quickSort' takes, as its first argument, a function that gives an ordering of twoas. Its second argument is a list ofas. Finally, it returns a new list ofas". This is enough to correctly guess that it uses the given ordering function to sort the list.

Note that the parentheses surroundinga -> a -> Ordering are mandatory. They specify thata -> a -> Ordering forms a single argument that happens to be a function.

Without the parentheses, we would geta -> a -> Ordering -> [a] -> [a] which accepts four arguments (none of which are themselves functions) instead of the desired two, and that wouldn't work as desired.

Remember that the-> operator is right-associative. Thus, our erroneous type signaturea -> a -> Ordering -> [a] -> [a] means the same thing asa -> (a -> (Ordering -> ([a] -> [a]))).

Given that-> is right-associative, the explicitly grouped version of the correctquickSort' signature is actually(a -> a -> Ordering) -> ([a] -> [a]). This makes perfect sense. Our originalquickSort lacking the adjustable comparison function argument was of type[a] -> [a]. It took a list and sorted it. Our newquickSort' is simply a function that generatesquickSort style functions! If we plug incompare for the(a -> a -> Ordering) part, then we just return our original simplequickSort function. If we use a different comparison function for the argument, we generate adifferent variety of aquickSort function.

Of course, if we not only give a comparison function as an argument but also feed in an actual list to sort, then the final result is not the newquickSort-style function; instead, it continues on and passes the list to the new function and returns the sorted list as our final result.

for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()for i p f job = -- ???

for 1 (<10) (+1) print

We will close the chapter by discussing a few examples of common and useful general-purpose higher-order functions. Familiarity with these will greatly enhance your skill at both writing and reading Haskell code.

flip is a handy little Prelude function. It takes a function of two arguments and returns a version of the same function with the arguments swapped.

flip::(a->b->c)->b->a->c

flip in use:

Prelude> (flip (/)) 3 10.3333333333333333Prelude> (flip map) [1,2,3] (*2)[2,4,6]

We could have used flip to write a point-free version of thedescending comparing function from the quickSort example:

descending=flipcompare

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 higher-order function.

The(.) composition operator is another higher-order function. It has the signature:

(.)::(b->c)->(a->b)->a->c

(.) takes two functions as arguments and returns a new function which applies the second function to the argument and then the first. (Writing the type of(.) as(b -> c) -> (a -> b) -> (a -> c) can make that easier to see.)

Composition and higher-order functions provide a range of powerful tricks. For a tiny sample, first consider theinits function, defined in the moduleData.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]]

We can provide a one-line implementation forinits (written point-free for extra dramatic effect) using only the following higher-order functions from Prelude:flip,scanl,(.) andmap:

myInits::[a]->[[a]]myInits=mapreverse.scanl(flip(:))[]

Swallowing a definition so condensed may look daunting at first, so analyze it slowly, bit by bit, recalling what each function does and using the type signatures as a guide.

The definition ofmyInits is super concise and clean with use of parentheses kept to a bare minimum. Naturally, if one goes overboard with composition by writing mile-long(.) chains, things will get confusing; but, when deployed reasonably, these point-free styles shine. Furthermore, the implementation is quite "high level": we do not deal explicitly with details like pattern matching or recursion; the functions we deployed — both the higher-order ones and their functional arguments — take care of such plumbing.

($) is a curious higher-order operator. Its type is:

($)::(a->b)->a->b

It takes a function as its first argument, andall it does is to apply the function to the second argument, so that, for instance,(head $ "abc") == (head "abc").

You might think that($) is completely useless! However, there are two interesting points about it. First,($) has very low precedence,^[2] unlike regular function application which has the highest precedence. In effect, that means we can avoid confusing nesting of parentheses by breaking precedence with$. We write a non-point-free version ofmyInits without adding new parentheses:

myInits::[a]->[[a]]myInitsxs=mapreverse.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.)

As the name suggests,uncurry is a function that undoes currying; that is, it converts a function of two arguments into a function that takes a pair as its only argument.

uncurry::(a->b->c)->(a,b)->c

Prelude> let addPair = uncurry (+)Prelude> addPair (2, 3)5

One interesting use ofuncurry occasionally seen in the wild is in combination with($), so that the first element of a pair is applied to the second.

Prelude> uncurry ($) (reverse, "stressed")"desserts"

There is alsocurry, which is the opposite ofuncurry.

curry::((a,b)->c)->a->b->c

Prelude> curry addPair 2 3 -- addPair as in the earlier example.5

Because most Haskell functions are already curried,curry is nowhere near as common asuncurry.

Finally, we should mention two functions which, while not higher-order functions themselves, are most often used as arguments to higher-order functions.id, theidentity function, is a function with typea -> a that returns its argument unchanged.

Prelude> id "Hello""Hello"

Similar in spirit toid,const is ana -> b -> a function that works like this:

Prelude> const "Hello" "world""Hello"

const takes two arguments, discards the second and returns the first. Seen as a function of one argument,a -> (b -> a), it returns a constant function, which always returns the same value no matter what argument it is given.

id andconst might appear worthless at first. However, when dealing with higher-order functions it is sometimes necessary to pass a dummy function, be it one that does nothing with its argument or one that always returns the same value.id andconst give us convenient dummy functions for such cases.

1. ↑The "true", in-place quicksortcan be done in Haskell, but it requires some rather advanced tools that we will not discuss in the Beginners' Track.
2. ↑As a reminder, precedence here is meant in the same sense that* has higher precedence (i.e. is evaluated first) than+ in mathematics.

• Book:Haskell

• Pages needing clarification