# 3.11 Higher-Order Computations

The arguments of a function can be functions themselves. This feature is banned or restricted by many programming languages. E.g., in C only a pointer to a function can be passed as a parameter to another function.

A function that takes an argument of function type is referred to as a higher-order function. Loosely speaking, a higher-order function is computation parameterized by another computation. We show the power of this feature with a simple example. The function “sort”, shown below, takes a list of numbers and sorts them in ascending order. On non-empty arguments, the function “sort” recursively sorts the tail and inserts the head at the right place in the sorted tail. This algorithm becomes inefficient as lists grow longer, but it is easy to understand [Browse Program][Download Program]:

sort []     = []
sort (x:xs) = insert x (sort xs)
insert x [] = [x]
insert x (y:ys) | x <= y    = x : y : ys
| otherwise = y : insert x ys

To sort a list in descending order or to sort a list of a different type, a new function must be coded.

An alternative is to code a sort function where the ordering criterion is an argument. The overall structure of the function is the same. The new argument, the first one of each function, is denoted by “f”. This argument is a function that takes two arguments and returns “True” if and only if the first argument must appear before the second argument in the output list [Browse Program][Download Program]:

sort _ []     = []
sort f (x:xs) = insert f x (sort f xs)
insert _ x [] = [x]
insert f x (y:ys) | f x y     = x : y : ys
| otherwise = y : insert f x ys

For example:

HOInsertionSort> sort (<=) [3,5,1,2,6,8,9,7]
[1,2,3,5,6,7,8,9]
HOInsertionSort> sort (>) [3,5,1,2,6,8,9,7]
[9,8,7,6,5,3,2,1]

In the above expressions, the operators “<=” and “>” are the functional arguments. The parentheses around them are necessary, since these functions are identified by infix operators. Without parentheses, the expression “sort <= [3,5,1,2,6,8,9,7]” would test whether the left argument of “<=” is smaller than the right argument, which is meaningless.

Observe that the first version of the “sort” function constrains the elements of the input list to be numbers, since these elements are arguments of “<=”. In the second, higher-order version, the type of the elements of the input list is unconstrained. Thus, the function can be applied to lists of any type as long as a suitable ordering criterion for the type of the list elements is provided.

Higher-order computations involve a functional argument. Sometimes, the corresponding argument in a call, which is a function, is referenced only in the call itself. In this case, it is appropriate to use an anonymous function. For example, suppose that an elementary school information system represents classes with a grade and a section. The grade is a number in the range 1 through 5 and the section is a letter, a, b … The following ordering criterion sorts the classes in a “natural” (lexicographic) order [Browse Program][Download Program]:

sortClasses xs = sort lex xs
where lex (x,y) (u,v) = x<u || x==u && ord y <= ord v

A more compact and informative formulation uses an anonymous function as follows [Browse Program][Download Program]:

sortClasses xs = sort (\(x,y) (u,v) -> x<u || x==u && ord y <= ord v) xs

Observe that pattern matching is normally used in the definition of the above anonymous function.