First-Class Functions

In the previous chapter, we studied higher-order functions (HOFs), one of the defining features of functional programming. This chapter explains how Haskell actively supports working with HOFs by providing a number of facilitating language features.

The ability of HOFs to abstract over functions means that they are more reusable than first-order functions. Indeed, often tasks can be concisely handled by assembling a number of predefined higher-order functions. Of course, HOFs are useless without the functions that we supply to them as parameters. Hence, part of the effectiveness of HOFs stems from being able to quickly and concisely supply the right function parameters to instantiate the HOFs.

In the previous chapter, we often did not have the right function at hand to supply as a parameter. Instead, we wrote a dedicated new function, often in the form of a local definition, to make up for this lack. Recall, for example, the isSpaceCharacter function that...

Anonymous functions

The first feature we will study to facilitate writing custom functions, usually as parameters for HOFs, are anonymous functions. These are also called lambda functions or lambda abstractions after their origin in the lambda calculus.

We will illustrate the concept of an anonymous function using the dropSpaces example from this chapter’s introduction. The local definition of its isSpaceCharacter function takes up two additional lines (or one if we omit the optional type signature). Moreover, it has to be given a name, which, while useful for documentation purposes, takes some effort. This effort has very little benefit, as the function is only called once, right where it is defined. Hence, the effort cannot be amortized over multiple call sites.

Anonymous function syntax

An anonymous function is a function that is not given a name. Hence, when referring to such a nameless function, we have to supply its definition instead. The nameless version of...

Currying and partial application

The second feature that aids in creating new functions as parameters to HOFs is currying. Currying is named after Haskell B. Curry, the logician after whom the Haskell language is named, even though Curry attributed the concept of currying to the logician Moses Schönfinkel; in fact, the first known application predates both and is credited to a third logician, Gottlob Frege. It is based on an idea that greatly simplifies the design and mechanics of a functional programming language, possibly requiring a revision of your current mental model of Haskell. The idea is that functions need not have more than one parameter. Whenever we want to write a multi-parameter function, we can simulate it instead by means of single-parameter functions. This idea features in the lambda calculus, as it serves its minimality objective. As we will now see, Haskell too has currying built in.

One parameter is enough

Let us revisit the very first two-parameter function...

Eta reduction

The third feature that Haskell has borrowed from the lambda calculus is eta reduction. Eta reduction is named after the Greek letter eta, written as η. It allows us to shorten function definitions of a particular form. Its inverse is known as eta expansion, and collectively, they are known as eta conversion.

Basic eta reduction

We will illustrate the idea using a basic anonymous function:

\x -> sin x

This function takes a parameter, x, and computes its sine by calling the sin function on it. The observation that eta reduction makes is that this anonymous function behaves in exactly the same way as the sin function itself; both functions produce the same output given the same input. In other words, this anonymous function is indistinguishable from sin and, therefore, equal to it. For example, consider the following:

map (\x -> sin x) [1.0, 2.0, 3.0]

We can rewrite that as the following:

map sin [1.0, 2.0, 3.0]

This idea also works at the...

Function composition

Function composition is a well-known operator from mathematics, written as ∘, that combines two functions into a new one.

Basic function composition

Consider the following anonymous function:

\l -> show (length l)

This function returns the length of a list rendered as a string. It is not in the right shape to apply eta reduction to because, in its current form, we cannot identify one function that is applied to l.

The function composition operator captures this particular pattern in a general way:

Prelude
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

This higher-order operator takes two functions and returns a new function that applies the first to the output of the second. We can use this to replace our preceding example with the following:

show . length

This can be read as "show composed with length" or, better, "show after length".

Pipelines

The function composition...

Functions as data structures

In this last section, we will aim to further shift our perspective away from functions as a mechanism to perform computations on functions as data, or, more specifically, on functions as data structures.

Evaluation with many variables

In Chapter 3, Recursion, we looked at an interpreter for a small expression language that features one variable. Let us generalize this now to expressions that can contain many different variables:

data Expr = Var String | Lit Int | Add Expr Expr

This data type has a constructor, Var, to denote a variable expression. The constructor’s String field identifies which of the possibly many variables is referenced. For example, the expression x + (y + 3) would be written as follows:

expr :: Expr
expr = Add (Var "x") (Add (Var "y") (Lit 3))

When evaluating an expression like this, we need to know what values the "x" and "y" variables take. This was easy in Chapter 3,...

Summary

This chapter introduced a number of language features that facilitate the creation of new functions out of existing ones, which is particularly useful when working with higher-order functions. Three of these features originate in the lambda calculus – anonymous functions, currying, and eta reduction. The fourth feature, function composition, is a common operator used in mathematics. Function composition and eta reduction both promote the point-free programming style that focuses on functions, rather than on the values they process. Finally, to illustrate the first-class nature of functions, we saw how they can be used to represent data structures.

In Chapter 6, Type Classes, we will learn about Haskell’s mechanism for overloading functions called type classes. While we expect that predefined operators such as (+) and (<) work for different built-in types, type classes also allow us to define these operators for our own algebraic data types. Moreover, with...

Questions

1. What are anonymous functions?
2. What is currying?
3. What is eta reduction?
4. What is function composition?
5. What are first-class functions?

Answers

1. Anonymous functions are functions that are not given by name but by their definition. They are used where an expression is expected – for example, as a parameter to a HOF. Syntactically, they take the form \x1 … x2n -> e, where x1,...,xn are the function parameters and e is the function body.
2. Currying is the technique of encoding a multi-parameter function in terms of single-parameter functions. In Haskell, all functions are curried. For example, the \x y -> x + y function is encoded as \x -> (\y -> x + y). Currying allows partial application – a multi-parameter function is not applied to all of its parameters. The result is a function that expects the remaining parameters. For example, map not is a partial application of map; it is a function that turns a list of Booleans into a list of the negation of them.
3. Eta reduction is the simplification of a function of the form (\x -> f x) to just f. The idea is that both functions are...