DEV Community

Cover image for F# applicative computation expressions
Romain Deneau
Romain Deneau

Posted on • Edited on

F# applicative computation expressions

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.

Table of contents

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>
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

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"]
Enter fullscreen mode Exit fullscreen mode

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 })
}                                           ; )
Enter fullscreen mode Exit fullscreen mode

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 on Validation<_, _> tuples, distinguishing between Ok (all elements are valid) and Error (any element is invalid). Err is used in bind2 and bind3.
  • bind2 and bind3 are the base helpers used to implement the builder methods that deal with two and three Validation<_, _> 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)
Enter fullscreen mode Exit fullscreen mode

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))
    )
Enter fullscreen mode Exit fullscreen mode

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)
    )
Enter fullscreen mode Exit fullscreen mode

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)
    )
Enter fullscreen mode Exit fullscreen mode

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)
    )
Enter fullscreen mode Exit fullscreen mode

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)
    )
Enter fullscreen mode Exit fullscreen mode

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 })
                                            ;          )
                                            ;      )
                                            ;  )
Enter fullscreen mode Exit fullscreen mode

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 a Validation<'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 })
Enter fullscreen mode Exit fullscreen mode

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) ]
Enter fullscreen mode Exit fullscreen mode

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)