# Applicative functors: definition and syntax

In a recent blog post, Edward Z. Yang talks about applicative functors [3]. He mentions two equivalent definitions of applicative functors - the standard definition used in Haskell libraries (`Applicative`) and an alternative that has been also presented in the original paper [1], but is generally less familiar (`Monoidal`).

The standard definition makes a perfect sense with the standard uses in Haskell, however I always preferred the alternative definition. Edward uses the alternative (`Monoidal`) definition to explain the laws that should hold about applicative functors and to explain commutative applicative functors, but I think it is even more useful.

The `Monoidal` definition fits nicely with a trick that you can use to encode applicative functors in C# using LINQ [6] and I also used it as a basis for an F# syntax extension that allows writing code using applicative functors in a similar style as using monads (which is discussed in my draft paper about writing abstract computations in F# [5]). And I also think that commutative applicative functors deserve more attention.

## Alternative definitions

### Applicative

Let's start with the definitions. If you want to define an applicative functor in Haskell, you need to define the following operations (I'll be using the F# syntax, but the idea is the same):

```val pure  : 'T -> F<'T>
val (<*>) : F<'T1 -> 'T2> -> F<'T1> -> F<'T2>```

The definition explains why applicative functors are called applicative in Haskell and it also suggests their usual use. When we have some function `f` and effectful arguments `a1`, `a2` and `a3`, we can can use the combinators and apply the function as follows:

`(pure f) <*> a1 <*> a2 <*> a3`

This is an extremely useful for programming in Haskell, but it gives one specific presentation of the idea.

### Monoidal

