What does "applicative" mean?

Question

When reading stuff on Haskell, I sometimes come across the adjective "applicative", but I have not been able to find a sufficiently clear definition of this adjective (as opposed to, say, Haskell's Applicative class). I would like to learn to recognize a piece of code/algorithm/data structure, etc. that is "applicative", just like I can recognize one that is "recursive". Some contrasting examples of "applicative" vs. whatever the term intends to draw a distinction from (which I hope is something more meaningful in its own right than "non-applicative") would be much appreciated.

Edit: for example, why was the word "applicative" chosen to name the class, and not some other name? What is it about this class that makes the name Applicative such a good fit for it (even at the price of its obscurity)?

Thanks!

Answer 1

It's not clear what "applicative" is being used to mean without knowing the context.

If it's truly not referring to applicative functors (i.e. Applicative), then it's probably referring to the form of application itself: f a b c is an applicative form, and this is where applicative functors get their name from: f <$> a <*> b <*> c is analogous. (Indeed, idiom brackets take this connection further, by letting you write it as (| f a b c |).)

Similarly, "applicative languages" can be contrasted with languages that are not primarily based on the application of function to argument (usually in prefix form); concatenative ("stack based") languages aren't applicative, for instance.

To answer the question of why applicative functors are called what they are in depth, I recommend reading Applicative programming with effects; the basic idea is that a lot of situations call for something like "enhanced application": applying pure functions within some effectful context. Compare these definitions of map and mapM:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
mapM _ [] = return []
mapM f (x:xs) = do
  x' <- f x
  xs' <- mapM f xs
  return (x' : xs')

with mapA (usually called traverse):

mapA :: (Applicative f) => (a -> f b) -> [a] -> f [b]
mapA _ [] = pure []
mapA f (x:xs) = (:) <$> f x <*> mapA f xs

As you can see, mapA is much more concise, and more obviously related to map (even more so if you use the prefix form of (:) in map too). Indeed, using the applicative functor notation even when you have a full Monad is common in Haskell, since it's often much more clear.

Looking at the definition helps, too:

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

Compare the type of (<*>) to the type of application: ($) :: (a -> b) -> a -> b. What Applicative offers is a generalised "lifted" form of application, and code using it is written in an applicative style.

More formally, as mentioned in the paper and pointed out by ertes, Applicative is a generalisation of the SK combinators; pure is a generalisation of K :: a -> (r -> a) (aka const), and (<*>) is a generalisation of S :: (r -> a -> b) -> (r -> a) -> (r -> b). The r -> a part is simply generalised to f a; the original types are obtained with the Applicative instance for ((->) r).

As a practical matter, pure also allows you to write applicative expressions in a more uniform manner: pure f <*> effectful <*> pure x <*> effectful as opposed to (\a b -> f a x b) <$> effectful <*> effectful.

Answer 2

On a more fundamental level one could say that "applicative" means working in some form of the SK calculus. This is also what the Applicative class is about. It gives you the combinators pure (a generalization of K) and <*> (a generalization of S).

Your code is applicative when it is expressed in such a style. For example the code

liftA2 (+) sin cos

is an applicative expression of

\x -> sin x + cos x

Of course in Haskell the Applicative class is the main construct for programming in an applicative style, but even in a monadic or arrowic context you can write applicatively:

return (+) `ap` sin `ap` cos

arr (uncurry (+)) . (sin &&& cos)

Whether the last piece of code is applicative is controversial though, because one might argue that applicative style needs currying to make sense.