Applicative Functors in Haskell

Archive note: this post began as an unpublished Hakyll draft from 2020. I have lightly edited it for grammar, metadata, and rendering, but preserved the original line of argument and its unfinished exploratory character.

Now it’s getting even more interesting about functors in Haskell. Recall that if we have a functorial type f a, where f is an instance of type class Functor, we can apply fmap g to its values x :: f a, where g :: a -> b. In terms of category theory, this means that if we have an object $x$ in category $D$ and a functor $F$ such that, for every morphism $f : a \to b$ in $C$ such that $Fa = x$ and $Ff : Fa \to Fb$, we can lift the morphism $f$ from category $C$ along the functor $F$ to the morphism $Ff$ in category $D$.

We also discovered that, e.g., Maybe and [] are such functorial type constructors f, or simply “functors.” Now, how is an applicative functor different from an ordinary functor? First of all, an applicative functor is always a functor.

Function Application

Ordinary function application

Given a function u :: a -> b, apply it to a value x :: a to obtain a value u x :: b. This implicit function application can be represented by the infix function, or operator, if you like, denoted by $. Its signature is $ :: (a -> b) -> a -> b. It can be written as the binary “application” or “evaluation” operator $\Langle\, \cdot\,,\; \cdot\, \Rangle \;:\; b^a \times a \to a,\; (u,x) \mapsto u(x),$ to represent the sections

• (u $) : a -> b which corresponds to just u as $\Langle u, \cdot \Rangle$, and
• ($ x) : (a -> b) -> b which describes the curried association $u \mapsto u(x)$.

Function application in functorial context

Now if in fact our x :: f a, where f is a functor, we need a way to lift u to apply it in that context f. In Haskell, this is accomplished with fmap, which describes the application of the functor f or $F : C \to D$, which by definition transforms morphisms $u : a \to b$ in $\mathrm{Hom}(C)$ into $Fu : Fa \to Fb$ in $\mathrm{Hom}(D)$, corresponding to Haskell’s fmap u :: f a -> f b. Recall that <$> = fmap.

Application of a functorial function

In a next step we will discover how we can describe the situation where u is binary or also belongs to the context f, where f now is a more complex structure than an ordinary functor, viz. an applicative functor.

Recall that

• fmap :: (a -> b) -> (f a -> f b).

