Applicative

An applicative functor is a functor $F$ with two further operations, $pure : a \to F a$ and $⊛ : F (a \to b) \to F a \to F b$ (written <*>), that combine independent computations, satisfying four laws. It sits between functors and monads: every monad is applicative, but not every applicative is a monad. Because each step's computation is fixed before any of them runs, an applicative computation can collect every error, run its parts in parallel, or be inspected before it is run, none of which a monadic one can.

§ 01

Overview

A functor maps a function of one argument over a structure. Mapping a function of two arguments over two structures needs more: fmap f a gives a structure of functions, and something has to apply those to the values in the second structure. That is $⊛$ :

map2 f a b = pure f ⊛ a ⊛ b

and the same pattern lifts a function of any number of arguments. What "apply" means depends on the functor. For option the result exists only if both arguments do. For lists every function meets every argument, giving all combinations. For functions $r \to a$ both are applied to the same $r$ .

pure and ap for option, lists (all combinations), zipped lists (pointwise), and functions.

(* pure and ap for option and list; map2 and product follow. *)
module Option_a = struct
  let pure x = Some x
  let ap mf mx = match (mf, mx) with Some f, Some x -> Some (f x) | _ -> None
  let map2 f a b = ap (ap (pure f) a) b
end
 
module List_a = struct
  let pure x = [ x ]
  (* every function applied to every argument *)
  let ap fs xs = List.concat_map (fun f -> List.map f xs) fs
  let map2 f a b = ap (ap (pure f) a) b
end
 
(* The zip applicative: same functor as lists, different combination. *)
module Zip_a = struct
  let ap fs xs = List.map2 (fun f x -> f x) (List.filteri (fun i _ -> i < List.length xs) fs)
                            (List.filteri (fun i _ -> i < List.length fs) xs)
  let map2 f a b = ap (List.map f a) b
end
 
(* Functions out of a fixed type: pure is K and ap is S. *)
module Fun_a = struct
  let pure x = fun _ -> x
  let ap f g = fun r -> f r (g r)
end

Running it.

Option_a.map2 ( + ) (Some 1) (Some 2)   ->  Some 3
Option_a.map2 ( + ) (Some 1) None       ->  None
List_a.map2 ( + ) [1; 2] [10; 20]       ->  [11; 21; 12; 22]
Zip_a.map2 ( + ) [1; 2] [10; 20]        ->  [11; 22]
Fun_a: (fun s n -> s / n) <$> sum <*> length  applied to [2; 4; 9]  ->  5

Lists have two lawful applicative instances with the same map: the cartesian one and the zipping one. The zipping one's pure has to be an infinite list, so that it can be zipped with a list of any length, which is why Haskell's ZipList needs laziness and why the OCaml version above leaves it out. For functions, pure is the K combinator and $⊛$ is S: $pure x = λ r . x$ and $(f ⊛ g) r = f r (g r)$ , exactly the SKI combinators.

§ 02

Definition

An applicative functor is a functor $F$ with

pure : a \to F a ⊛ : F (a \to b) \to F a \to F b

Laws

pure id ⊛ v pure (\circ) ⊛ u ⊛ v ⊛ w pure f ⊛ pure x u ⊛ pure y = v = u ⊛ (v ⊛ w) = pure (f x) = pure (λ f . f y) ⊛ u identity composition homomorphism interchange

Together they say that pure adds no effect and that the effects of a combination happen in the order the arguments are written, independently of the functions being applied. A consequence is that any expression built from pure and $⊛$ can be put in the canonical form $pure f ⊛ a_{1} ⊛ \dots ⊛ a_{n}$ : the pure function first, then the effects in order^[1]. The functor's map is $fmap f x = pure f ⊛ x$ .

The four laws for the list applicative on random lists and functions.

(* The four applicative laws for the list applicative, on random inputs. *)
let pure x = [ x ]
let ap fs xs = List.concat_map (fun f -> List.map f xs) fs
let compose f g x = f (g x)
 
let () = Random.init 11
let rand_list () = List.init (Random.int 4) (fun _ -> Random.int 20)
let rand_fns () = List.init (Random.int 3) (fun _ -> let k = Random.int 5 in fun x -> (x * 3) + k)
 
