Higher order functions
length function that finds the length of a list. Below is a recursive definition.
The type signature tells us that
length is a function that accepts a list of an arbitrary type
a, and returns an
(x:xs) term binds
x to the head of the list and
xs to the tail.
This works by pattern matching on the type constructor
(:). If we had recursively defined our list as
then the same length function would be written as follows.
Abstracting to map
Suppose we’re writing a function that doubles every element in a list of
Ints. We might write the following.
We can easily generalize this, for example to a function that multiplies every element in a list of
Ints by \(m\).
Here, the naive reading of the type signature is as a function from an
Int and a
[Int] to a
[Int]. However, since the
-> operator is right associative, we can read the type signature as
multiplyList takes an
Int and returns a function from
[Int]. In particular, note that we can recover
doubleList by passing one argument to
multiplyList. The following code gives us a function equivalent to the original.
Functions in Haskell are “first-class citizens,” and behave exactly like any other value. As we’ve seen, functions can return other functions. Similarly, functions can accept other functions as arguments. To generalize
multiplyList further, we can write
applyToInts accepts a function from integers to integers, with type signature
Int -> Int, and returns a function that applies that function to each element in a list.
We can further generalize
applyToIntegers. While its type signature is
(Int -> Int) -> [Int] -> [Int], the definition is not integer specific. We can make a polymorphic version with the type signature
(a -> b) -> [a] -> [b]. This function is called
map, which you might be familiar with.
The filter function
map, Haskell contains numerous other higher-order functions for list operations. As in other languages,
filter is a function that takes a predicate and a list, and returns the list of elements that satisfy the predicate.
Looking at the type signature, we can see that the predicate, which is the first argument, has type
(a -> Bool) where
a is the type of the list elements.
Here are some examples.
map, we can define more specific functions using filter. For example, the following function
justEvens takes a list of type
[Int] and returns a list of its even elements.