Applicative functors

What if we need to apply a binary function to values from two lists? A C++ programmer would write a binary function or lambda and pass it to the chosen traversal algorithm. In Haskell, $\mathtt{(+)}$ is curried: after receiving one argument, it returns a function waiting for the second. If we map $\mathtt{(+)}$ over the first list, we get not sums but a list of partially applied functions: $\mathtt{fmap\;(+)\;[1,2,3]}$ has type $\mathtt{Num\;a}$ $\Rightarrow \mathtt{[a \to a]}$. In other words, the functions are now inside the list context.

An ordinary $\mathtt{Functor}$ can apply a function $\mathtt{a \to b}$ to values in $\mathtt{f\;a}$, but it cannot apply functions from $\mathtt{f\;(a \to b)}$ to values from another $\mathtt{f\;a}$. That requires a stronger type class: $\mathtt{Applicative}$ and its $(\mathbin{\mathtt{<*>}})$ operator.

The $\mathtt{Applicative}$ class extends $\mathtt{Functor}$ with two operations:

class Functor f => Applicative f where
  pure  :: a -> f a                  -- put a plain value into a context
  (<*>) :: f (a -> b) -> f a -> f b  -- apply a function from a context

In this declaration, $\mathtt{f}$ is a type constructor of kind $\mathtt{* \to *}$. The $\mathtt{pure}$ operation puts a plain value into a context, while $(\mathbin{\mathtt{<*>}})$ applies a function in a context to a value in the same context. Each instance defines the concrete semantics of these operations. The standard instances for lists and $\mathtt{Maybe}$ work as follows:

instance Applicative [] where
  pure x    = [x]
  fs <*> xs = [g x | g <- fs, x <- xs]

instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  Just g  <*> x = fmap g x

Just (+3) <*> Just 2   -- Just 5

Lifting is an important idea for applicative functors: an ordinary function of several arguments is “lifted” into a context so that it accepts arguments in contexts and returns its result in the same context. $\mathtt{liftA2}$ lifts a binary function, while $\mathtt{liftA3}$ lifts a ternary function:

liftA2 (+)
  (Just 2)
  (Just 3)
-- Just 5

liftA3 (\x y z -> x + y + z)
  (Just 1)
  (Just 2)
  (Just 3)
-- Just 6

There are four laws, and programmers are responsible for obeying them: an implementation may pass type checking while still breaking the laws. After defining an instance, we therefore need to verify all four conditions:

pure id <*> v == v                             -- identity

pure g <*> pure x == pure (g x)                -- homomorphism (a structure-preserving mapping)
u <*> pure y == pure ($ y) <*> u               -- interchange
pure (.) <*> u <*> v <*> w == u <*> (v <*> w)  -- composition

The laws ensure that $\mathtt{pure}$ introduces no extra effect, contextual application agrees with ordinary function application, and regrouping a chain of $(\mathbin{\mathtt{<*>}})$ does not change its result. They do not, however, permit effects to be reordered arbitrarily: order may still matter.

A couple of list examples, perhaps:

-- Every function is applied to every value
[(+1), (*2)] <*> [10, 20]
-- [11, 21, 20, 40]

-- Partially applied addition: again, all combinations
(+) <$> [1, 2] <*> [10, 20]
-- [11, 21, 12, 22]