Suppose b ~ (s -> t). Then fmap :: (a -> s -> t) -> (f (s -> t) -> b). But what if we needed (a -> s -> t) -> (f a -> f s -> f t? For this we can’t use fmap. But with Applicative, we obtain

• liftA = fmap :: (a -> b) -> (f a -> f b)
• liftA2 :: (a -> b -> c) -> (f a -> f b -> f c)
• liftA3 :: (a -> b -> c -> d) -> (f a -> f b -> f c -> f d)

This is one of the benefits. The other one is the application of functorial functions u :: f (a -> b) to functorial values f a, where f is an Applicative functor.¹

So eventually we get at our disposal the functions

$      ::   (a -> b)    ->   a ->   b
<$>    ::   (a -> b)    -> f a -> f b
<*>    :: f (a -> b)    -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c

Remark. We also have the flipped variants for convenience,

&    = flip ($)   ::   a -> (a -> b) ->   b    -- infixl 1, Data.Function
<&>  = flip (<$>) :: f a ->   (a -> b) -> f b  -- infixl 1, Data.Functor

Remark. For syntactic correctness, such infix operators must be defined and referenced enclosed in matching parentheses, e.g., (<&>) = flip (<$>).

Definition of Applicative in Haskell

In Haskell, a Functor instance f is said to be applicative or instantiate the class Applicative, if it correctly implements the following behavior.

class Functor f => Applicative f where   {-# MINIMAL pure, ((<*>) | liftA2) #-}
  pure   :: a -> f a

  <*>    :: f (a -> b)      -> (f a -> f b)         -- A fancy `fmap`.
  liftA2 ::   (a -> b -> c) -> (f a -> f b -> f c)  -- Lifting a ternary fn.

where infixl 4 <*>.

Remark. The fact that either one of (<*>) and liftA2 suffices is due to the fact that we can express either one in terms of the other one.

By default, liftA2 u x y = u <$> x <*> y, which is referred to as the “applicative pattern” below.

Here, “correctly” above refers to satisfying the following four Applicative laws.

1. Lifted identity: pure id <*> x = x, i.e., (pure id <*>) = id.
2. Composition: pure (.) <*> u <*> v <*> x = u <*> (v <*> x), where parentheses are due to the infixl 4 fixity.
3. Functoriality:² pure u <*> pure x = pure (u x), where u :: a -> b and x :: f a.
4. Commutativity: u <*> pure x = pure ($ x) <*> u. Also called “interchange.”

These four laws define the additional structure imposed upon Functor, which means that we therefore have six laws to satisfy for an arbitrary type that is deemed to be an instance of Applicative. Suppose we wanted to instantiate Applicative for a tailor-made type constructor T :: * -> * of our own. We then first instantiate Functor for T and prove the Functor laws, and then, given that instance, we instantiate Applicative for T and prove the Applicative laws.

In other words an “applicative” functor $F$ is a functor in its own right, enriched with additional structure. It is a special functor, a more specific one. In the language of Haskell, this is expressed by a class definition above, repeated here:

class (Functor f) => Applicative f where    {-# MINIMAL pure, ((<*>) | liftA2) #-}
  pure   :: a -> f a
  (<*>)  :: f (a -> b) -> (f a -> f b)
  liftA2 :: (a -> b -> c) -> (f a -> f b -> f c)

The MINIMAL pragma means that an instance must specify an implementation of pure and either one of (<*>) or liftA2. The <*> operator is pronounced “ap” for “apply” and there exists a functor ap :: Monad m => m (a -> b) -> (m a -> m b) in the module Control.Monad, too, which does the same but is more specific by being defined for monads m only --- applicative functors are more general than monads, and monads are special applicative functors.

Exercise: Contrast <*> with <$> = fmap. What do you think is its purpose? We will need this below.

A side note: applicative functors describe parallel computations, whereas monads encode sequential computations that enable the sequencing of side effects.

The class declaration above entails that there are two ways to declare an instance of the applicative functor type class. Both require that you ensure its correctness. As I’ve already mentioned, there is a QuickCheck extension that automates this for you. But it is still a good practice to do it by hand. The laws for the implementation in terms of ap are stated above, and the laws that we need to verify for a liftA2 implementation are as follows.

1. Lifted identity: pure id <*> x = x, i.e., (pure id <*>) = id.

2. Composition: pure (.) <*> u <*> v <*> x = u <*> (v <*> x), where parentheses are due to the infixl 4 fixity.

3. Functoriality: pure u <*> pure x = pure (u x), where u :: a -> b and x :: f a.

4. Commutativity: u <*> pure x = pure ($ x) <*> u. Also called “interchange.”

\node (X) {$X$};
\node (Y) [below of=X, left of=X] {$Y$};
\node (Y') [below of=X, right of=X] {$Y^\prime$};
\draw[->] (Y) to node {$i$} (X);
\draw[->] (Y') to node [swap] {$i^\prime$} (X);
\draw[transform canvas={yshift=0.5ex}, ->] (Y) to node {$\alpha$} (Y');
\draw[transform canvas={yshift=-0.5ex}, ->] (Y') to node {$\alpha^{-1}$} (Y);

A Characterization

The type class Applicative in Haskell is intended to denote strong lax monoidal endofunctors. Without extra mental tinkering, Hask does not constitute a category, and thereby speaking of “functors” is a bit of a leap. But we can denotationally approximate the notions in a sense.

Indeed, consider the type class

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

Since we omit to provide the dual functions, reversed in the opposite directly, it is called “lax.” The monoidal structure is given in terms of unit and pairing, which can be rewritten as

unit' :: () -> f ()
(**') :: (f a, f b) -> f (a, b)

Indeed, recall that, among function arguments, the product type (a, b) is equivalent to the function type a -> b, which can be converted to a function using curry and uncurry, and that f () is equivalent to () -> f (), where the unit () is just a singleton type, canonically represented by the single element (), which is simply written the same (again no syntactic ambiguity, since both occupy different name spaces); in fact, there is a bijection or isomorphism (a, ()) = a = ((), a) and similarly ((a, b), c) = (a, b, c) = (a, (b, c)).

The structure thus given must satisfy the monoidal laws,

1. associativity: u ** (v ** w) = (u ** v) ** w
2. identity:
   • unit ** v = v
   • u ** unit = u

which are equivalent to the Applicative laws stated above.

Let’s now construct pure and (<*>) from unit and (**).

pure :: a -> f a
pure a = (\() -> a) <$> unit

where we can substitute the first function with const a :: b -> a, which is more general. And now the applicative operator,

(<*>) :: f (a -> b) -> (f a -> f b)
f <*> a = (\(a, f) -> f a) <$> a ** f

where the first function lifted by fmap or (<$>) is just the usual evaluation operator, often used in the definition of a duality pairing or an inner product in functional analysis. This is admittedly not really apparent. Let’s dissect the expression. Observe first that a ** f :: f (a, a -> b), so we simply need to apply the second component to the first to obtain a value of type b that will be lifted to f b, the result of <*> that are seeking; but first we need to lift that function evaluation since the tuple itself is lifted, which we do with fmap. In fact, that function evaluation operator that we lift with fmap is nothing fancy and it is equivalent to

uncurry ($) :: (a -> b, a) -> b

where the function application operator

curry   :: ((a, b) -> c) -> a -> b -> c
uncurry :: (a -> b -> c) -> (a, b) -> c
($)     :: (a -> b) -> a -> b

In other words,

f <*> a = uncurry ($) <$> f ** a

Now, conversely, in much more straightforward way,

unit   = pure ()
a ** b = (,) <$> a <*> b

where ((,) <$>) = fmap (,) :: f a -> f (b -> (a, b)) and (<*>) :: f (a -> b) -> f a -> f b, and hence applying the former to its argument, we get (,) <$> a :: f (b -> (a, b)), which sets the stage for <*>, taking just such a function, and then just another lifted value b :: f a, to produce a value of type f (a, b). And pure () is obvious.

As for the laws,

The Applicativeness of a Functor

What does it mean for a Functor instance to be applicative? To answer this question we need only consider the functions <*> and liftA2, which distinguish the class Applicative from the class Functor. In fact, pure is the trivial embedding, lifting, or the action of the corresponding free functor, i.e., only the minimal structure is superimposed on the argument to pure, which also justifies this name.³ The modern Haskell typeclass hierarchy for Monad goes Functor -> Applicative -> Monad. In every consecutive class we thus can use the methods of the respective predecessor.

So let’s scrutinize the behavior of <*> and liftA2 emanating from their type signatures, as this is the only information we can use in their implementation, in addition to the knowledge of the particular instantiated type constructor f such as Maybe or [].

<*>    :: Applicative f => f (a -> b) -> (f a -> f b)
liftA2 :: Applicative f => (a -> b -> c) -> (f a -> f b -> f c)

In liftA2 we immediately recognize the same pattern as in Functor’s fmap, albeit with one additional argument. In other words, liftA2, as the name suggests, lifts a binary function to the context of f. These naming inconsistencies should perhaps be addressed in future modernizations of the base library.

Now what does <*> approach? Let’s see, instead of a function a -> b we now have this type of function embedded in the context of f, and the result is the same f a -> f b. So while fmap lifts j : a -> b to fmap j :: f a -> f b, and liftA2 lifts k : a -> b -> c to liftA2 k :: f a -> f b -> f c, the ap operator <*> doesn’t really lift anything, but instead it applies this embedded function l : f (a -> b) by sort of extracting it from the context of f to get a function a -> b, and then lifting it via fmap. So can we just write something like…?

instance Applicative Maybe where
  pure x = Just x                        -- Trivial embedding. No structure-altering.

  Nothing     <*> Nothing  = Nothing     -- No function to apply.
  Nothing     <*> (Just x) = Nothing     -- Ditto.
  l@(Just l') <*> Nothing  = Nothing     -- No value to apply it to.
  l@(Just l') <*> (Just x) = Just (l' x) -- This is what we actually want.

or, more succinctly,

instance Applicative Maybe where
  pure = Just

  (Just l') <*> x = fmap l' x
  _         <*> _ = Nothing

since we know that any Applicative instance must be a Functor instance, and Maybe is such one, so we can use its fmap implementation. We use pure = Just because otherwise we’d map any x to Nothing or an arbitrary constant, which would contradict the notion of minimal structure imposition or freeness; this is also stipulated in an applicative law.

Does it type-check? It does! Does it satisfy the applicative functor laws? Let’s see…

So as you see, we can just use fmap to implement Applicative in this case. We almost always have to. This also emphasizes the minimality of addition of structures in the step from Functor to Applicative, and then to Monad, which we can also implement via fmap and <*> or liftA2.

If you’re wondering how we can obtain such a strange function k :: f (a -> b). Well, how about

fmap (+) :: (Num a, Functor f) => f a -> f (a -> a)

where f ~ [] and a ~ Int, which would result in

fmap (+) [1,2,3 :: Int]  ==  [(1+), (2+), (3+)]  ::  f (a -> b)  ~  [Int -> Int]

that is, a list of partially applied or sections of (+).

Alternatively, using the liftA2 definition of Applicative,

instance Applicative Maybe where
  pure = Just

  liftA2 k (Just a) (Just b) = Just (k a b)
  liftA2 _ _        _        = Nothing

The remaining questions are whether it type-checks and whether it satisfies the applicative laws.

And it’s easy to pass from <*> to liftA2 and vice versa. Indeed, given a definition in terms of <*>, (here we don’t know anything about the concrete structure of f, so we can only use pure and <*>)

liftA2 k x y = k <$> x <*> y

which is the “applicative pattern” and where in fact k :: a -> b -> c, (<$>) = fmap, (k <$>) :: f a -> f (b -> c), and x :: f a, y :: f b, whence k <$> x :: f (b -> c), so (k <$> x <*>) :: f b -> f c, which results in an f c value when applied to y.

And now, conversely, given a definition in terms of liftA2. Well, suppose we went by trial and error: it is neither of:

liftA2 fmap l (pure x)
  ==  liftA2 fmap . pure ::
liftA2 fmap        :: (Functor f, Applicative g) => g (a -> b) -> g (f a) -> g (f b)
liftA2 . fmap      ::             Appllcative g  => (c -> b) -> g (a -> c) -> (g a -> g b)
liftA2 . fmap pure ::             Applicative g  => (b -> c) -> (g a -> g b -> g c)

but it is simply

(<*>) = liftA2 id    ::             Applicative g  => g (b -> c) -> (g b -> g c)

where id :: s -> s with necessarily s ~ a ~ (b -> c) in liftA2.

Instances for the Reader, Writer, and State Monads

Let’s go a step further. Let’s in fact instantiate less obvious type constructors (,) (cf. Writer) and -> (cf. Reader), and even -> . (,) (cf. State). Indeed, essentially,

newtype Reader' r  = (->) r        -- == (r ->)
newtype Writer' w  = (,) w         -- == (e,)
newtype State' r w = (->) r ((,)w) -- == r -> (r,w)

The Applicative Pattern

Suppose we have an applicative functor af⁴, which could be any instance of the likes of Maybe, Either, [], (,), or ->. Now take a binary “pure” function f : a -> b -> c and a ternary “pure” function g :: a -> b -> c -> d. What do the following expressions mean?

f <$> x <*> y
g <$> x <*> y <*> z

Can you see that these are precisely liftA2 as defined above, and by trivial extension liftA3? Again, let’s infer the types step by step. First we have to recognize for these expressions to make sense and type-check, we must have x :: af a, y :: af b and z :: af c. Let’s proceed by stepwise exhaustion:

• (f <$>) == fmap f :: af a -> af (b -> c), for recall that f :: a -> t ~ (b -> c).
• (<$> x) :: (a -> b -> c) -> af b -> af c
• (f <$> x) :: af (b -> c)
• (f <$> x <*>) :: af b -> af c, for recall that (<*>) :: af (s -> u) -> (af s -> af u).
• f <$> x <*> y :: af c.

Exercise: Now it’s on you to do the same for g with three arguments. I strongly suggest you just do it. Choose pen and paper, your favorite editor, or run it in your mind⁵. Once you’ve automated this practice, you’ll become much faster in thinking Haskell, functional style, logic and type theory.⁶

Examples

time

One of the fundamental examples to using the applicative style, enabled by an Applicative and Functor instances for a data type, is the computation of times.

The time library provides several data types that deal with modeling the various notions of “time” and defines instances of Applicative for them. The library is sometimes quite confusing, often providing but a limited number of functions that meet your purpose. This spurred some activity among Haskell developers and led to a number of other APIs to dealing with the various notions of time.

The library provides a nice entry point to getting accustomed to the applicative style because we often need to parse strings of dates or times to programmatic representations, in other words, we need to have a way to go String -> Time, in a sense. But as is usual with parsing we virtually never can be certain in advance whether the input string---be it our own data, third-party data, or even more problematic arbitrary user input---conforms to the various ways of writing down dates and times. How can we know, for instance whether 01.12.2020 represents “January 12th, 2020” or rather “December 1st, 2020”. And how about 01.12.20? Is this “1920” or “2020”? All these simple but---without given context---ambiguous notations need somehow to be assessed and transformed to one and only programmatic representation, which enables further computations on it.

This parsing ambiguity can be dealt with in multiple ways. Typical parsers can be transparent in their procedures and fairly tell us that the result is uncertain, or they can arbitrarily discard what they deem ambiguous and give us just what the parser’s author believes might be of interest to us.

One typical result of parsing is Either String Result, which is equivalent to the pair data type (String, Result), and where the left value provides the error and the right the successful parse. Alternatively, we can fix the left component to a unit data type, with a single value Nothing, which will be the result of an error, without telling us what exactly went wrong, and Just Result, which gives the successful parse. We disambiguate the state of the parser by pattern matching on the constructors Left and Nothing, to wit,

data Either a b = Left a  | Right b
data Maybe  b   = Nothing | Just  b

Recall that a functor is modeled in Haskell as a unary type constructor f :: * -> *, with a single function fmap :: Functor f => (a -> b) -> (f a -> f b) that lifts a function g :: a -> b to a function fmap g :: f a -> f b, which acts in the “context” defined by f, and which satisfies the two conditions fmap id = id and fmap h . fmap g = fmap (h . g). Simply speaking, f is a sort of a fancy tag.

Now, as we’ve seen above, an applicative functor is modeled in Haskell as a functor augmented by the operator (<*>) :: Applicative f => f (a -> b) -> (f a -> f b), which lets us apply functions lifted to the context determined by f to lifted values x :: f a in the context of f.

In other words, a functor f transforms a regular function g :: a -> b to the lifted function fmap g :: f a -> f b in the context of f, i.e., it acts on lifted values f a in the context of f. In contrast to this, an applicative functor provides the operator <*>, which accepts a lifted function g :: f (a -> b) and lets it act on the lifted values f a.

Note that the notion of “lifting” of the argument function to the functor is different from the notion of “lifting” a function argument to the applicative functor. In the case of an ordinary Functor f, the function g :: a -> b is lifted to the context of f to act on lifted values f a, i.e., it is transformed into fmap g :: f a -> f b, whereas in the case of Applicative f, the argument function is expected to be of the lifted function type f (a -> b), and is then applied to the lifted values f a of the Applicative f. Recall that a typical common practical example is when f a = [a], the list functor, and we simply apply a list of functions, [a -> b], to a list of values, [a]. On the surface of this degree of abstraction, that distinction may seem subtle, but its repercussions are profound, as we have seen and will encounter very often.

Conveniently, if g :: a -> b -> c, which is the same as a -> (b -> c), then fmap g :: Functor f => f a -> f (b -> c). This is where <*> kicks in to enable the applicative style. Note that (g <$>) is just an operator equivalent to fmap g. Then the applicative-style expression

g <$> x <*> y

expects that x :: Functor f => f a, and hence g <$> x :: Functor f => f (b -> c), which is precisely what the operator <*> expects on its left-hand side, so the expression

(g <$> x <*>) :: f b -> f c

In other words, this is a function fmap h lifted to the context of Applicative f, where h :: b -> c. And all that is left to process is the argument y, which must be of type f b.

So much for the recap on the abstract side of applicative functors. Now let’s turn our attention to a practical example concerning the time package. For starters, let’s define a couple of values to process.

pTimeM x = parseTimeM True defaultTimeLocale "%H:%M" x :: Maybe TimeOfDay
let j = pTimeM "10:17"
let k = pTimeM "12:17"

parsed as 24-hour values. The type annotation is necessary here, because the result of parseTimeM is any FormatTime instance in any compatible monad (MonadFail to be precise), which is an ambiguity in the type system, and we are forced to specify just which monad we want; we could also have taken [] or IO, among the canonical instances, for example. We see here that j and k are lifted values, qualified by Maybe. Recall that Maybe is a Functor instance. This means we can write the functorial expression

timeOfDayToTime <$> k

and even an applicative-style expression such as

timeToTimeOfDay <$> ((-) <$> (timeOfDayToTime <$> k) <*> (timeOfDayToTime <$> j))

Outlook: Traversalble, Foldable, and Monad

Another way the nesting may occur is

traverse :: (Traversable t, Applicative f)
         => (a -> f b) -> t a -> f (t b)

The interplay here is between two different classes t and f.

Similarly,

join :: Monad m => m (m a) -> m a

This will become handy when we deal with monad transformers, which absent proper composition of monads, is a work-around.

Interestingly, a monad is given equivalently in terms of return, fmap and join, rather than return and bind (>>=), i.e., we need only to reconstruct the other operators in terms of the ones given. In one direction we need to reconstruct the bind operator from fmap (or liftM) and join. Indeed,

m (>>=) k = join $ fmap k m

This is relatively easy if we just follow the types. Indeed, we have m :: m a and k :: a -> m b, whence fmap k :: m a -> m (m b) and hence fmap k m :: m (m b), to which we apply join, which gives a value of type m b. That’s it.

There’s no difference between fmap and liftM here since every monad is a functor, so the instance is automatically dispatched correctly. More efficient implementation might however be provided locally for liftM.

This demonstrates that a monad given in terms of return, fmap and join implies a monad defined in terms of return and (>>=). To establish equivalence, we need to demonstrate the converse statement, namely that a monad given in terms of return and the bind operator implies a monad given in terms of return, fmap, and join. We also call such an equivalence a “characterization” of the object. We have left aside the monad laws, more on this in a dedicated post on my blog.

Now, conversely, given (>>=) :: m a -> (a -> m b) -> m b and return :: a -> m a, we want to implement the two functions

liftM :: (a -> b) -> m a -> m b
join  :: m (m a) -> m a

This too is quite straightforward, once one gets used to reasoning with types. First, note that liftM is just fmap specialized for Monad instances, which makes no particular difference with respect to using fmap with monads, as noted before. We can reconstruct fmap (or liftM) and join, for example, as follows,

liftM f a = a >>= return . f
join    a = a >>= id

Let’s discuss how we got there.

First of all, liftM takes a function f :: a -> b and a lifted value a :: m a, whereas the bind operator has type (>>=) :: m a -> (a -> m b) -> m b, so we can just take the second argument to liftM and pass it to the bind operator, which gives (a >>=) :: (a -> m b) -> m b, and we’re almost there; what’s left is a way to construct a Kleisli arrow from f :: a -> b and return :: a -> m a, but that’s apparent: we just compose them and get return . f :: a -> m b, and pass this Kleisli arrow as the second argument to the bind operator.

Now, as for join, it is very similar. Look join has type m (m a) -> m a and we can only use return and (>>=) to reconstruct it. What if we just passed the twice lifted argument a :: m (m a) to join directly to the bind operator? We would get (a >>=) :: (m a -> m b) -> m b, since the original first argument to (>>=), which is of type m a, now is m (m a), and the Kleisli arrow takes a value of one level of lifting fewer, i.e., given the first argument of type m (m a), the Kleisli arrow will operate on values of type m a, and result in a lifted value m b, as before, where b can be anything, including m (m (m c)) or whatever seems conceivable, within the bounds of Haskell’s type system, which are exceptionally wide. So, what can we get for m a -> m b? Well, we know that actually join :: m (m a) -> m a, and hence b ~ a, so we only need a Kleisli arrow of type m a -> m a, which trivially is the identity id :: m a -> m a in the monad m, nothing else would fit, as we proved before (there’s no specific information about what a might be, and the only way to pass a -> a---without thereby adding any constraints---is by identity). And therefore, a >>= id :: m a. That’s it.

Exercise: Retrace these two “proofs by chasing the arrows” a couple of times if you still feel uncertain about it. Don’t worry, once you get used to it, you won’t need pen and paper to follow, but the challenge will become to do the same with more complicated expressions, especially when defining your own monad instances. You’ll have a choice to define a monad in either of the ways, picking the one in which it is easier or more clear to express your data types. And you will always have the benefit of being able to rely completely on all the properties of these type classes that we have demonstrated, you can reuse them everywhere in your code. They’re universally true, regardless of the code, they are the properties of the type system, not your program. And that’s huge. You just may need to get used to it.

ApplicativeDo

Let’s now investigate some language extensions of GHC to Haskell2010, which facilitate the work with applicative functors.

First of all, imagine we wanted to validate some inputs. In case of an invalid piece of data, we represent the error at first by Nothing, for brevity. We could also simply short-circuit the result using Booleans. But we want to maintain semantic consistency.

data Credentials = Credentials { id :: Int, name :: String, password :: String }

validId          :: Id          -> Maybe Id
validName        :: Name        -> Maybe Name
validPassword    :: Password    -> Maybe Password
validCredentials :: Credentials -> Maybe Credentials
validCredentials c = case validId $ id c of
    Nothing  -> Nothing
    Just id' -> case validName $ name c of
        Nothing    -> Nothing
        Just name' -> case validPassword $ c password of
            Nothing        -> Nothing
            Just password' -> Just . Credentials $ id' name' password'

This ladder with a storey for each level in the nested dependence hierarchy is very typical. It is a heavy lexical burden and hence prone to error. Let’s change this. With standard Haskell2010 we can just write

validCredentials = Credentials <$> validId <*> validName <*> validPassword

With ApplicativeDo, we can resort to the imperative-style do-notation, which is syntactically a specialization, semantically a generalization of the monadic do-notation,

validCredentials c = do
  id'       <- validId c
  name'     <- validName c
  password' <- validPassword c
  return $ Credentials id' name' password'

which is just a syntactic construct that gets desugared into exactly the same applicative pattern as the one preceding this do block.

There are however certain limitations which we need to be aware of. First of all, monadic computations are sequenced in a do block, their order of evaluation matters but, on the other hand, the results may be bound to variables, which are just ad-hoc Kleisli arrows. In this applicative do-notation the order doesn’t matter, since this is just the desugared applicative-style syntax, and hence no expression following may depend on the result of a previous one; in contrast to monadic do, which models sequential computations, applicative style and hence applicative do notation models parallel computations, in that all computations are independent of one another.

In particular, we can’t use id' in the call to validName.

$$\begin{aligned} (u \otimes s * v \otimes t) * w \otimes r &\equiv us \odot vt \odot wr \\ &\equiv u \otimes s * (v \otimes t * w \otimes r). \end{aligned}$$

Thus the direct product $b^a \otimes a$ is in fact a semigroup with the operator $*$, if just $b$ is a semigroup. So we can expect that $Fb^a \otimes Fa$ also constitutes a semigroup.
Long story short, or sort of, it gets quite complicated if we go deeper and deserves a separate post, but the essence here is that pure must be “homomorphic” here in the sense that if $F = \mathtt{pure}$ is our functor defined on the direct products (as tensor products, think for simplicity on Cartesian products), then we assert $F(U \otimes a) = FU \otimes Fa$, where $U = b^a$, and the right-hand side is well-defined when $F$ is a functor, but what about the left-hand side? Either way, we take ($) as the operation on the left-hand side and <*> as the operation on the right-hand side, which in both cases represents lazily defined “thunks” prior to evaluation. In this sense the (free) functor pure must be homomorphic. So we assert that $\mathtt{pure}\, (u \otimes s) = (\mathtt{pure}\, u) \otimes (\mathtt{pure}\, s)$

Footnotes

1. What I’ve decided to dub here a “functorial function” is just the image $u = Fg : Fa \to Fb$ of the morphism under the functor $F$, where $g : a \to b$ ↩

2. In Haskell community, this property is usually called “homomorphism.” But the term “homomorphism” has meaning only in the context of a particular structure that it preserves. What is this structure here? It could also be referred to as “applicative homomorphy,” amounting to the assertion that the function application operator ($) is a “homomorphism,” but again of what structure? So, in the Applicative context f in which pure freely embeds a function u :: a -> b is a good candidate.
   Let’s recall what a “homomorphism” of semigroups $(S,*)$ and $(T,\circledast)$ is: $\phi(x * y) = \phi x \circledast \phi y$, for all $x,y$ in $S$ . And here in Haskell now, pure u <*> pure x = pure (u x). If $\phi = \mathtt{pure}$, then we assert that $\phi u \mathtt{<*>} \phi x = \phi (ux)$. But $u$ and $x$ do not belong to the same semigroup, in general.
   Therefore, these must be different pure functions. Indeed, due to its polymorphy, the former acts on functions a -> b while the latter on values of type a. Assuming type consistency, these are two distinct types, and hence also sets.
   What kind of structures do we want to preserve that functorial application <*> is the operation in one of them, while the ordinary function application $ is the operation in the other (u x == u $ x)?
   How about a direct product of pairs semigroups? For $, we take the direct product $U \otimes a$, where $U = b^a$, i.e., the “semigroup” of functions $a \to b$, but with what semigroup operation, given that the semigroup operation of the direct product must be $? At the same time, for <*>, we take the lifted semigroups along the given functor f. Does the informal expression <*> = F ($), where $F$ describes our f, then have any sense?
   Obviously, unless $b\subseteq a$, the set $b^a$ cannot constitute a semigroup with composition. So let $a$ denote any set and ($b$,$\odot$) any semigroup, take the direct product $S := b^a \otimes a$ and denote $* : S \times S a \to s$ the supposedly semigroup operation on $S$, which maps elements $u \otimes s$ and $v \otimes t$, denoting the lazy thunks u $ s and v $ t prior to evaluation, to a combined thunk denoting the lazy evaluation of $u s \odot v t$ in the semigroup $b$, which defines what it means to combine the results of the evaluation of the values $us$ and $vt$ in $b$. This is a somewhat imprecise justification of well-definedness of $*$, without diving deep into lazy evaluation in Haskell. But we can show rigorously that $*$ is associative. Indeed, we can simply delegate to the semigroup operation of $b$: ↩

3. Due to historical peculiarities, some syntactic limitations were introduced to Haskell, which resulted in a lack of namespace isolation of modules, and hence require us to distinguish, e.g., between pure for Applicative and return for Monad, which was superseded by a more accurate hierarchy, so return = pure now by default, similarly to ++ = mconcat = <> by default, where the latter is the semigroup operation. ↩

4. The seemingly arbitrary choice of names for syntactic entities is a very good exercise to peel off mnemonics and get to the core of the notion. Only by understanding the abstraction do we become capable of utilizing it to the full extent. This is by no means an immediate achievement, but takes time and requires practice. So I suggest you vary the names on your learning codebase. It is certainly completely different when working on mainline codebases, intended for others to clearly and quickly understand your intentions. ↩

5. Type inference is always a good exercise. It is essentially just structural induction. A strong ↩

6. There is a wonderful connection between logic and types, as formalized in the Curry—Howard correspondence. Roughly, having a formal proof is equivalent to having a type-checking program. I will introduce a blog series on this topic later. It is incredibly fascinating. ↩