let identity () = let v = rand_list () in ap (pure Fun.id) v = v
let composition () =
  let u = rand_fns () and v = rand_fns () and w = rand_list () in
  ap (ap (ap (pure compose) u) v) w = ap u (ap v w)
let homomorphism () = let x = Random.int 20 and f = fun x -> x * x in ap (pure f) (pure x) = pure (f x)
let interchange () = let u = rand_fns () and y = Random.int 20 in ap u (pure y) = ap (pure (fun f -> f y)) u

Running it.

identity      holds on 10000 random cases
composition   holds on 10000 random cases
homomorphism  holds on 10000 random cases
interchange   holds on 10000 random cases

Monoidal form

An equivalent definition replaces $⊛$ by a product:

unit : F () ⋆ : F a \times F b \to F (a \times b)

associative and unital up to the isomorphisms $(a \times b) \times c ≅ a \times (b \times c)$ and $() \times a ≅ a ≅ a \times ()$ . The two are interdefinable:

u ⋆ v = fmap (λ x . λ y . (x, y)) u ⊛ v u ⊛ v = fmap (λ (f, x) . f x) (u ⋆ v)

This form is often easier to implement and makes the structure plain: an applicative is a way of pairing up two structures of the same shape. It is also the form OCaml's syntax uses.

§ 03

Notation

Haskell writes f <$> a <*> b <*> c, with <$> for fmap; McBride and Paterson called such expressions idioms and proposed brackets for them^[1]. Haskell's ApplicativeDo extension lets do-notation desugar to applicative operations when no step uses an earlier result.

OCaml's binding operators have a form made for applicatives. With let+ defined as map and and+ as the product,

let + x = a and + y = b in e = map (λ (x, y) . e) (a ⋆ b)

Every bound expression is evaluated independently of the others, and the body sees all their results^[8].

§ 04

Examples

Validation

The standard example of an applicative that is not a monad. A validation either succeeds or holds a list of errors, and the product of two failures keeps both lists:

Validating an order with let+ and and+, and the same checks with Result.bind.

type 'a validation = Ok of 'a | Errors of string list
 
let map f = function Ok x -> Ok (f x) | Errors e -> Errors e
let product a b =
  match (a, b) with
  | Ok x, Ok y -> Ok (x, y)
  | Errors e, Ok _ | Ok _, Errors e -> Errors e
  | Errors e1, Errors e2 -> Errors (e1 @ e2)
 
