The Haskell School of Expression Learning Functional Programming through Multimedia

All of the types considered thus far have been first order. For example, the type constructor Tree has always been paired with an argument, as in Tree Int (a tree containing Int values) or Tree a (representing the family of trees containing a values). But Tree by itself is a type constructor: something that takes a type as an argument and returns a type as a result. There are no values in Haskell that have this type, but such “higher-order” types can be used in class declarations in useful ways, as we shall see in this chapter.

The Functor Class

To begin, consider the following Functor class defined in the Standard Prelude:

There is something new here. The type variable f is applied to other types, as in f a and f b. Thus, we would expect f to be a type such as Tree, which can be applied to an argument. Indeed, a suitable instance of Functor for type Tree would be:

Recall that in Section 7.2 we defined a function mapTree that behaved just as the above fmap method, so we could have instead written:

Such an instance declaration declares that Tree, rather than Tree a, is an instance of Functor.

Note that in Haskell we write Tree Int for trees of integers, and we say that Tree is a type constructor. And we write [Int] for lists of integers. However, what is the type constructor for lists? Because of Haskell's special syntax for the list data type, there is also a special syntax for its type constructor, namely [].