User:Duplode/Applicative functors rewrite

When covering the vital Functor and Monad type classes, we glossed over a third type class: Applicative, the class for applicative functors. Like monads, applicative functors are functors with extra laws and operations; in fact, Applicative is an intermediate class between Functor and Monad. Applicative are a widely used class with a wealth of applications (pardon the pun). It enables the eponymous applicative style, a convenient way of structuring functorial computations, and also provides means to express a number of important patterns.

Functor recap

We will begin with a quick review of the Functor class chapter. Functor is characterised by the fmap function:

class Functor f where
    fmap :: (a -> b) -> (f a -> f b)

If a type has an instance of Functor, you can use fmap to apply a functions to values in it. Another way of describing fmap is saying that it promotes functions to act on functorial values. To ensure fmap works sanely, any instance of Functor must comply with the following two laws:

fmap id = id                   -- 1st functor law
fmap (g . f) = fmap g . fmap f -- 2nd functor law

Maybe, for example, has a Functor instance, and so we can easily modify the value inside it...

Prelude> fmap negate (Just 2)
Just (-2)

...as long as it exists, of course.

Prelude> fmap negate Nothing
Nothing

For extra convenience, fmap has an infix synonym, (<$>). It often helps readability, and also suggests how fmap can be seen as a different kind of function application.

Prelude> negate <$> Just 2
Just (-2)

Exercises
Define instances of Functor for the following types: A rose tree, defined as: data Tree a = Node a [Tree a] Either e for a fixed e. The function type ((->) r). In this case, f a will be (r -> a)

Application in functors

As useful as it is, fmap isn't much help if we want to apply a function of two arguments to functorial values. For instance, how could we sum Just 2 and Just 3? The brute force approach would be extracting the values from the Maybe wrapper. That, however, would mean having to do tedious checks for Nothing. Even worse: in a different Functor extracting the value might not even be an option (just think about IO).

We could use fmap to partially apply (+) to the first argument:

Prelude> :t (+) <$> Just 2
(+) <$> Just 2 :: Num a => Maybe (a -> a)

But now we are stuck: we have a function and a value both wrapped in Maybe, and no way of applying one to the other. What we would like to have is an operator with a type akin to f (a -> b) -> f a -> f b to apply functions in the context of a functor. If that operator was called (<*>), we would be able to write:

(+) <$> Just 2 <*> Just 3

Lo and behold - if you try that in GHCi it will just work!

Prelude> (+) <$> Just 2 <*> Just 3
Just 5

The type of (<*>) is:

Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

(<*>) is one of the methods of Applicative, the type class of applicative functors - functors that support function application within their contexts. Expressions such as (+) <$> Just 2 <*> Just 3 are said to be written in applicative style, which is as close as we can get to regular function application while working with a functor. If you pretend for a moment the (<$>), (<*>) and Just aren't there, our example looks just like (+) 2 3.

The Applicative class

The definition of Applicative is:

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

Beyond (<*>), the class has a second method, pure, which brings arbitrary values into the functor. As an example, let's have a look at the Maybe instance:

instance Applicative Maybe where
    pure                  = Just
    (Just f) <*> (Just x) = Just (f x)
    _        <*> _        = Nothing

It doesn't do anything surprising: pure wraps the value with Just; (<*>) applies the function to the value if both exists, and results in Nothing otherwise.

Applicative functor laws

Note

For the lack of a better shorthand, in what follows we will use the jargony word morphism to refer to the values to the left of (<*>), which fit the type Applicative f => f (a -> b); that is, the function-like things inserted into an applicative functor. "Morphism" is a term which comes from category theory and which has a much wider meaning, but that needn't concern us now.

Just like Functor, Applicative has a set of laws which reasonable instances should follow. They are:

pure id <*> v = v                            -- Identity
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition

Those laws are a bit of a mouthful. They become easier to understand if you think of pure as a way to inject values into the functor in a default, featureless way, so that the result is as close as possible to the plain value. Thus:

