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