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) = 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.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)> =
    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

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

Full name: TryJoinads.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: TryJoinads.render
val keys : string list
  type: string list
val evaluate : Map<string,string> -> Formlet<'a> -> 'a

Full name: TryJoinads.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: TryJoinads.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:

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

Full name: TryJoinads.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 =
    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>

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

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

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

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

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

Full name: TryJoinads.Formlets.unit

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

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

Full name: TryJoinads.form
val userInfo : Formlet<string>

Full name: TryJoinads.userInfo
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>

Full name: TryJoinads.inputs
  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>

Full name: TryJoinads.ApplicativeTranslation.userInfo
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

Full name: TryJoinads.f
val shouldEqual : 'a -> 'b -> 'c

Full name: TryJoinads.shouldEqual
val a : 'a
val b : 'b
val failwith : string -> 'T

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

Full name: TryJoinads.identity

 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

Full name: TryJoinads.associativity

 The associativity law of monoidal functors
 (The translation of 'f2' and 'f3' is the same.)
val g1 : Formlet<'a>
val g2 : Formlet<'b>
val g3 : Formlet<'c>
val f1 : Formlet<('a * 'b) * 'c>
val c : 'c
val f2 : Formlet<('a * 'b) * 'c>
val f3 : Formlet<('a * 'b) * 'c>