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

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

Discuss on twitter, .
Send corrections via GitHub pull requests.