# Applicative computations

Applicative functors (also called idioms) are a weaker abstraction than monads. This means that certain computations that cannot implement the full monadic structure can still implement the applicative interface. Perhaps the best known example is the formlet abstraction that is used to represent server-side HTML forms.

In key difference between applicative functors and monadic computations is that, given an applicative computation, we can statically determine the basic operations that are used to compose it - for monads, this is not possible, because the structure may depend on the values provided at runtime.

In this section, we look at a research extension to F# computation expressions that makes it possible to write applicative computations. Note that this is not a part of standard F# 2.0 (and it is not planned for any future version of F#). However, the implementation is available for the open-source release of F# and is also available in the Interactive F# console on this site.

## Applicative formlets

Implementing a complete formlet library is beyond the scope of this page, but we show a simple formlet-like computation. The computation `Formlet<'T>` is defined as follows:

```type Formlet<'T> =
F of list<string> * (Map<string, string> -> 'T)

/// Represents a textbox formlet
let textBox key =
F([key], fun map -> map.[key])

// Primitive operations for working with formlets
let render (F(keys, _)) = keys
let evaluate state (F(_, op)) = op state```

The second component `Map<string, string> -> 'T` is a function that calculates the value of a form, when provided with a map that assigns values to individual keys (form elements). The first component `list<string>` is a list of keys that need to be provided in order to evaluate the second component. In a real implementation, the first element would represent the HTML to be rendered when the page is accessed for the first time - in this phase, we do not have values for the keys yet and so it is not possible to run the processing function, but we need to obtain the form - that is, the static structure of the computation.

The `textBox` function constructs a primitive formlet - the formlet consists of a list with just the name of the textbox and a function that returns the value associated with the text box.

The following operations define the applicative functor structure for our simple formlet:

```module Formlets =
/// Formlet that always returns the given value
let unit v = F([], fun _ -> v)

/// The map operation applies 'f' to the result
let map f (F(keys, op)) =
F(keys, fun state -> f (op state))

/// Combine two formlets and pair their results
let merge (F(keys1, op1)) (F(keys2, op2)) =
F(keys1 @ keys2, fun state -> (op1 state, op2 state))```

The `unit` operation returns a formlet that does not require any form elements and always returns the provided value (when evaluated using the second component). The `map` operation does not affect the structure of the form - it just applies the given function to the result that is calculated by the original formlet.

Finally, the `merge` operation generates a new formlet that consists of all form elments of the two given formlets (this is done by concatenating the lists of keys). When executed, it runs both underlying formlets and returns a tuple that contains both of the results. The tuple is not usually returned as the final result, but it can be easily transformed further using `map`.

## Applicative computation builder

A basic computaiton builder for working with applicative functors consists of the three operations defined in the previous section:

```type FormletBuilder() =
member x.Merge(form1, form2) = Formlets.merge form1 form2
member x.Select(form, f) = Formlets.map f form
member x.Return(v) = Formlets.unit v
member x.ReturnFrom(form) = form

let form = FormletBuilder()```

The `map` operation is provided as a `Select` member - this matches with the usual .NET framework naming guidelines where the name `Select` is used for the map operation in LINQ. The rest of the definition is straightforward. We also added `ReturnFrom` in order to allow the `return!` syntax, although it is less useful than when working with monads.

The following example creates a simple formlet that can be used for entering user information. When the data is available, the formlet returns a message "Your name is X Y" as a single string:

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

// Select and run the following to get the required form keys
userInfo |> render
// Select and run the following to evaluate the formlet
let inputs = Map.ofSeq ["name", "Tomas"; "surname", "Petricek"]
userInfo |> evaluate inputs```

The structure of the computations that can be written is quite limited - the computation block `form { .. }` has to start with a binding of a form `let! .. and .. and ..` (with an arbitrary fixed number of `and` constructs). This can be followed by any expression that always ends with `return` (for example, `return!` or other computation expressions are not be allowed). The only other form that is allowed is `f { return! e }`.

The translation of the above example looks as follows:

```let userInfo =
form.Select
( form.Merge(textBox "name", textBox "surname"),
fun (name, surname) ->
let combined = name + " " + surname
let message = "Your name is " + combined
message )```

The code is translated quite differently to monadic or monoidal computations. All bindings that are performed using `let! .. and` block are combined using `Merge` and the rest of the computation is translated to the application of `Select`. The `return` keyword is removed (and is only used to keep the computations syntactically uniform).

These syntactic limitations explain why we do not extend the computation builder with members that define other standard F# control flow constructs. These can be used in their standard form (i.e. after the initial binding and before the last `return`), but in this form, they do not have any non-standard meaning and they are pushed into the function that is used as an argument to `Select`.

## Applicative functor laws

Formally, formlets can be defined in two ways. The approach that is used in F# computation expression uses the (lax) monoidal functor definition (as opposed to the applicative definition emphasized by Paterson and McBride). The structure requires a number of laws that can be expressed using the computation expression syntax as follows:

```/// The left and right identity laws of monoidal functors
let identity g =
let f1 = f { let! a = g
and b = f { return () }
return a }
let f2 = f { let! a = f { return () }
and b = g
return b }
let f3 = f { return! g }
f1 |> shouldEqual f3
f2 |> shouldEqual f3

/// The associativity law of monoidal functors
/// (The translation of 'f2' and 'f3' is the same.)
let associativity g1 g2 g3 =
let f1 = f { let! a, b = f { let! a = g1
and b = g2
return a, b }
and c = g3
return (a, b), c }
let f2 = f { let! a = g1
and b, c = f { let! b = g2
and c = g3
return b, c }
return (a, b), c }
let f3 = f { let! a = g1
and b = g2
and c = g3
return (a, b), c }
f1 |> shouldEqual f3
f2 |> shouldEqual f3```
union case Formlet.F: string list * (Map<string,string> -> 'T) -> Formlet<'T>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
type: 'T list
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
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>

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

val keys : string list
type: string list
val evaluate : Map<string,string> -> Formlet<'a> -> 'a

val state : Map<string,string>
type: Map<string,string>
val op : (Map<string,string> -> 'a)
Multiple items
val unit : 'a -> Formlet<'a>

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>

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

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

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

val form1 : Formlet<'e>
val form2 : Formlet<'f>
module Formlets

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

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

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

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

val form : 'a
val form : FormletBuilder

val userInfo : Formlet<string>

val name : string
type: string
val surname : string
type: string
val combined : string
type: string
val message : string
type: string
val inputs : Map<string,string>

type: Map<string,string>
val ofSeq : seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.ofSeq
val userInfo : Formlet<string>

member FormletBuilder.Select : form:Formlet<'c> * f:('c -> 'd) -> Formlet<'d>
member FormletBuilder.Merge : form1:Formlet<'e> * form2:Formlet<'f> -> Formlet<'e * 'f>
val f : FormletBuilder

val shouldEqual : 'a -> 'b -> 'c

val a : 'a
val b : 'b
val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val identity : Formlet<'a> -> 'b

The left and right identity laws of monoidal functors
val g : Formlet<'a>
val f1 : Formlet<'a>
val b : unit
type: unit
val f2 : Formlet<'a>
val a : unit
type: unit
val b : 'a
val f3 : Formlet<'a>
val associativity : Formlet<'a> -> Formlet<'b> -> Formlet<'c> -> 'd