Typeclass instances for functions

Question

I've just realized, that Functions have instances for Monad, Functor and Applicative.

What I usually do, when I see some typeclass instance I don't get, is write some well-typed expression and see what it returns:

Can somebody explain these instances? You usually hear about the instances for List and Maybe, which by now are natural to me, but I don't understand how Functions can be a Functor or even a Monad.

EDIT: Okay, this is a valid well-typed expression that doesn't compile:

fmap (+) (+) 1 (+1) 1

Answer 1

fmap for functions acts on the results produced by the function:

GHCi> :set -XTypeApplications
GHCi> :t fmap @((->) _)
fmap @((->) _) :: (a -> b) -> (t -> a) -> t -> b

The a result of the t -> a function is modified through an a -> b function. If that sounds a lot like function composition, that is because it is exactly that:

GHCi> fmap (3 *) (1 +) 4
15
GHCi> ((3 *) <$> (1 +)) 4
15
GHCi> ((3 *) . (1 +)) 4
15

(<*>) is a bit trickier:

GHCi> :t (<*>) @((->) _)
(<*>) @((->) _) :: (t -> a -> b) -> (t -> a) -> t -> b

The Applicative f => f (a -> b) argument becomes t -> (a -> b). (<*>) converts a function of two arguments (of type t -> a -> b) into a function of one argument (of type t -> b) by using an auxiliary function (of type t -> a) to generate the second argument from the first:

GHCi> :t \k f -> \x -> k x (f x)
\k f -> \x -> k x (f x) :: (t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1

Here is an example written in applicative style, using the Functor and Applicative instances of functions:

GHCi> ((&&) <$> (> 0) <*> (< 4)) 2
True

One way of reading it is "feed 2 to (> 0) and to (< 4), and combine the results with (&&)". It can be written in a more compact way with liftA2 from Control.Applicative, but I believe the (<$>)/(<*>) spelling is more intention-revealing.

The other method of Applicative, pure...

GHCi> :t pure @((->) _)
pure @((->) _) :: a -> t -> a

... makes a t -> a function out of an a and nothing else. A constant function is the only way of doing that:

GHCi> pure 2 "foo"
2
GHCi> pure 2 42
2

Do note that pure 2 has a different type in each of the examples above.

Given all of the above, the Monad instance is surprisingly uninteresting. For extra clarity, let's look at (=<<) rather than at (>>=):

GHCi> :t (=<<) @((->) _)
(=<<) @((->) _) :: (a -> t -> b) -> (t -> a) -> t -> b

If you compare this type with the one of (<*>), you will see they are the same, except that the first argument has been flipped. The function instances are an exceptional case in which Applicative and Monad do essentially the same thing.

It is worth mentioning that join from Control.Monad can be used to use a value as both arguments of a two-argument function:

GHCi> :t join @((->) _)
join @((->) _) :: (t -> t -> a) -> t -> a
GHCi> join (*) 5
25

Answer 2

First, I agree with you: functions are not very intuitive as functors, and indeed I sometimes wish these instances weren't there. It's not that they aren't useful sometimes, but quite as often they're used in a needless and confusing manner. These methods can always be replaced with either more specific combinators (in particular from Control.Arrow), or with the equivalent but somehow much more descriptive reader monad.

That said... to understand the function functor, I suggest you first consider Map. In a way, Map Int is a lot like an array: it contains some elements that you can transform (i.e. fmap over), and you can access individual elements by indexing them with integers. Map just allows the “array” to have gaps in it, and generalises from integer-indices to any sort of index that can be ordered.

On another view though, Map is just a specific implementation of a function: it associates arguments (keys) to results (values). And that should make it quite clear how the function functor works: it fmaps over all possible results^† of the function.

This explanation unfortunately doesn't much explain the Monad instance, because Map doesn't actually have a monad (nor even Applicative) instance. A direct adaption of the list/array implementation would indeed not be possible... recap: on lists, we have

pure x ≡ [x]
(,) <$> [a,b] <*> [x,y,z] ≡ [(a,x),(a,y),(a,z),(b,x),(b,y),(b,z)]

so after combining, the indices are all different. That can't work for Map where we want to support generic keys.

However, there's an alternative monad instance for list, the zip list:

pure x ≡ repeat x
(,) <$> [a,b] <*> [x,y,z] ≡ [(a,x),(b,y)]

Notice that the indices of the elements are preserved.

Now this instance could in fact be adapted for Map, if only there was a repeat :: a -> Map k a generator. This doesn't exist because in general there are infinitely many keys and we can't enumerate them all nor balance the infinite tree that such a Map would entail. But if we restrict ourselves to key types with only finitely many possible values (such as Bool), then we're good:

instance Applicative (Map Bool) where
  pure x = Map.fromList [(False, x), (True, x)]
  <*> = Map.intersectWith ($)

Now, that's exactly how the function monad works, just unlike with Map there's no problem if infinitely many different arguments are possible, because you never attempt to store all of them with associated values; rather you always only compute the values on the spot.

---

^†_{That would be infeasible if it weren't done lazily – which in Haskell is hardly a problem, in fact if you fmap over a Map it also happens lazily. For the function functor, fmap is actually not just lazy but the result is also immediately forgotten and needs to be recalculated.}