Functors and Applicative Functors

On my continuing journey through Learn You a Haskell, I have come to Functors and Applicative Functors. Two related data types which seem to be pretty fundamental to understanding Haskell and which I can use, but don’t feel I properly understand. So time to write about it, since it’s the best method I know of to get my thoughts crystallised and focussed.

What is a functor?

Practically speaking, Functor is a type which can be mapped over. The classic example is a list, which contains a list of values and is the target of many mapping operations, but there are others: Notably the Maybe type, which describes a value as being either Just something or Nothing.

Lipovaca describes them as being like boxes which hold one or many values, or as the context of a piece of data. I prefer the latter since I think it’s more descriptive. Using a Maybe gives the context that the value can be missing, and adds a level of non-determinism to a data structure that must be resolved deterministically by defining the action to take with Nothing and Just.

Functors are defined as having the type * -> * which means that they accept a concrete type as a type parameter. This applies equally to both [] and Maybe: A List can only hold one type of item, it is homogenous, and Maybe a can also only hold one type of item because it only holds one value.

The context of a List is that it holds a non-deterministic number of values of the same type. So you don’t know how many values it has, so you need to take that context into account when you try and work with those values. Again, the case also applies with Maybe: you don’t know if the value is there or not.

All functors derive the fmap function. It has the following signature:

    fmap :: Functor f => (a -> b) -> f a -> f b

So fmap takes a function that converts a -> b and a functor containing a and then returns a functor containing b. The key point to bear in mind here is that the f does not change. The type signature says: “Give me a function that takes one parameter and a functor, and I will give you access to its value by applying the value of the functor to that equation, and then return a new functor of the same type with the new value in it”.

Simple.

Each instance of class functor defines its own implementation of fmap which gives the caller access to the value it contains. In the case of list it is simply as follows:

instance Functor [] where
    fmap = map

However in the case of Maybe it is:

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing

The Maybe version describes the paradigm well: x in Just x is applied to f and wrapped in a new Just. fmap grants you access to the value in its context and handles the application of the function accordingly.

Functions as Functors

I’m pretty much going to lift this bit directly from Lipovaca; more or less regurgitate what he says in a more compact form.

Functions are functors as well. The definition of Functor as it is derived by function (formally symbolised as ((->) r)) is as follows:

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

This is a pretty easy one. It returns a new function where f, the first argument passed to fmap receives the value of g, the function acting as the functor, which in turn receives x, the only parameter of the new function. So you could do something like this:

    fmap (*2) (*3) $ 3 -- => 3 * 3 * 2 => 18

Where is the “context” in these examples? The context is defined by the function itself, because the value that is contained in the box that is the function is whatever the function does to the value that it is given. For example, in the case of sum the context is that the value will be the sum of all the values in a list. fmap gives you access to that eventual value once sum has received the list of values it has to add up. You provide a function that gains access to that value through the functor.

In the example above I used a function that accepts two parameters in the first argument, and another which accepts one argument as the functor. You must use a function that accepts one argument as the functor, because the new function only accepts one argument, which it passes directly to the functor. However, due to partial application the function passed to fmap can take as many arguments as you like, provided that its first argument accepts the type that the functor returns. This actually feels awfully familiar. One function, that accepts another function that only takes one parameter? Function composition! Here’s an example:

    > f = fmap (abs) (sum)
    > f [-1,-2,-3,-4,-5] -- => 15
    > abs . sum $ [-1,-2,-3,-4,-5] -- => 15

Applicative Functors

There is an inherent problem with functors, which is essentially this:

    fmap (Just (+3)) (Just 3) -- => BOOM! error: Couldn't match...

fmap provides a function access to the context of a functor, but it does not allow you to perform operations within the same context. For that job, there is the Applicative class.

Applicative defines two methods: pure and <*> . The class definition is as follows:

    class (Functor f) => Applicative f where
        pure :: a -> f a
        (<*>) :: f (a -> b) -> f a -> f b

The type definition says: An Applicative is a Functor that defines two methods: pure which accepts any value and returns it wrapped in a context, and <*> which accepts a functor containing a function that converts a value from a to b, as well as a functor containing a value of type a, and will return a functor containing a value of type b. In other words, it accepts a function in a given context, and a value in the same context, and applies the function to that value in order to return a value in the same context. Got it? I’m impressed! I confused myself with that one. Just for my own sanity let’s see an example:

    > Just(abs) <*> Just (-5) -- => Just 5

There is an interesting aside about type classes that one can learn from pure which is that the type is also a kind of parameter. Look at the following:

    > pure 5 -- => 5
    > f = pure 5 -- type: (Applicative f, Num a) => f a
    > f :: Maybe -- => Just 5 

By putting pure 5 in a variable, I stopped the compiler from resolving the type immediately - Haskell is a lazy language. Literally. When I applied a type signature to f it was then able to return a value because it could resolve the type.

However, when I just called pure 5 Haskell was forced to work out a type for the result immediately since it had to return something and so it interpreted the type as being the same as the parameter - Num, hence it just returned the original parameter. This is not partial application, everything must have a type and if a type cannot be resolved the Haskell has no choice but to throw an error.

Well, that all makes a lot more sense to me now. The next chapter is monoids, whatever they may be…

Written with StackEdit.