Applicative functor

Headline

A functor with function application within the functor

Description

Applicative functors are described here briefly in Haskell's sense.

The corresponding type class (modulo some simplifications) looks as follows.

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

The expectation is that pure promotes a value to a functorial value whereas "<*>" can be seen as a variation of fmap such that a function within the functor (as opposed to just a plain function) is applied to a functorial value.

The following laws are assumed.

pure f <*> x = fmap f x
pure id <*> v = v
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u

Illustration

Simple examples

We make Maybe and lists applicative functors:

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

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

Thus, in the Maybe case, a Nothing as a function makes us return a Nothing as result, but if the function is available then it is fmapped over the argument. In the list case, we use a list comprehension to apply all available functions too all available values.

The instances can be exercised at the Haskell prompt as follows:

> Just odd <*> Just 2
Just False
> [odd, even] <*> [1,2,3,4]
[True,False,True,False,False,True,False,True]

To see that applicative functors facilitate function application for functorial values pretty well, consider the following functorial variation on plain function application.

(<$>) :: Functor f => (a -> b) -> f a -> f b
f <$> x = fmap f x

Consider the following application.

> (+) <$> [1,2] <*> [3,4]
[4,5,5,6]

Thus, the applicative operator "<*>" is used to line up (any number of) functorial arguments and fmap is used for the "rest" of the application.

A more advanced example

We will use now an applicative functor to support environment passing within a recursive computation.

Consider the following interpreter for simple expressions:

data Exp
  = Var String
  | Val Int
  | Add Exp Exp

-- Environments with a fetch (lookup) function
type Env = [(String, Int)]
fetch x ((y,v):n) = if x==y then v else fetch x n

-- Straightforward interpreter; we take care of environment passing
eval :: Exp -> Env -> Int
eval (Var x) n = fetch x n
eval (Val v) _ = v
eval (Add e1 e2) n = eval e1 n + eval e2 n

We can evaluate expressions like this:

> eval (Add (Var "x") (Val 22)) [("x", 20)]
42

Let's try to switch to a more combinatorial style such that we abstract from explicit environment passing. To this end, we leverage the so-called SKI combinators:

-- More point-free, combinatorial interpreter hiding some environment passing
eval' :: Exp -> Env -> Int
eval' (Var x) = fetch x
eval' (Val v) = k v
eval' (Add e1 e2) = k (+) `s` eval' e1 `s` eval' e2

-- https://en.wikipedia.org/wiki/SKI_combinator_calculus
i :: a -> a
i x = x -- aka id
k :: a -> b -> a
k x y = x -- aka const
s :: (a -> b -> c) -> (a -> b) -> a -> c
s x y z = x z (y z) -- aka <*> of applicative

The applicative functor for the instance "(->) a" provides exactly the necessary abstraction:

-- Switch to applicative functor style, thereby demonstrating a general pattern
eval'' :: Exp -> Env -> Int
eval'' (Var x) = fetch x
eval'' (Val v) = pure v
eval'' (Add e1 e2) = pure (+) <*> eval'' e1 <*> eval'' e2