The alternative definition (which is equivalent to the first one) uses the following operations (in Haskell, the `map` operation is a part of `Functor` type class, but since we do not have type classes in F#, I'll write all the operations explicitly):

```val map    : ('T1 -> 'T2) -> (F<'T1> -> F<'T2>)
val unit   : F<unit>
val ( ** ) : F<'T1> -> F<'T2> -> F<'T1 * 'T2>```

The `unit` value is essentially the same as the `pure` function in the previous definition (in terms of effects, they both create effect-free computations, with the only difference being that `pure` contains specified value and `unit` contains values of the `unit` type -- using `map`, you can easily turn `unit` into `pure`).

However, the `**` operator (which call merge) is more interesting. It says that if we have multiple computations with different effects (or other non-standard computational properties), we can combine the values and, at the same time, combine the effects (properties).

When talking about effects and IO, this operation simply combines the effects. However, when we take lists, this operation behaves as `zip`. One possible interpretation is that we're writing data-flow computations and list contains past values. In that interpretation, merge combines n past values of the first argument with m past values of the second argument and the result is min(n, m) past tuples. Interestingly enough, Uustalu and Vene use exactly this operation in their comonadic model of data-flow computations [9]. That's out of the scope of this blog post, but it is an interesting point (they use commutative merge operation).

The typical use of this interface is in some sense reversed when compared to the previous one. If we have a number of computations `c1`, `c2` and `c3`, we can combine them and then perform some computation with the resulting tuple:

```c1 ** c2 ** c3 |> map (fun (a1, (a2, a3)) ->
f a1 a2 a3 ) ```

I could use `map` and `**` in a similar style as `<*>` and `pure` (with a couple of `uncurry` combinators etc.), but the different style is intentional, because I think that the second definition is more suited for the explicit (as opposed to point-free) programming style.

Perhaps another analogy is possible here. There are two analogies when explaining monads (and they also apply to applicative functors). The first treats `F<'T>` as a "box" that wraps value `'T` and the second treats `F<'T>` as a "computation" that produces `'T`.

• The `Applicative` definition fits better with the "box" analogy. We write applicative style code as usual, and additional combinators make sure the boxes are handled correctly.

• The `Monoidal` definition fits better with the "computations" analogy. We compose computations, bind the results to variables (`a1`, `a2` and `a3`) and then continue computing.

## Alternative syntax

So far, I tried to informally explain the difference between two definitions. Indeed, the definitions are equivalent, so mathematically speaking, there is no difference. However, I believe thay supply different intuitions and suggest different use. In this section, I'll talk about the syntactic support for applicative functors that Haskell and (a research extension of) F# have.

The original paper on applicative functors proposes a syntax that simplifies programming with applicative functors (see also idiom brackets in She [2]). When you write:

`(| f a1 .. an |) `

The syntax is desugared to:

`(pure f) <*> a1 <*> .. <*> an`

This is a nice and useful simplification if you're using the applicative style. It even more clearly highlights the intuition that applicative functors are useful for writing code where we apply some function to an effectful arguments (values in "boxes") and want to propagate the effects (deal with the boxes).

It is also worth mentioning that this syntax is completely different from the notations that Haskell supports for working with other similar abstractions, most notably the `do` notation and also monad comprehensions.

### Computation syntax for F#

In a recent paper that I wrote with Don Syme [5], I tried to design a syntax for applicative functors that would match with the rest of F# computation expressions. As discussed in the paper, F# computation expressions can be used for a wider range of abstractions., but if we work with monads, they look pretty similar to `do` in Haskell. Assuming `m` is a computation builder for a monad and `f : int -> M<int>`, we can write:

```m { let! a = f 42
let! b = f a
return a + b }```

We can use a very similar style of syntax for working with applicative functors. Assuming `a` is a computation builder for applicative syntax and `g : int -> F<int>`, we can write:

```a { let! a = g 42
and  b = g 43
return a + b }```

You can find more details about the syntax in the paper [5], but here are the key points:

• The body of computation expression (in `{ .. }`) can have only one parallel binding block consisting of `let! .. and .. and ..`. This defines the computations that are combined using the merge operation (the `**` operator)

• The defined variables are not mutually recursive, so it is not possible to use, for example, the variable `a` in `g 43`. This is where my above example differs for monads and applicative functors.

• The code block following the parallel binding can contain other non-applicative `let` bindings, as well as other standard constructs (like `if`), but it cannot contain any more `let!` and it has to end with `return`.

I think the syntax nicely demonstrates the difference between monads and applicative functors (and explains in what way is monad more powerful). To quote the original applicative functors paper (Section 5):

Intuitively, [a monad] allows the value returned by one computation to influence the choice of another, whereas [applicative functor] keeps the structure of a computation fixed, just sequencing the effects.

This is exactly describing the limitation of the `let! .. and .. and ..` syntax. The value of a variable cannot affect what (applicative) computations are evaluated as part of the computation. They have to be specified at once and are always all evaluated. On the other hand, with monads in F#, we can write `let!` followed by `if` and then have another `let!` only in one branch (in which case, the nested computation may or may not be evaluated).

### Realistic example

There is a number of examples where the applicative programming style (and the idiom bracket syntax) make a good sense. So are there also some good examples where the explicit style that treats applicative functors as computations makes sense? Perhaps the best example I can think of are formlets [4] - a computation type that represents HTML forms:

```let userInfo =
form { let! name = textBox "name"
and surname = textBox "surname"
let combined = name + " " + surname
let message = "Your name is " + combined
return message }```

The example builds a form that generates two HTML textbox elements, asking for name and surname. When processed, the form returns a message of the form "Your name is First Last". I do not want to go into details, but you can find more (including a live browser-hosted example that works on Mac and Windows) on the try joinads web site [8].

## Summary

I hope this article provided some more evidence that the alternative definition of applicative functors (the `Monoidal` type class) is useful. As Edward pointed out [3], it makes it easier to understand the laws. This is even more the case with the syntax that I proposed for F# above - commutative applicative functor allows you to reorder the bindings in the `let! .. and .. and ..` block.

I believe that, intuitively, the `Applicative` definition is more natural when we treat values `F<'T>` as boxed values of type `'T` and want to work with them as if they were just `'T` values. However, if we treat them as computations returning `'T`, then the other definition might be more natural. It describes the operations that can be done with the computations and also leads to an interesting syntax (which I implemented for F#) and which relates applicative functors to monads.

Finally, the merge operation (`**` operator) of type `F<'T1> * F<'T2> -> F<'T1 * 'T2>` is quite interesting, because it appears in a number of places. Aside from applicative functors, it is used in comonadic model of data-flow [9] and it is also used in monad comprehensions as a generalization of `zip` (see my Monad.Reader article [7], Section 2.5)

### References

val f : int -> string -> float -> 'a

Full name: Blog.f

An applicative functor structure
val a : int
type: int
inherits: System.ValueType
Multiple items
val int : 'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type: int<'Measure>
inherits: System.ValueType

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int
type: int
inherits: System.ValueType
val b : string
type: string
Multiple items
val string : 'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
type: string
val d : float
type: float
inherits: System.ValueType
Multiple items
val float : 'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
type: float<'Measure>
inherits: System.ValueType

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float
type: float
inherits: System.ValueType
val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
type F<'T> = | FC of 'T

Full name: Blog.F<_>
type: F<'a>
union case F.FC: 'T -> F<'T>
val a1 : F<int>

Full name: Blog.a1
type: F<int>
val a2 : F<string>

Full name: Blog.a2
type: F<string>
val a3 : F<float>

Full name: Blog.a3
type: F<float>
val c1 : F<int>

Full name: Blog.c1
type: F<int>
val c2 : F<string>

Full name: Blog.c2
type: F<string>
val c3 : F<float>

Full name: Blog.c3
type: F<float>
val pure : 'T -> F<'T>

Full name: Blog.pure
val a : 'T
val f : F<('T1 -> 'T2)>
type: F<('T1 -> 'T2)>
val a : F<'T1>
type: F<'T1>
val a : 'a
val b : 'b
val map : ('a -> 'b) -> F<'a> -> F<'b>

Full name: Blog.map
val f : ('a -> 'b)
type Formlet<'T> = | FR of string list * (Map<string,string> -> 'T)

Full name: Blog.Formlet<_>
union case Formlet.FR: string list * (Map<string,string> -> 'T) -> Formlet<'T>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
type: 'T list
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
class
interface System.Collections.IEnumerable
interface System.IComparable
interface System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<'Key,'Value>>
interface System.Collections.Generic.ICollection<System.Collections.Generic.KeyValuePair<'Key,'Value>>
interface System.Collections.Generic.IDictionary<'Key,'Value>
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
member Add : key:'Key * value:'Value -> Map<'Key,'Value>
member ContainsKey : key:'Key -> bool
override Equals : obj -> bool
member Remove : key:'Key -> Map<'Key,'Value>
member TryFind : key:'Key -> 'Value option
member Count : int
member IsEmpty : bool
member Item : key:'Key -> 'Value with get
end

Full name: Microsoft.FSharp.Collections.Map<_,_>
type: Map<'Key,'Value>
val textBox : string -> Formlet<string>

Full name: Blog.textBox

Represents a textbox formlet
val key : string
type: string
val map : Map<string,string>
type: Map<string,string>
val render : Formlet<'a> -> string list

Full name: Blog.render
val keys : string list
type: string list
val evaluate : Map<string,string> -> Formlet<'a> -> 'a

Full name: Blog.evaluate
val state : Map<string,string>
type: Map<string,string>
val op : (Map<string,string> -> 'a)
Multiple items
val unit : 'a -> Formlet<'a>

Full name: Blog.Formlets.unit

Formlet that always returns the given value

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit
val v : 'a
val map : ('a -> 'b) -> Formlet<'a> -> Formlet<'b>

Full name: Blog.Formlets.map

The map operation applies 'f' to the result
val merge : Formlet<'a> -> Formlet<'b> -> Formlet<'a * 'b>

Full name: Blog.Formlets.merge

Combine two formlets and pair their results
val keys1 : string list
type: string list
val op1 : (Map<string,string> -> 'a)
val keys2 : string list
type: string list
val op2 : (Map<string,string> -> 'b)
type FormletBuilder =
class
new : unit -> FormletBuilder
member Merge : form1:Formlet<'e> * form2:Formlet<'f> -> Formlet<'e * 'f>
member Return : v:'b -> Formlet<'b>
member ReturnFrom : form:'a -> 'a
member Select : form:Formlet<'c> * f:('c -> 'd) -> Formlet<'d>
end

Full name: Blog.FormletBuilder
val x : FormletBuilder
member FormletBuilder.Merge : form1:Formlet<'e> * form2:Formlet<'f> -> Formlet<'e * 'f>

Full name: Blog.FormletBuilder.Merge
val form1 : Formlet<'e>
val form2 : Formlet<'f>
module Formlets

from Blog
member FormletBuilder.Select : form:Formlet<'c> * f:('c -> 'd) -> Formlet<'d>

Full name: Blog.FormletBuilder.Select
val form : Formlet<'c>
val f : ('c -> 'd)
member FormletBuilder.Return : v:'b -> Formlet<'b>

Full name: Blog.FormletBuilder.Return
val v : 'b
val unit : 'a -> Formlet<'a>

Full name: Blog.Formlets.unit

Formlet that always returns the given value
member FormletBuilder.ReturnFrom : form:'a -> 'a

Full name: Blog.FormletBuilder.ReturnFrom
val form : 'a
val form : FormletBuilder

Full name: Blog.form
type F<'T> = | FC of 'T

Full name: Blog.F<_>
type: F<'T>
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit
val a1 : int
type: int
inherits: System.ValueType
val a2 : string
type: string
val a3 : float
type: float
inherits: System.ValueType
type M<'T> = | MM of 'T

Full name: Blog.M<_>
type: M<'a>
union case M.MM: 'T -> M<'T>
type MBuilder =
class
new : unit -> MBuilder
member Bind : M<'b> * f:('b -> 'c) -> 'c
member Return : v:'d -> M<'d>
member ReturnFrom : M<'a> -> M<'a>
end

Full name: Blog.MBuilder
val x : MBuilder
member MBuilder.Return : v:'d -> M<'d>

Full name: Blog.MBuilder.Return
val v : 'd
member MBuilder.Bind : M<'b> * f:('b -> 'c) -> 'c

Full name: Blog.MBuilder.Bind
val f : ('b -> 'c)
member MBuilder.ReturnFrom : M<'a> -> M<'a>

Full name: Blog.MBuilder.ReturnFrom
type FBuilder =
class
new : unit -> FBuilder
member Merge : F<'d> * F<'e> -> F<'d * 'e>
member Return : a:'a -> F<'a>
member Select : F<'b> * f:('b -> 'c) -> F<'c>
end

Full name: Blog.FBuilder
val x : FBuilder
member FBuilder.Merge : F<'d> * F<'e> -> F<'d * 'e>

Full name: Blog.FBuilder.Merge
val a : 'd
val b : 'e
member FBuilder.Select : F<'b> * f:('b -> 'c) -> F<'c>

Full name: Blog.FBuilder.Select
val a : 'b
member FBuilder.Return : a:'a -> F<'a>

Full name: Blog.FBuilder.Return
val m : MBuilder

Full name: Blog.m
val a : FBuilder

Full name: Blog.a
val f : int -> M<int>

Full name: Blog.f
val g : int -> F<int>

Full name: Blog.g
val b : int
type: int
inherits: System.ValueType
val userInfo : Formlet<string>

Full name: Blog.userInfo
val name : string
type: string
val surname : string
type: string
val combined : string
type: string
val message : string
type: string

Published: August 21, 2012 14:23
Tags: Research | Haskell | F# language

Share:

• RE: Applicative functors: definition and syntax by Sjoerd Visscher (8/21/2012 4:14:32 PM)

I don't see how the Monoidal definition makes your syntax easier to implement. I.e. your example translates simply to:

pure (\name surname -> "Your name is " ++ name ++ " " ++ surname) <*> textBox "name" <*> textBox "surname"

• RE: Applicative functors: definition and syntax by Tomas (8/21/2012 6:28:15 PM)

@Sjoerd: Well, the definitions are equivalent, so the difference is mainly intuitive. However, if you use the Monoidal definition then you can take all the computations and merge them into a valid expression (e = textBox "name" ** textBox "surname") and then use that to compose the expression "map (...) e".

If you use the Applicative definition, then you cannot simply compose all the arguments in an AST, because something like '<*> textBox "name" <*> textBox "surname"' is not a valid expression. You have to start by building the function and then adding the arguments (which is, inded, quite simple and perfectly fine, but it means you have to process the syntax in a backward direction).

• RE: Applicative functors: definition and syntax by Quentin Moser (8/21/2012 7:12:13 PM)

About the "mzip :: f a -> f b -> f (a,b)" function used in Haskell monad comprehensions, it's important to note that this function is only useful because it's expected to be <b>different</b> from the one you'd get by using the applicative/monad instance for f ("\a b -> (,) <*> a <*> b").

In this sense it's probably wrong to call it the "same" merge operation

• RE: Applicative functors: definition and syntax by Tomas (8/21/2012 10:34:04 PM)

@Quentin: Yes, that's a good point - the 'mzip' operation for monad comprehensions should be different than the one you can get from monad for free (which makes it an interesting extension!) Although, I think that 'mzip' should be commutative (and then you can get it for free only for commutative monads).

You can say that monad comprehensions need two different monoidal functors (but one is actually a monad). I briefly talk about that in Section 2.5 the Monad.Reader article referenced above. The same is the case for a monadic pattern matching (http://www.cl.cam.ac.uk/~tp322/papers/docase.html) which also uses 'mzip'.

I agree that calling it the same operation may be confusing, but it has the same laws and the same categorical interpretation, so I think it is correct - the trick is that sometimes you can use two of them in a single computation.