(* OCaml's binding operators for applicatives: let+ is map, and+ is product. *)
let ( let+ ) x f = map f x
let ( and+ ) = product
 
let nonempty field s = if s = "" then Errors [ field ^ " is empty" ] else Ok s
let natural field s =
  match int_of_string_opt s with Some n when n >= 0 -> Ok n | _ -> Errors [ field ^ " is not a natural number" ]
 
type order = { item : string; quantity : int; customer : string }
 
let order ~item ~quantity ~customer =
  let+ item = nonempty "item" item
  and+ quantity = natural "quantity" quantity
  and+ customer = nonempty "customer" customer in
  { item; quantity; customer }
 
(* The same checks with Result.bind stop at the first failure. *)
let order_monadic ~item ~quantity ~customer =
  let ( let* ) = Result.bind in
  let check = function Ok x -> Stdlib.Ok x | Errors e -> Stdlib.Error e in
  let* item = check (nonempty "item" item) in
  let* quantity = check (natural "quantity" quantity) in
  let* customer = check (nonempty "customer" customer) in
  Stdlib.Ok { item; quantity; customer }

Running it. The applicative version reports every problem; the monadic one stops at the first.

applicative  ->  item is empty; quantity is not a natural number; customer is empty
monadic      ->  item is empty

No lawful monad can behave like the applicative here. With $> > =$ the check on quantity is a function of the result of the check on item, and when that check failed there is no result to call the function with. The product receives both checks up front, and can keep both failures.

Parsers

Parser combinators built from pure and $⊛$ alone describe a context-free grammar whose structure is known before any input is read, which parsers can use to compute lookahead sets and recover from errors^[4]. A monadic parser can choose its next parser from a value it has parsed, which is more expressive and cannot be analysed ahead of time. See parser combinators.

Static structure

Because an applicative computation's shape does not depend on any result, it can be examined without running it. A form built from fields knows which fields it needs:

A form description whose list of fields is computed without any input.

(* A form description that knows its fields before it is run: possible
   because an applicative's structure does not depend on parsed values. *)
type 'a form = { fields : string list; parse : (string * string) list -> 'a option }
 
let field name = { fields = [ name ]; parse = (fun input -> List.assoc_opt name input) }
let pure x = { fields = []; parse = (fun _ -> Some x) }
let map f a = { a with parse = (fun i -> Option.map f (a.parse i)) }
let product a b =
  { fields = a.fields @ b.fields;
    parse = (fun i -> match (a.parse i, b.parse i) with Some x, Some y -> Some (x, y) | _ -> None) }
let ( let+ ) x f = map f x
let ( and+ ) = product
 
let signup =
  let+ user = field "user"
  and+ email = field "email"
  and+ plan = field "plan" in
  Printf.sprintf "%s <%s> on %s" user email plan

Running it.

signup.fields  ->  [user; email; plan]   (known without any input)
signup.parse   ->  ada <[email protected]> on pro

Larger systems use the same property. Facebook's Haxl data-fetching library batches and deduplicates the requests in the independent parts of an applicative expression^[2]. In build systems, applicative tasks have dependencies known before any task runs, while monadic tasks can discover them as they go^[3].

§ 05

Traversals

A traversable structure is one whose elements can be visited in order while an applicative effect is accumulated:

traverse : (a \to F b) \to T a \to F (T b) sequence = traverse id

Only the applicative operations are needed, which is why traverse works for validations and zipped lists as well as for monads. For option it fails if any element fails; for lists, sequence of a list of lists is their cartesian product.

traverse for lists, written once for any applicative passed to the functor.

(* traverse for lists, written once for any applicative given as a module. *)
module type APPLICATIVE = sig
  type 'a t
  val pure : 'a -> 'a t
  val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
end
 
module Traverse (A : APPLICATIVE) = struct
  let traverse f xs = List.fold_right (fun x acc -> A.map2 List.cons (f x) acc) xs (A.pure [])
  let sequence xs = traverse Fun.id xs
end
 
module T_option = Traverse (struct
  type 'a t = 'a option
  let pure x = Some x
  let map2 f a b = match (a, b) with Some x, Some y -> Some (f x y) | _ -> None
end)
 
module T_list = Traverse (struct
  type 'a t = 'a list
  let pure x = [ x ]
  let map2 f a b = List.concat_map (fun x -> List.map (f x) b) a
end)

Running it.

T_option.traverse int_of_string_opt ["4"; "8"]   ->  Some [4; 8]
T_option.traverse int_of_string_opt ["4"; "x"]   ->  None
T_list.sequence [[1; 2]; [3]; [4; 5]]             ->  [[1; 3; 4]; [1; 3; 5]; [2; 3; 4]; [2; 3; 5]]

Traversals satisfy laws of their own, which say that visiting every element exactly once is the only thing traverse can do^[5].

§ 06

Relation to functors and monads

Each abstraction adds one capability. A functor maps over one structure. An applicative combines several structures whose effects are all fixed in advance. A monad also lets the next computation depend on the result of the previous one. Every monad gives an applicative:

pure = return m f ⊛ m x = m f > > = λ f . m x > > = λ x . return (f x)

but validation and zipped lists are applicatives with no compatible monad. The extra power of $> > =$ is paid for by losing everything that depends on knowing the structure in advance: static analysis, batching, parallel execution and error accumulation. Lindley, Wadler and Yallop compared the three precisely: idioms are "oblivious" to earlier results, arrows "meticulous" and monads "promiscuous"^[6].

§ 07

Category theory

In category theory an applicative functor is a lax monoidal functor with a strength, on a category with finite products. Lax monoidal means there are maps

η : 1 \to F 1 ϕ_{A, B} : F A \times F B \to F (A \times B)

natural in $A$ and $B$ and compatible with the associativity and unit isomorphisms of the product^[7]. These are the unit and product of the monoidal form above. The strength, which lets a value from outside the functor be paired with one inside it, is automatic for functors on the category of types and functions, which is why the programming definition does not mention it.

§ 08

History

McBride and Paterson introduced applicative functors in a paper circulated from 2005 and published in 2008, under the name idioms^[1]; the pattern had appeared earlier in parser combinator libraries^[4]. Haskell's standard library made Applicative a superclass of Monad in 2015, so every monad must now define the applicative operations as well.