# 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.

### Idiom brackets in Haskell

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

- [1] Applicative Programming with Effects - C. McBride and R. Paterson
- [2] Idiom brackets (She's effectful) - C. McBride
- [3] Applicative functors - Edward Z. Yang
- [4] The essence of form abstraction - E. Cooper, S. Lindley, P. Wadler, and J. Yallop
- [5] Syntax Matters: Writing abstract computations in F# - T. Petricek and D. Syme
- [6] Beyond the Monad fashion (I.): Writing idioms in LINQ - T. Petricek
- [7] Fun with parallel monad comprehensions (The Monad.Reader) - T. Petricek
- [8] TryJoinads - Applicative computations - T. Petricek
- [9] Comonadic Notions of Computation - T. Uustalu and V. Vene

Full name: Blog.f

An applicative functor structure

An applicative functor structure

type: int

inherits: System.ValueType

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

type: string

val string : 'T -> string

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

--------------------

type string = System.String

Full name: Microsoft.FSharp.Core.string

type: string

type: float

inherits: System.ValueType

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

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

Full name: Blog.F<_>

type: F<'a>

Full name: Blog.a1

type: F<int>

Full name: Blog.a2

type: F<string>

Full name: Blog.a3

type: F<float>

Full name: Blog.c1

type: F<int>

Full name: Blog.c2

type: F<string>

Full name: Blog.c3

type: F<float>

Full name: Blog.pure

type: F<('T1 -> 'T2)>

type: F<'T1>

Full name: Blog.map

Full name: Blog.Formlet<_>

Full name: Microsoft.FSharp.Collections.list<_>

type: 'T list

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>

Full name: Blog.textBox

Represents a textbox formlet

Represents a textbox formlet

type: string

type: Map<string,string>

Full name: Blog.render

type: string list

Full name: Blog.evaluate

type: Map<string,string>

val unit : 'a -> Formlet<'a>

Full name: Blog.Formlets.unit

Formlet that always returns the given value

Formlet that always returns the given value

--------------------

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

type: unit

Full name: Blog.Formlets.map

The map operation applies 'f' to the result

The map operation applies 'f' to the result

Full name: Blog.Formlets.merge

Combine two formlets and pair their results

Combine two formlets and pair their results

type: string list

type: string list

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

Full name: Blog.FormletBuilder.Merge

from Blog

Full name: Blog.FormletBuilder.Select

Full name: Blog.FormletBuilder.Return

Full name: Blog.Formlets.unit

Formlet that always returns the given value

Formlet that always returns the given value

Full name: Blog.FormletBuilder.ReturnFrom

Full name: Blog.form

Full name: Blog.F<_>

type: F<'T>

Full name: Microsoft.FSharp.Core.unit

type: unit

type: int

inherits: System.ValueType

type: string

type: float

inherits: System.ValueType

Full name: Blog.M<_>

type: M<'a>

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

Full name: Blog.MBuilder.Return

Full name: Blog.MBuilder.Bind

Full name: Blog.MBuilder.ReturnFrom

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

Full name: Blog.FBuilder.Merge

Full name: Blog.FBuilder.Select

Full name: Blog.FBuilder.Return

Full name: Blog.m

Full name: Blog.a

Full name: Blog.f

Full name: Blog.g

type: int

inherits: System.ValueType

Full name: Blog.userInfo

type: string

type: string

type: string

type: string

**Published:** Tuesday, 21 August 2012, 2:23 PM

**Author:** Tomas Petricek

**Typos:** Send me pull request!

**Tags:** research, haskell, f#