• The identity law says that applying the pure id morphism does nothing, exactly like with the plain id function.
• The homomorphism law says that applying a "pure" function to a "pure" value is the same than applying the function to the value in the normal way and then using pure on the result. In a sense, that means pure preserves function application.
• The interchange law says that applying a morphism to a "pure" value pure y is the same as applying pure ($ y) to the morphism. No surprises there - as we have seen in the higher order functions chapter, ($ y) is the function that supplies y as argument to another function.
• The composition law says that if (<*>) is used to compose morphisms the composition is associative, like plain function composition .

There is also a bonus law about the relation between fmap and (<*>):

fmap f x = pure f <*> x                      -- fmap

Applying a "pure" function with (<*>) is equivalent to using fmap. This law is a consequence of the other ones, so you need not bother with proving it when writing instances of Applicative.

Exercises
Check that the Applicative laws hold for this instance for Maybe Write Applicative instances for a. Either e, for a fixed e b. ((->) r), for a fixed r

Déja vu

Does pure remind you of anything?

pure :: Applicative f => a -> f a

The only difference between that and...

return :: Monad m => a -> m a

... is the class constraint. pure and return serve the same purpose; that is, bringing values into functors. The uncanny resemblances do not stop here. Back in the chapter about State we mentioned a function called ap...

ap :: (Monad m) => m (a -> b) -> m a -> m b

... which could be used to handle functions with many arguments less painful to handle in monadic code:

allTypes :: GeneratorState (Int, Float, Char, Integer, Double, Bool, Int)
allTypes = liftM (,,,,,,) getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom

ap looks a lot like (<*>).

Those, of course, are not coincidences. Monad inherits from Applicative...

Prelude> :info Monad
class Applicative m => Monad (m :: * -> *) where
--etc.

... because return and (>>=) are enough to implement pure and (<*>) .

pure = return
(<*>) = ap

ap u v = do
    f <- u
    x <- v
    return (f x)

Several other monadic functions have more general applicative versions. Here are a few of them:

Monadic	Applicative	Module (where to find the applicative version)
(>>)	(*>)	Prelude
liftM2	liftA2	Control.Applicative
mapM	traverse	Prelude
sequence	sequenceA	Data.Traversable
forM_	for_	Data.Foldable

Exercises
Write a definition of (<*>) using (>>=) and fmap. Do not use do-notation. Implement liftA5 :: Applicative f => (a -> b -> c -> d -> e -> k) -> f a -> f b -> f c -> f d -> f e -> f k

ZipList

Lists are applicative functors as well. Specialised to lists, the type of (<*>) becomes...

[a -> b] -> [a] -> [b]

... and so (<*>) applies a list of functions to another list. But exactly how is that done?

The standard instance of Applicative for lists, which follows from the Monad instance, applies every function to every element, like an explosive version of map.

Prelude> [(2*),(5*),(9*)] <*> [1,4,7]
[2,8,14,5,20,35,9,36,63]

Interestingly, there is another reasonable way of applying a list of functions. Instead of using every combination of functions and values, we can match each function with the value in the corresponding position in the other list. A Prelude function which can be used for that is zipWith:

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> zipWith ($) [(2*),(5*),(9*)] [1,4,7]
[2,20,63]

When there are two useful possible instances for a single type, the dilemma is averted by creating a newtype which implements one of them. In this case, we have ZipList, which lives in Control.Applicative:

newtype ZipList a = ZipList { getZipList :: [a] }

We have already seen what <*> should be for zip-lists; all that is needed is to add the newtype wrappers:

instance Applicative ZipList where
    (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs xs)
    pure x                        = undefined -- TODO

As for pure, it is tempting to use pure x= ZipList [x], following the standard list instance. We can't do that, however, as it violates the applicative laws. According to the identity law:

pure id <*> v = v

Substituting (<*>) and the suggested pure, we get:

ZipList [id] <*> ZipList xs = ZipList xs
ZipList (zipWith ($) [id] xs) = ZipList xs

Now, suppose xs is the infinite list [1..]:

ZipList (zipWith ($) [id] [1..]) = ZipList [1..]
ZipList [1] = ZipList [1..]
[1] = [1..] -- Obviously false!

