This fifth article in the series dedicated to F# computation expressions is a guide to writing F# computation expressions (CE) with applicative behavior.
An applicative CE offers the widest variety of method combinations for the CE builder. We'll examine in detail when these are useful, based on compiler error messages and desugared versions of the expressions used in these tests.
Introduction
Applicative computation expressions are characterized by the use of the and!
keyword introduced in F# 5.
Builder method signatures
An applicative CE builder typically defines the following methods:
// Method | Signature | Comment
MergeSources : mx: M<X> * my: M<Y> -> M<X * Y> ; (* ≡ *) map2 (fun x y -> x, y) mx my
BindReturn : m: M<T> * f: (T -> U) -> M<U> ; (* ≡ *) map f m
// Additional methods for performance optimization
// - MergeSourcesN, N >= 3:
MergeSources3: mx: M<X> * my: M<Y> * mz: M<Z> -> M<X * Y * Z>
// - BindNReturn, N >= 2:
Bind2Return : mx: M<X> * my: M<Y> * f: (X * Y -> U) -> M<U> ; (* ≡ *) map2 f mx my
// - BindN, N >= 2:
Bind2 : mx: M<X> * my: M<Y> * f: (X * Y -> M<U>) -> M<U>
Bind3 : mx: M<X> * my: M<Y> * mz: M<Z> * f: (X * Y * Z -> M<U>) -> M<U>
Applicative CE example: validation
The purpose is to accumulate errors given by a group of results.
Base implementation
The implementation relies on the type Validation<'t, 'e>
that is an alias of Result<'t, 'e list>
. The Error
case holds the list of accumulated errors.
The builder implements two essential methods to achieve applicative behavior: BindReturn
and MergeSources
.
type Validation<'t, 'e> = Result<'t, 'e list>
type ValidationBuilder() =
member _.BindReturn(x: Validation<'t, 'e>, f: 't -> 'u) =
Result.map f x
member _.MergeSources(x: Validation<'t, 'e>, y: Validation<'u, 'e>) =
match (x, y) with
| Ok v1, Ok v2 -> Ok(v1, v2) // Merge both values in a pair
| Error e1, Error e2 -> Error(e1 @ e2) // Merge errors into a single list
| Error e, _ | _, Error e -> Error e // Short-circuit on single error source
let validation = ValidationBuilder()
Use case: validate a customer
Let's create a smart constructor to get a valid customer: whose name is not null or empty, and whose height in centimeters is strictly positive. If both the name and height are invalid, we want to know both errors at once. This makes the use case ideal for the validation {}
computation expression with a let! ... and! ...
expression.
type [<Measure>] cm
type Customer = { Name: string; Height: int<cm> }
let validateHeight height =
if height <= 0<cm>
then Error ["Height must be positive"]
else Ok height
let validateName name =
if System.String.IsNullOrWhiteSpace name
then Error ["Name can't be empty"]
else Ok name
module Customer =
let tryCreate name height : Validation<Customer, string> =
validation {
let! validName = validateName name
and! validHeight = validateHeight height
return { Name = validName; Height = validHeight }
}
let c1 = Customer.tryCreate "Bob" 180<cm> // Ok { Name = "Bob"; Height = 180 }
let c2 = Customer.tryCreate "Bob" 0<cm> // Error ["Height must be positive"]
let c3 = Customer.tryCreate "" 0<cm> // Error ["Name can't be empty"; "Height must be positive"]
Desugaring:
validation { ; validation.BindReturn(
; validation.MergeSources(
let! name = validateName "Bob" ; validateName "Bob",
and! height = validateHeight 0<cm> ; validateHeight 0<cm>
; ),
return { Name = name; Height = height } ; (fun (name, height) -> { Name = name; Height = height })
} ; )
Other method combinations
Let's explore different method combinations to see what the compiler requires and how the expressions are desugared.
For convenience, let's start by defining some helpers:
- The
Err
active pattern simplifies pattern matching onValidation<_, _>
tuples, distinguishing betweenOk
(all elements are valid) andError
(any element is invalid).Err
is used inbind2
andbind3
. -
bind2
andbind3
are the base helpers used to implement the builder methods that deal with two and threeValidation<_, _>
parameters respectively.
let (|Err|) (vx: Validation<'x, 'e>) =
match vx with
| Ok _ -> []
| Error errors -> errors
module Validation =
let ok (x: 'x) : Validation<'x, 'e> = Ok x
let error (e: 'e) : Validation<'x, 'e> = Error [ e ]
let errors (e: 'e list) : Validation<'x, 'e> = Error e
let bind2 (vx: Validation<'x, 'e>) (vy: Validation<'y, 'e>) (f: 'x -> 'y -> Validation<'u, 'e>) : Validation<'u, 'e> =
match vx, vy with
| Ok x, Ok y -> f x y
| Err ex, Err ey -> Error(ex @ ey)
let bind3 (vx: Validation<'x, 'e>) (vy: Validation<'y, 'e>) (vz: Validation<'z, 'e>) (f: 'x -> 'y -> 'z -> Validation<'u, 'e>) : Validation<'u, 'e> =
match vx, vy, vz with
| Ok x, Ok y, Ok z -> f x y z
| Err ex, Err ey, Err ez -> Error(ex @ ey @ ez)
Two-element expression
To handle an expression like let! ... and! ...
, the combination of Bind2
and Return
is valid for the compiler:
type ValidationBuilder() =
member _.Bind2(vx: Validation<'x, 'e>, vy: Validation<'y, 'e>, f: 'x * 'y -> Validation<'u, 'e>) : Validation<'u, 'e> =
Validation.bind2 vx vy (fun x y -> f (x, y))
member _.Return(x: 't) =
Validation.ok x
let test =
validation {
let! x = Validation.ok 1
and! y = Validation.ok 10
return x + y
}
let test_desugared =
validation.Bind2(
Validation.ok 1,
Validation.ok 10,
(fun (x, y) -> validation.Return(x + y))
)
Examining the desugared version, we see that this method combination is not more efficient than the classic BindReturn
and MergeSources
approach. Let's try using only Bind2Return
!
type ValidationBuilder() =
member _.Bind2Return(vx: Validation<'x, 'e>, vy: Validation<'y, 'e>, f: 'x * 'y -> 'u) : Validation<'u, 'e> =
Validation.bind2 vx vy (fun x y -> Validation.ok (f (x, y)))
let test =
validation {
let! x = Validation.ok 1
and! y = Validation.ok 10
return x + y
}
let test_desugared =
validation.Bind2Return(
Validation.ok 1,
Validation.ok 10,
(fun (x, y) -> x + y)
)
In this case, Bind2Return
can be the only method needed by the compiler. The desugared result confirms that it's the only method call, leading to a more efficient builder implementation for handling let! ... and! ...
expressions.
Three-element expression
The regular BindReturn
and MergeSources
method combination can handle an expression like let! ... and! ... and! ...
:
type ValidationBuilder() =
member _.BindReturn(x: Validation<'t, 'e>, f: 't -> 'u) : Validation<'u, 'e> =
Result.map f x
member _.MergeSources(vx: Validation<'x, 'e>, vy: Validation<'y, 'e>) : Validation<'x * 'y, 'e> =
Validation.bind2 vx vy (fun x y -> Validation.ok (x, y))
let test =
validation {
let! x = Validation.ok 1
and! y = Validation.ok 2
and! z = Validation.ok 3
return (z - x) * y
}
let test_desugared =
validation.BindReturn(
validation.MergeSources(
Validation.ok 1,
validation.MergeSources(
Validation.ok 2,
Validation.ok 3
)
),
(fun (x, (y, z)) -> (z - x) * y)
)
The desugared version shows that two MergeSources
calls are needed to assemble the three values x
, y
and z
required for the final calculation (z - x) * y
. If the MergeSources3
method is provided, the compiler can replace this double call to MergeSources
with a single call to MergeSources3
, simplifying the parameter deconstruction to obtain x
, y
and z
—from (x, (y, z))
to (x, y, z)
:
type ValidationBuilder() =
member _.BindReturn(x: Validation<'t, 'e>, f: 't -> 'u) : Validation<'u, 'e> =
Result.map f x
member _.MergeSources(vx: Validation<'x, 'e>, vy: Validation<'y, 'e>) : Validation<'x * 'y, 'e> =
Validation.bind2 vx vy (fun x y -> Validation.ok (x, y))
member _.MergeSources3(vx: Validation<'x, 'e>, vy: Validation<'y, 'e>, vz: Validation<'z, 'e>) : Validation<'x * 'y * 'z, 'e> =
Validation.bind3 vx vy vz (fun x y z -> Validation.ok (x, y, z))
let test =
validation {
let! x = Validation.ok 1
and! y = Validation.ok 2
and! z = Validation.ok 3
return (z - x) * y
}
let test_desugared =
validation.BindReturn(
validation.MergeSources3(
Validation.ok 1,
Validation.ok 2,
Validation.ok 3
),
(fun (x, y, z) -> (z - x) * y)
)
Note that MergeSources
is not used, but is still required for compilation 🤷
Finally, we can verify that the locally optimal builder only needs a single method, Bind3Return
:
type ValidationBuilder() =
member _.Bind3Return(vx: Validation<'x, 'e>, vy: Validation<'y, 'e>, vz: Validation<'z, 'e>, f: 'x * 'y * 'z -> 'u) : Validation<'u, 'e> =
Validation.bind3 vx vy vz (fun x y z -> Validation.ok (f (x, y, z)))
let test =
validation {
let! x = Validation.ok 1
and! y = Validation.ok 2
and! z = Validation.ok 3
return (z - x) * y
}
let test_desugared =
validation.Bind3Return(
Validation.ok 1,
Validation.ok 2,
Validation.ok 3,
(fun (x, y, z) -> (z - x) * y)
)
Method combination conclusion
The regular BindReturn
and MergeSources
method combination can handle all cases, but requires one additional call to MergeSources
per additional input value. You can optimize the number of builder method calls by providing additional builder methods. BindNReturn
methods are the most efficient option. MergeSourcesN
methods are less efficient but more versatile, as they can be combined to handle tuples with more elements.
FsToolkit validation CE
FsToolkit.ErrorHandling provides a similar validation {}
implementation.
The desugaring reveals the definition of additional methods: Delay
, Run
, Source
📍
validation { ; validation.Run(
let! name = validateName "Bob" ; validation.Delay(fun () ->
and! height = validateHeight 0<cm> ; validation.BindReturn(
return { Name = name; Height = height } ; validation.MergeSources(
} ; validation.Source(validateName "Bob"),
; validation.Source(validateHeight 0<cm>)
; ),
; (fun (name, height) -> { Name = name; Height = height })
; )
; )
; )
Source
methods
In FsToolkit's validation {}
, there are a couple of Source
methods defined:
- The main definition is the
id
function. - Another overload is interesting: it converts a
Result<'a, 'e>
into aValidation<'a, 'e>
. Because it's defined as an extension method, it has lower priority for the compiler, which improves type inference. Otherwise, type annotations would be required.
☝️ Note: Source
documentation is scarce. The most valuable information comes from a Stack Overflow question referenced in the FsToolkit source code!
Applicative CE example: async
As of today, we have to use intermediary calls to Async.StartChild
to get the tasks executed in parallel. This feature can be implemented as an applicative behavior behind the let! ... and and! ...
syntax. Let's extend the AsyncBuilder
class to support this feature.
module Async =
let bind2 (tx: Async<'x>) (ty: Async<'y>) (f: 'x -> 'y -> Async<'u>) : Async<'u> =
async {
let! cx = Async.StartChild tx
let! cy = Async.StartChild ty
let! rx = cx
let! ry = cy
return! f rx ry
}
let bind3 (tx: Async<'x>) (ty: Async<'y>) (tz: Async<'z>) (f: 'x -> 'y -> 'z -> Async<'u>) : Async<'u> =
async {
let! cx = Async.StartChild tx
let! cy = Async.StartChild ty
let! cz = Async.StartChild tz
let! rx = cx
let! ry = cy
let! rz = cz
return! f rx ry rz
}
type AsyncBuilder with
member _.Bind2Return(tx: Async<'x>, ty: Async<'y>, f: 'x * 'y -> 'u) : Async<'u> =
Async.bind2 tx ty (fun x y -> async { return f (x, y) })
member _.Bind3Return(tx: Async<'x>, ty: Async<'y>, tz: Async<'z>, f: 'x * 'y * 'z -> 'u) : Async<'u> =
Async.bind3 tx ty tz (fun x y z -> async { return f (x, y, z) })
member _.MergeSources(tx: Async<'x>, ty: Async<'y>) : Async<'x * 'y> =
Async.bind2 tx ty (fun x y -> async { return x, y })
member _.MergeSources3(tx: Async<'x>, ty: Async<'y>, tz: Async<'z>) : Async<'x * 'y * 'z> =
Async.bind3 tx ty tz (fun x y z -> async { return x, y, z })
The calls to Async.StartChild
are done in Async.bind2
. We provide an Async.bind3
to optimize the usage up to three parallel asynchronous tasks.
Let's test this by comparing the execution duration of three tasks run in series versus in parallel:
open System
open Swensen.Unquote
open Xunit
let returnAfter (t: TimeSpan) x =
async {
do! Async.Sleep t
return x
}
type Take =
| LessThan of TimeSpan
| MoreThan of TimeSpan
let should takes task =
let sw = Diagnostics.Stopwatch.StartNew()
let _ = Async.RunSynchronously task
sw.Stop()
let actualTime = sw.Elapsed
test
<@
takes
|> List.forall (
function
| Take.LessThan t -> actualTime < t
| Take.MoreThan t -> actualTime > t
)
@>
[<Fact>]
let ``Should run the tasks in series`` () =
let taskInSeries =
async {
let! x = 1 |> returnAfter (TimeSpan.FromMilliseconds 10)
let! y = 2 |> returnAfter (TimeSpan.FromMilliseconds 15)
let! z = 3 |> returnAfter (TimeSpan.FromMilliseconds 5)
return x + y + z
}
taskInSeries |> should [ Take.MoreThan(TimeSpan.FromMilliseconds 40) ]
[<Fact>]
let ``Should run the 3 tasks in parallel`` () =
let tasksInParallel =
async {
let! x = 1 |> returnAfter (TimeSpan.FromMilliseconds 10)
and! y = 2 |> returnAfter (TimeSpan.FromMilliseconds 15)
and! z = 3 |> returnAfter (TimeSpan.FromMilliseconds 5)
return x + y + z
}
tasksInParallel |> should [ Take.MoreThan(TimeSpan.FromMilliseconds 15); Take.LessThan(TimeSpan.FromMilliseconds 40) ]
Conclusion
Applicative computation expressions in F# enable parallel computation and error accumulation using the and!
syntax introduced in F# 5. By implementing MergeSources
and BindReturn
methods, you can create powerful validation workflows that collect all errors instead of stopping at the first failure, as well as efficient computations that leverage parallelism. This approach is particularly valuable for form validation, configuration parsing, and any scenario where you want to provide comprehensive feedback to users about multiple validation failures simultaneously. While applicative computation expressions are less versatile than monadic ones, they excel in specific scenarios where their unique capabilities make a significant difference.
Top comments (0)