In this chapter I will introduce two new important ideas. The first is poly-morphism, the ability to consider entire families of types as one. Polymorphic data types are one source of this concept, which is then inherited by functions defined over these data types. The already familiar list is the most common example of a polymorphic data type, and it will be discussed at length in this chapter.
The second concept is the higher-order function, which is a function that can take one or more functions as arguments or return a function as a result (functions can also be placed in data structures, making the data constructors higher-order too). Together, polymorphic and higherorder functions substantially increase our expressive power and our ability to reuse code. You will see that both of these new ideas naturally follow the foundations that we have already built. (A more detailed discussion of polymorphic functions that operate on lists can be found in Chapter 23.)
Polymorphic Types
In previous chapters we have seen examples of lists of many different kinds of elements integers, floating-point numbers, points, characters, and even 10 actions. You can well imagine situations requiring lists of other element types as well. Sometimes, however, we don't wish to be so particular about the precise type of the elements. For example, suppose we want to define a function length, which determines the number of elements in a list. We don't really care whether the list contains integers, characters, or even other lists. We imagine computing the length in exactly the same way in each case. The obvious definition is:
length [ ] = 0
length (x: xs) = 1 + length xs
This definition is self-explanatory. We can read the equations as saying: “The length of the empty list is 0, and the length of a list whose first element is x and remainder is xs, is 1 plus the length of x.s”
But what should the type of length be? Intuitively, what we'd like to say is that, for any type a, the type of length is [a] → Integer.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.