The problem is that zipWith produces lists whose length is that of the shortest list passed as argument, and so (ZipList [id] <*>) will cut off all elements of the other zip-list after the first. The only way to ensure zipWith ($) fs never removes elements is making fs infinite. The correct pure follows from that:

instance Applicative ZipList where
    (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs xs)
    pure x                        = ZipList (repeat x)

The ZipList applicative instance offers an alternative to all the zipN and zipWithN functions in Data.List which can be extended to any number of arguments:

>>> import Control.Applicative
>>> ZipList [(2*),(5*),(9*)] <*> ZipList [1,4,7]
ZipList {getZipList = [2,20,63]}
>>> (,,) <$> ZipList [1,4,9] <*> ZipList [2,8,1] <*> ZipList [0,0,9]
ZipList {getZipList = [(1,2,0),(4,8,0),(9,1,9)]}
>>> liftA3 (,,) (ZipList [1,4,9]) (ZipList [2,8,1]) (ZipList [0,0,9])
ZipList {getZipList = [(1,2,0),(4,8,0),(9,1,9)]}

Sequencing of effects

As we have just seen, the standard Applicative instance for lists applies every function in one list to every element of the other. That, however, does not specify (<*>) unambiguously. To see why, try to guess what is the result of [(2*),(3*)]<*>[4,5] without looking at the example above or the answer just below.

Prelude> [(2*),(3*)] <*> [4,5]


--- ...


[8,10,12,15]

Unless you were paying very close attention or had already analysed the implementation of (<*>), the odds of getting it right were about even. The other possibility would be [8,12,10,15]. The difference is that for the first (and correct) answer the result is obtained by taking the skeleton of the first list and replacing each element by all possible combinations with elements of the second list, while for the other possibility the starting point is the second list.

In more general terms, the difference between is one of sequencing of effects. Here, by effects we mean the functorial context, as opposedto the values within the functor (some examples: the skeleton of a list, actions performed in the real world in IO, the existence of a value in Maybe). The existence of two legal implementations of (<*>) for lists which only differ in the sequencing of events indicates that [] is a non-commutative applicative functor. A commutative applicative functor, by contrast, leaves no margin for ambiguity in that respect. More formally, a commutative applicative functor is one for which the following holds:

liftM2 f u v = liftM2 (flip f) v u -- Commutativity

Or, equivalently,

f <$> u <*> v = flip f <$> v <*> u

By the way, if you hear about commutative monads in Haskell, the concept involved is the same, only specialised to Monad.

Commutativity (or the lack thereof) affects other functions which are derived from (<*>) as well. (*>) is a clear example:

(*>) :: Applicative f => f a -> f b -> f b

(*>) combines effects while preserving only the values of its second argument. For monads, it is equivalent to (>>). Here is a demonstration of it using Maybe, which is commutative:

Prelude> Just 2 *> Just 3
Just 3
Prelude> Just 3 *> Just 2
Just 2
Prelude> Just 2 *> Nothing
Nothing
Prelude> Nothing *> Just 2
Nothing

Swapping the arguments does not affect the effects (that is, the being and nothingness of wrapped values). For IO, however, swapping the arguments does reorder the effects:

Prelude> (print "foo" *> pure 2) *> (print "bar" *> pure 3)
"foo"
"bar"
3
Prelude> (print "bar" *> pure 3) *> (print "foo" *> pure 2)
"bar"
"foo"
2

The convention in Haskell is to always implement (<*>) and other applicative operators using left-to-right sequencing. Even though this convention helps reducing confusion, it also means appearances sometimes are misleading. For instance, the (<*) function is not flip (*>), as it sequences effects from left to right just like (*>):

Prelude> (print "foo" *> pure 2) <* (print "bar" *> pure 3)
"foo"
"bar"
2

For the same reason, (<**>) :: Applicative f => f a -> f (a -> b) -> f b from Control.Applicative is not flip (<*>). That means it provides a way of inverting the sequencing:

>>> [(2*),(3*)] <*> [4,5]
[8,10,12,15]
>>> [4,5] <**> [(2*),(3*)]
[8,12,10,15]

