Higher-Order Functions

One of the most important concepts in programming is the notion of abstraction. Abstraction is the ability to reuse a common code pattern without having to repeat its details and by referring to it by name. Functions themselves are a fundamental form of abstraction. For instance, in the expressions 1+2 and 1+40, the common part is (1+). We can abstract over this common pattern by defining a function:

inc :: Integer -> Integer
inc n = 1 + n

In this chapter, we go one step further by abstracting over these abstractions. Indeed, we allow functions to have other functions as parameters. Such functions are called HOF (HOFs). A HOF represents a whole family of different functions that have the same overall structure but differ in some of the details. Arguably, support for HOFs is one of the defining features of the functional programming paradigm. The typical concise nature of functional programs is often due to the judicious composition of HOFs, and a programmer...

Abstracting over functions

This section introduces HOF as a way to share code between similar functions. We will investigate two small case studies – dropping a prefix from a list or string and sorting a list.

Dropping a prefix

A frequent data-cleaning task is to drop the leading spaces from a string. This is accomplished by the following function:

dropSpaces :: String -> String
dropSpaces []     = []
dropSpaces (c:cs)
  | c == ' '      = dropSpaces cs
  | otherwise     = c:cs

Recall that strings are just lists of characters. This function uses that fact to perform primitive recursion over the string. It does the job as required:

*Main> dropSpaces "   hello"
"hello"

This is usually not enough though, as we also want to drop other so-called whitespace characters such as tab and newline. The isSpace :: Char ->...

An abstraction for structural recursion

In the previous chapter, we studied recursive functions and presented structural recursion schemes as a useful template to write such functions. Thanks to HOF, we can capture these structural recursion schemes in reusable functions.

Folding lists

The first structural recursion scheme we encountered in the previous chapter is that for lists:

f :: [A] -> B
f []     = n
f (x:xs) = c x (f xs)

By replacing the underlined elements in the preceding template with concrete names, we obtain different functions, such as sum and and:

Prelude
sum :: [Integer] -> Integer
sum []     = 0
sum (x:xs) = x + sum xs
and :: [Bool] -> Bool
and []     = True
and (x:xs) = x && and xs

Thanks to the ability to parameterize over functions, we can actually do better than this. Indeed, we can capture the recursion scheme in a HOF called foldr:

Prelude
foldr :: (a...

Common HOFs

Besides foldr and dropWhile, Haskell’s standard library contains a number of useful and frequently used HOF.

Taking instead of dropping

The dropWhile function has an opposite that takes rather than drops elements from the front of a list:

Prelude
takeWhile :: (a -> Bool) -> [a] -> [a]
    takeWhile p []     = []
    takeWhile p (x:xs)
       | p x            = x : takeWhile p xs
       | otherwise      = []

As long as the elements satisfy the predicate, they are returned. Yet, as soon as a first element is found that does not satisfy the predicate, no more elements are returned.

For example, by passing isDigit from the Data.Char module to takeWhile, we can take the leading digits of a string:

*Main> takeWhile isDigit...

Writing compact code with HOF

Thanks to their function parameters, the behavior of HOF can be customized more extensively than that of similar first-order functions. This means they can be used in more circumstances. That is particularly true for the HOF of the previous sections because they cover highly general code patterns. In this section, we will show how some problems can be quickly and compactly solved by combining a number of HOF.

Standard deviation

The standard deviation of a list of numbers is a well-known statistical value that characterizes the amount of variation among those numbers. It is defined in terms of the average of those numbers. Let us first work out how to implement this average and then move on to the actual standard deviation.

Average

This average can easily be computed using predefined first-order functions:

average :: [Float] -> Float
average l = sum l / fromIntegral (length l)

Both sum and length are predefined functions that are themselves...

Summary

This chapter introduced HOF. We saw how we can generalize existing code by abstracting over function parameters and then reuse this generalization more widely. Next, we studied how this mechanism can be used to capture structural recursion in a reusable HOF. Then, we reviewed a range of commonly used predefined HOF and combined them to concisely solve tasks.

In Chapter 5, First-Class Functions, we will see how Haskell strongly encourages the use of HOFs with a range of language features that facilitate their use. In particular, they make it easy to write function parameters for HOFs and, more generally, write programs mostly in terms of functions, rather than in terms of the values they process.

Questions

1. How do you generalize functions by abstracting over function parameters?
2. How do you capture structural recursion as a HOF?
3. What are common predefined HOF?
4. How do we solve problems by composing HOF?

Answers

1. You can make a function more general by replacing one of the (other) functions it calls with a parameter. The type of this function parameter will be the same as the type of the function abstracted over. Further generality is often possible at this point by generalizing the types by means of parametric polymorphism.
2. The foldr function captures the structural recursion scheme for lists:

   foldr :: (a -> b -> b) -> b -> [a] -> b
   foldr c n []     = n
   foldr c n (x:xs) = c x (foldr c n xs)

   The n parameter abstracts over the result for the base constructor, [], and the c function parameter for the recursive constructor, (:). Similar fold functions can be written for other algebraic datatypes.

3. Notable predefined HOF are as follows:
   • map :: (a -> b) -> [a] -> [b]
   • filter :: (a -> Bool) -> [a] -> [a]
   • any :: (a -> Bool) -> [a] -> Bool
   • all :: (a -> Bool) -> [a] -> Bool
   • takeWhile :: (a -> Bool) -> [a] -...