Functors

Exercise 1.

You may recall the function map, which applies a function to each element of a list:

map :: (a -> b) -> [a] -> [b]

write a similar function mapMaybe that uses a provided function to transform the contents, if any, of a Maybe a.
Don't forget to give it a type signature!

suggested solution:

mapMaybe f Nothing = Nothing
mapMaybe f (Just x)

(Slide)

If you wrote out the type signature for mapMaybe, you'll notice that it's quite similar to the type of map

map      :: (a -> b) -> [a]     -> [b]
mapMaybe :: (a -> b) -> Maybe a -> Maybe b

Both of these are polymorphic in the type of the contents of the container - you can map over a list of strings or a list of ints, or any [a], as long as you have a function that takes the appropriate type to transform with.

We can take it up a notch. What if we wanted a single map function that not only works for any type of contents, but any type of container? Then we could call that function on a list, or a maybe, or
anything for which it makes sense to transform each of the elements. It should work like this:

> mapAnything (+1) [1,2,3]
[2,3,4]

> mapAnything (+1) $ Just 1
Just 2

> mapAnything (+1) Nothing
Nothing

(Slide)

What would the type of such a function be?

mapAnything :: (a -> b) -> f a -> f b

Here, we introduce a new type parameter, f. f stands in for something like [] or Maybe - the container. More precisely, f stands in for some *type constructor*.

If we try to implement this function, we won't be able to - there's no way to do it generically for any f.

Instead, we can create a typeclass:

class Container f where
        mapAnything :: (a -> b) -> f a -> f b

Then we make any container we want to map over an instance of this typeclass.

instance Container [] where
        mapAnything = map

instance Container Maybe where
        mapAnything = mapMaybe

And voila! We have a function mapAnything that works on any Container we've defined an instance for!

In fact, we don't need this typeclass. It's provided by the standard library. It's called Functor, and mapAnything is called fmap (the f is short for functor). Functor is very commonly used in haskell - most container types will have a Functor instance.

aside: whilst thinking of Functors as containers is a great starting intuition, there are some functors for which this metaphor becomes a bit less accurate. For example, there is a functor instance for for (r ->), the type of functions taking some type r. While you *can* think of a function as a sort of "container of a return value to be determined", doing so is a bit of a stretch.

> fmap (+1) [1,2,3]
[2,3,4]

Exercise 2.
Write a Functor instance for the binary tree data type. It should apply the given function to the value at each node, and not add or remove any nodes.

(starting code)
data Tree a = Node a (Tree a) (Tree a) | Leaf

(suggested solution)
instance Functor Tree where
        fmap _ Leaf = Leaf
        fmap f (Node x lt rt) = Node (f x) (fmap f lt) (fmap f rt)

Exercise 3.
Write a function

exclaim :: Tree (Maybe [String]) -> Tree (Maybe [String])

that adds an exclamation mark to the end of each inner string.

(suggested solution)

exclaim :: Tree (Maybe [String]) -> Tree (Maybe [String])
exclaim = (fmap . fmap . fmap) (++"!")

(slide)
An aside - kinds and higher kinded polymorphism

The polymorphism of the f type parameter is more abstract than the polymorphism we have seen so far. We've seen type parameters standing in for concrete types like "Int", "String", or "[String]", but not type *constructors* like [] and Maybe.

We need a way of distinguishing between these *types of types* - we call them "kinds". Concrete types like "Int", for which we can create values, are of kind "*". Type constructors can be thought of as functions at the type level - they take a single type parameter and return a type. For example if you give "Maybe" an "Int", you get a "Maybe Int". We therefore write the kind of type constructors similarly to the types of functions - type constructors are of kind "* -> *" - in other words they take a concrete type, and return a concrete type.

Since this f parameter is a type constructor, it has kind (* -> *). Polymorphism in parameters with kinds other than "*" is known as "higher kinded polymorphism", and it sets haskell apart from many other languages. It offers serious abstraction power and code reuse, at the cost of sometimes being difficult to understand.