An alternative is the Control.Applicative.Backwards module from transformers, which offers a newtype for flipping the order of effects:

newtype Backwards f a = Backwards { forwards :: f a }

>>> Backwards [(2*),(3*)] <*> Backwards [4,5]
Backwards [8,12,10,15]

Exercises

For the list functor, implement from scratch (that is, without using anything from Applicative or Monad directly) both (<*>) and its version with the "wrong" sequencing of effects, (<|*|>) :: Applicative f => f (a -> b) -> f a -> f b Rewrite the definition of commutativity for a Monad using do-notation instead of ap or liftM2. Are the following applicative functors commutative? a. ZipList b. ((->) r) c. State s (Use the newtype definition from the State chapter. Hint: You may find the answer to exercise 2 of this block useful.) What is the result of [2,7,8] *> [3,9]? (Try to guess without writing.) Implement (<**>) in terms of other Applicative functions. As we have just seen, some functors allow two legal implementations of (<*>) with different sequencing of effects. Why there is not an analogous issue involving (>>=)?

A sliding scale of power

Functor, Applicative, Monad. Three closely related functor type classes; three of the most important classes in Haskell. Though we have seen many examples of Functor and Monad in use, and a few of Applicative, we have not compared them head to head yet. If we ignore pure/return for a moment, the characteristic methods of the three classes are:

fmap :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

While those look like disparate types, we can change the picture with a few aesthetic changes. Let's replace fmap by its infix synonym, (<$>); (>>=) by its flipped version, (=<<); and tidy up the signatures a bit:

(<$>) :: Functor t     =>   (a -> b) -> (t a -> t b)
(<*>) :: Applicative t => t (a -> b) -> (t a -> t b)
(=<<) :: Monad t       => (a -> t b) -> (t a -> t b)

Suddenly, the similarities are striking. fmap, (<*>) and (=<<) are all mapping functions over Functors . The differences between them are in what is being mapped over in each case:

• fmap maps arbitrary functions over functors.
• (<*>) maps t (a -> b) morphisms over (applicative) functors.
• (=<<) maps a -> t b functions over (monadic) functors.

The day-to-day differences in uses of Functor, Applicative and Monad follow from what the types of those three mapping functions allow you to do. As you move from fmap to (<*>) and then to (>>=), you gain in power, versatility and control, at the cost of guarantees about the results. We will now slide along this scale. While doing so, we will use the contrasting terms values and context to refer to plain values within a functor and to the whatever surrounds them, respectively.

The type of fmap ensures that it is impossible to use it to change the context, no matter which function it is given. In (a -> b) -> t a -> t b, the (a -> b) function has nothing to do with the t context of the t a functorial value, and so applying it cannot affect the context. For that reason, if you do fmap f xs on some list xs the number of elements of the list will never change.

Prelude> fmap (2*) [2,5,6]
[4,10,12]

That can be taken as a safety guarantee or as an unfortunate restriction, depending on what you intend. In any case, (<*>) is clearly able to change the context:

Prelude> [(2*),(3*)] <*> [2,5,6]
[4,10,12,6,15,18]

The t (a -> b) morphism carries a context of its own, which is combined with that of the t a functorial value. (<*>), however, is subject to a more subtle restriction. While t (a -> b) morphisms carry context, within them there are plain (a -> b), which are still unable to modify the context. That means the changes to the context (<*>) performs are fully determined by the context of its arguments, and the values have no influence over the resulting context.

Prelude> (print "foo" *> pure (2*)) <*> (print "bar" *> pure 3)
"foo"
"bar"
6
Prelude> (print "foo" *> pure 2) *> (print "bar" *> pure 3)
"foo"
"bar"
3
Prelude> (print "foo" *> pure undefined) *> (print "bar" *> pure 3)
"foo"
"bar"
3

Thus with list (<*>) you know that the length of the resulting list will be the product of the lengths of the original lists, with IO (<*>) you know that all real world effect will happen as long as the evaluation terminates, and so forth.

With Monad, however, we are in a very different game. (>>=) takes a a -> t b function, and so it is able to create context from values. That means a lot of flexibility:

