Typical instances for functions

Question

I just realized that functions have instances for Monad, Functor, and Applicative.

What I usually do when I see some typeclass instance that I don’t get is some well-typed expression written and see what it returns:

Can someone explain these cases? You usually hear about List and Maybe instances, which by then are natural for me, but I don’t understand how functions can be Functor or even Monad.

EDIT: Well, this is a valid well-typed expression that does not compile:

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

Answer 1

First, I agree with you: functions are not very intuitive, like functors, and I sometimes want these instances not to be there. It is not that they are sometimes not useful, but quite often they are used in a useless and confusing manner. These methods can always be replaced either by more specific combinators (in particular, from Control.Arrow ), or with an equivalent, but somehow more descriptive reader monad .

However ... to understand the functor of a function, I suggest you first consider Map . In a sense, Map Int very similar to an array: it contains some elements that you can convert (i.e. fmap over), and you can access individual elements by indexing them with integers. Map simply allows the "array" to have spaces in it and generalizes from whole indices to any type of index that you can order.

In another view, however, Map is just a concrete implementation of a function: it maps arguments (keys) to results (values). And this should clearly show how the functor of the function works: it displays all the possible results of the function ^† .

This explanation, unfortunately, does not explain the Monad instance much, because Map does not actually have a monad instance (or even Applicative ). Direct adaptation of the list / array implementation would really be impossible ... recap: in lists we have

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

therefore, after combining, the indices are all different. This may not work for Map , where we want to support shared keys.

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

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

Please note that item indices are saved.

Now this instance can really be adapted for Map , provided that the repeat :: a -> Map ka generator exists. This does not exist, because in the general case there are infinitely many keys, and we cannot list all of them and balance the infinite tree that such a Map entails. But if we restrict ourselves to key types with a finite number of possible values ​​(for example, Bool ), then we are good:

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

Now, how the monad function works, unlike Map there is no problem if an infinite number of different arguments are possible, because you never try to save them all with associated values; rather, you always only calculate the values ​​in place.

---

^† _{It would not be feasible 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 a functional functor, fmap is actually not just lazy, but the result is also immediately forgotten and needs to be recalculated.}

Answer 2

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

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

The result a function t -> a changed using the function a -> b . If this sounds very similar to function composition, it is because it is precisely what:

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

(<*>) little trickier:

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

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

 GHCi> :t \kf -> \x -> kx (fx) \kf -> \x -> kx (fx) :: (t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1 

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

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

One way to read: "feed 2 to (> 0) and (< 4) and combine the results with (&&) ." It can be written in a more compact way with liftA2 from Control.Applicative , but I believe that writing (<$>) / (<*>) reveals more intensively.

Another Applicative method, pure ...

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

... makes the function t -> a from a and nothing else. A persistent function is the only way to do this:

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

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

Given all of the above, the Monad instance is surprisingly uninteresting. For clarity, look at (=<<) , not (>>=) :

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

If you compare this type with one of (<*>) , you will see that they are the same, except that the first argument is inverted. Function instances are an exceptional case where Applicative and Monad perform essentially the same thing.

It is worth noting that the join from Control.Monad can be used to use the value as both arguments to a function with two arguments:

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