Prelude> [1,2,5] >>= \x -> replicate x x
[1,2,2,5,5,5,5,5]
Prelude> [0,0,0] >>= \x -> replicate x x
[]
Prelude> return 3 >>= \x -> print $ if x < 10 then "Too small" else "OK"
"Too small"
Prelude> return 42 >>= \x -> print $ if x < 10 then "Too small" else "OK"
"OK"

Taking advantage of the extra flexibility, however, might mean having less guarantees about, for instance, whether your functions are able to unexpectedly erase parts of a data structure for pathological inputs, or whether the control flow in your application remains intelligible. In some situations there might be performance implications as well, as the complex data dependencies monadic code makes possible might prevent useful refactorings and optimisations. All in all, it is a good idea to only use as much power as needed for the task at hand. If you do need the extra capabilities of Monad, go right ahead; however, it is often worth it to check whether Applicative or Functor are sufficient.

Exercises

The next few exercises concern the following tree data structure: data AT a = L a | B (AT a) (AT a) Write Functor, Applicative and Monad instances for AT. Do not use shortcuts such as pure = return. The Applicative and Monad instances should match; in particular, (<*>) should be equivalent to ap, which follows from the Monad instance. Implement the following functions, using either the Applicative instance, the Monad one or neither of them, if neither is enough to provide a solution. Between Applicative and Monad, choose the least powerful one which is still good enough for the task. Justify your choice for each case in a few words. a. fructify :: AT a -> AT a, which grows the tree by replacing each leaf L with a branch B containing two copies of the leaf. b. prune :: a -> (a -> Bool) -> AT a -> AT a, with prune z p t replacing a branch of t with a leaf carrying the default value z whenever any of the leaves directly on it satisfies the test p. c. reproduce :: (a -> b) -> (a -> b) -> AT a -> AT b, with reproduce f g t resulting in a new tree with two modified copies of t on the root branch. The left copy is obtained by applying f to the values in t, and the same goes for g and the right copy. There is another legal instance of Applicative for AT (the reversed sequencing version of the original one doesn't count). Write it. Hint: this other instance can be used to implement sagittalMap :: (a -> b) -> (a -> b) -> AT a -> AT b which, when given a branch, maps one function over the left child tree and the other over the right child tree. (In case you are wondering, "AT" stands for "apple tree". Botanist readers, please forgive the weak metaphors.)

The monoidal presentation

Back in Understanding monads, we saw how the Monad class can be specified using either (>=>) or join instead of (>>=). In a similar way, Applicative also has an alternative presentation, which might be implemented through the following type class:

class Functor f => Monoidal f where
    unit  :: f ()
    (*&*) :: f a -> f b -> f (a,b)

There are deep theoretical reasons behind the name "monoidal" . In any case, we can informally say that it does look a lot like a monoid: unit provides a default functorial value whose context wraps nothing of interest, and (*&*) combines functorial values by pairing values and combining effects. The Monoidal formulation provides a clearer view of how Applicative manipulates functorial contexts. Naturally, unit and (*&*) can be used to define pure and (<*>), and vice-versa.

The Applicative laws are equivalent to the following set of laws, stated in terms of Monoidal:

fmap snd $ unit *&* v = v                    -- Left identity
fmap fst $ u *&* unit = u                    -- Right identity
fmap asl $ u *&* (v *&* w) = (u *&* v) *&* w -- Associativity
-- asl (x, (y, z)) = ((x, y), z)

The functions to the left of the ($) are just boilerplate to convert between equivalent types, such as b and ((), b). If you ignore them, the laws are a lot less opaque than in the usual Applicative formulation. By the way, just like for Applicative there is a bonus law, which is guaranteed to hold in Haskell:

fmap (g *** h) (u *&* v) = fmap g u *&* fmap h v -- Naturality
-- g *** h = \(x, y) -> (g x, h y)

Exercises
Write implementations for unit and (*&*) in terms of pure and (<*>), and vice-versa. Formulate the law of commutative applicative functors (see the Sequencing of effects section) in terms of the Monoidal methods. Write from scratch Monoidal instances for: a. ZipList b. ((->) r)