Monoidal computations

In this article, we discuss how to use F# computation expressions to provide syntax for monoidal computations. Formally, a monoid is formed by an associative binary operation and a unit element. In computation expressions, the binary operation is represented by the Combine operation. Importantly, it has a different type and purpose than for monads. The unit element is defined as the Zero member.

Natural numbers with multiplication

The monoidal structure can be defined for a number of computations. Most well known are lists (which are covered in composed computations) and the Maybe data type (which we do not cover in this paper). In this section, we look at a simpler example - natural numbers with multiplication as the binary operation and 1 as the unit element.

The basic computation builder for mul { .. } computation expressions can be defined as follows:

type M = M of int

type MulBuilder() =
  /// Zero element of the monoid
  member x.Zero() = M 1
  /// Binary operation of the monoid
  member x.Combine(M a, M b) = M (a * b)

  /// Used to create elements of the monoid
  member x.Yield(v) = M v
  /// Enables the 'yield!' syntax
  member x.YieldFrom(M v) = M v

  /// Perform all effects immediately
  member x.Delay(f) = f()

let mul = MulBuilder()

Aside from Zero and Combine, we also define Yield, which wraps a number into the M type that represents the monoid and YieldFrom that is required to enable yield!. We also define Delay, because it is required by the translation - in the current implementation, it just runs the given function immediately to perform the effects (but we get back to this topic in the next section).

Using the computation builder defined above, we can write a function factorial that multiplies numbers from the given number to a provided upper bound (this is a more complete example than the one in the paper):

/// When called with 'factorial 0 x' calculates 'x!'
let rec factorial n bound = 
  mul { yield n
        if n <= bound then 
          yield! factorial (n + 1) bound } 

// Calculate the factorial of 10
factorial 0 10

The translation of the above function looks as follows:

let rec factorial n bound = 
  mul.Delay(fun () ->
    mul.Combine
      ( mul.Yield(n),
        mul.Delay(fun () ->
          if n <= bound then 
            mul.YieldFrom(factorial (n + 1) bound)
          else mul.Zero() )))

Monoid laws

Every monoid is required to obey two laws. The binary operation has to be associative (meaning that a (b c) = (a b) c) and the unit element has to behave as unit (meaning that a 1 = a = 1 a). The laws can be expressed using the computation expression syntax as follows:

/// The associativity monoid law 
let associativity n1 n2 n3 =
  let m1 = m { yield! n1 
               yield! n2
               yield! n3 }
  let m2 = m { yield! m { yield! n1 
                          yield! n2 }
               yield! n3 }

  m1 |> shouldEqual m2

/// The unit monoid laws 
let unit n1 n2 =
  let m1 = m { yield! n1
               if false then yield! n2 }
  let m2 = m { if false then yield! n2
               yield! n1 }
  let m3 = m { yield! n1 }

  m1 |> shouldEqual m3
  m2 |> shouldEqual m3

Delayed monoidal computations

In the previous example, the computation is eager. The mul { .. } computation evaluates all elements that are generated using yield and multiplies all of them. This also means that Delay does not need to actually delay the effects, because they will be evaluated anyway. However, we could use other properties of multiplication - since 0 * x = 0, the Combine member could check if the first argument is 0 and stop evaluating the rest of the computation. When using this alternative, the second argument of Combine needs to be a delayed computation - the following example uses the type D = 1 -> M:

type LazyMulBuilder() =
  /// Zero element of the monoid
  member x.Zero() = M 1
  /// Binary operation of the monoid
  member x.Combine(M a, f) = 
    if a = 0 then M 0 else 
      let (M b) = f() in M (a * b)

  /// Used to create elements of the monoid
  member x.Yield(v) = M v
  /// Enables the 'yield!' syntax
  member x.YieldFrom(M v) = M v

  /// Return the delayed computation
  member x.Delay(f) = f
  /// Evaluate a delayed computation
  member x.Run(f) = f()

let lmul = LazyMulBuilder()

The lazy lmul computation builder can be used to write the following code that multiplies an infinite sequence of randomly generated numbers in range 0 .. 10. The generator will eventually return 0 and then the computaiton stops:

/// Random number generator
let random = System.Random()

/// Multiply infinite sequence of random numbers
let rec inf () =
  lmul { yield random.Next(10)
         yield! inf () }

If we wrote the same function using the mul computation builder described earlier, than the computation would loop forever and would never terminate.

Control flow constructs

Similarly to monadic computations, it is possible to extend a monoidal computation expression with standard F# control flow constructs including loops (for and while) and exception handlers. The following code sample extends the LazyMulBuilder:

type LazyMulBuilder with
  /// The exception handling uses the delayed type directly
  member m.TryWith(f, handler) = 
    try f() 
    with e -> handler e

  /// The finalizer is defined similarly (but the body of the 
  /// finalizer cannot be monoidal - just a `unit -> unit` function)
  member m.TryFinally(f, finalizer) = 
    try f()
    finally finalizer()

  /// The 'while' loop evaluates the condition and then either ends
  /// (returning 'Zero'), or evaluates body once and then runs recursively
  member m.While(cond, body) = 
    if not (cond()) then m.Zero()
    else m.Combine(m.Run(body), m.Delay(fun () -> m.While(cond, body)))

  /// The 'for' loop can be defined using 'While' and 'Using'
  member m.For(xs:seq<'T>, f) = 
    let en = xs.GetEnumerator()
    m.TryFinally
      ( m.Delay(fun () ->
          m.While( (fun () -> en.MoveNext()), m.Delay(fun () -> 
            f en.Current) )),
        fun () -> en.Dispose() )

The definition of TryWith and TryFinally is the same as for monadic containers in the previous section. As the delayed computation type is a function unit -> M<'T>, the handling does not need to inspect the structure of the computation and can be implemented by wrapping the function call with a handler. For monoidal computations that have a built-in notion of delayed computations (such as lazy lists), the operations have to be implemented differently.

Unlike for monads, we do not provide the Using member (which corresponds to binding and so it is not appropriate). This means that the For member needs to use TryFinally explicitly (unlike in the previous section). However, otherwise the definition of While and For also follows the one dicussed for monads. The new definitions allow us to write the following:

/// Calculate the factorial of a number
let factorial x =
  lmul { for num in 1 .. x do 
           yield num }
type M = | M of int

Full name: TryJoinads.M
  type: M
union case M.M: int -> M
Multiple items
val int : 'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
  type: int<'Measure>
  inherits: System.ValueType


--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int
  type: int
  inherits: System.ValueType
type MulBuilder =
  class
    new : unit -> MulBuilder
    member Combine : M * M -> M
    member Delay : f:(unit -> 'a) -> 'a
    member Yield : v:int -> M
    member YieldFrom : M -> M
    member Zero : unit -> M
  end

Full name: TryJoinads.MulBuilder
val x : MulBuilder
member MulBuilder.Zero : unit -> M

Full name: TryJoinads.MulBuilder.Zero


 Zero element of the monoid
member MulBuilder.Combine : M * M -> M

Full name: TryJoinads.MulBuilder.Combine


 Binary operation of the monoid
val a : int
  type: int
  inherits: System.ValueType
val b : int
  type: int
  inherits: System.ValueType
member MulBuilder.Yield : v:int -> M

Full name: TryJoinads.MulBuilder.Yield


 Used to create elements of the monoid
val v : int
  type: int
  inherits: System.ValueType
member MulBuilder.YieldFrom : M -> M

Full name: TryJoinads.MulBuilder.YieldFrom


 Enables the 'yield!' syntax
member MulBuilder.Delay : f:(unit -> 'a) -> 'a

Full name: TryJoinads.MulBuilder.Delay


 Perform all effects immediately
val f : (unit -> 'a)
val mul : MulBuilder

Full name: TryJoinads.mul
val factorial : int -> int -> M

Full name: TryJoinads.factorial


 When called with 'factorial 0 x' calculates 'x!'
val n : int
  type: int
  inherits: System.ValueType
val bound : int
  type: int
  inherits: System.ValueType
val factorial : int -> int -> M

Full name: TryJoinads.MulTranslation.factorial
member MulBuilder.Delay : f:(unit -> 'a) -> 'a


 Perform all effects immediately
member MulBuilder.Combine : M * M -> M


 Binary operation of the monoid
member MulBuilder.Yield : v:int -> M


 Used to create elements of the monoid
member MulBuilder.YieldFrom : M -> M


 Enables the 'yield!' syntax
member MulBuilder.Zero : unit -> M


 Zero element of the monoid
val m : MulBuilder

Full name: TryJoinads.m
val shouldEqual : 'a -> 'a -> unit (requires equality)

Full name: TryJoinads.shouldEqual
val a : 'a (requires equality)
val b : 'a (requires equality)
val not : bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val associativity : M -> M -> M -> unit

Full name: TryJoinads.associativity


 The associativity monoid law
val n1 : M
  type: M
val n2 : M
  type: M
val n3 : M
  type: M
val m1 : M
  type: M
val m2 : M
  type: M
Multiple items
val unit : M -> M -> unit

Full name: TryJoinads.unit


 The unit monoid laws


--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
  type: unit
val m3 : M
  type: M
type LazyMulBuilder =
  class
    new : unit -> LazyMulBuilder
    member Combine : M * f:(unit -> M) -> M
    member Delay : f:'b -> 'b
    member For : xs:seq<'T> * f:('T -> M) -> M
    member Run : f:(unit -> 'a) -> 'a
    member TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a
    member TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a
    member While : cond:(unit -> bool) * body:(unit -> M) -> M
    member Yield : v:int -> M
    member YieldFrom : M -> M
    member Zero : unit -> M
  end

Full name: TryJoinads.LazyMulBuilder
val x : LazyMulBuilder
member LazyMulBuilder.Zero : unit -> M

Full name: TryJoinads.LazyMulBuilder.Zero


 Zero element of the monoid
member LazyMulBuilder.Combine : M * f:(unit -> M) -> M

Full name: TryJoinads.LazyMulBuilder.Combine


 Binary operation of the monoid
val f : (unit -> M)
member LazyMulBuilder.Yield : v:int -> M

Full name: TryJoinads.LazyMulBuilder.Yield


 Used to create elements of the monoid
member LazyMulBuilder.YieldFrom : M -> M

Full name: TryJoinads.LazyMulBuilder.YieldFrom


 Enables the 'yield!' syntax
member LazyMulBuilder.Delay : f:'b -> 'b

Full name: TryJoinads.LazyMulBuilder.Delay


 Return the delayed computation
val f : 'b
member LazyMulBuilder.Run : f:(unit -> 'a) -> 'a

Full name: TryJoinads.LazyMulBuilder.Run


 Evaluate a delayed computation
val lmul : LazyMulBuilder

Full name: TryJoinads.lmul
val random : System.Random

Full name: TryJoinads.random


 Random number generator
namespace System
type Random =
  class
    new : unit -> System.Random
    new : int -> System.Random
    member Next : unit -> int
    member Next : int -> int
    member Next : int * int -> int
    member NextBytes : System.Byte [] -> unit
    member NextDouble : unit -> float
  end

Full name: System.Random
val inf : unit -> M

Full name: TryJoinads.inf


 Multiply infinite sequence of random numbers
System.Random.Next() : int
System.Random.Next(maxValue: int) : int
System.Random.Next(minValue: int, maxValue: int) : int
val m : LazyMulBuilder
member LazyMulBuilder.TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a

Full name: TryJoinads.LazyMulBuilder.TryWith


 The exception handling uses the delayed type directly
val handler : (exn -> 'a)
Multiple items
val e : exn
  type: exn


--------------------
val e : exn
  type: exn
val e : exn
  type: exn
member LazyMulBuilder.TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a

Full name: TryJoinads.LazyMulBuilder.TryFinally


 The finalizer is defined similarly (but the body of the
 finalizer cannot be monoidal - just a `unit -> unit` function)
val finalizer : (unit -> unit)
member LazyMulBuilder.While : cond:(unit -> bool) * body:(unit -> M) -> M

Full name: TryJoinads.LazyMulBuilder.While


 The 'while' loop evaluates the condition and then either ends
 (returning 'Zero'), or evaluates body once and then runs recursively
val cond : (unit -> bool)
val body : (unit -> M)
member LazyMulBuilder.Zero : unit -> M


 Zero element of the monoid
member LazyMulBuilder.Combine : M * f:(unit -> M) -> M


 Binary operation of the monoid
member LazyMulBuilder.Run : f:(unit -> 'a) -> 'a


 Evaluate a delayed computation
member LazyMulBuilder.Delay : f:'b -> 'b


 Return the delayed computation
member LazyMulBuilder.While : cond:(unit -> bool) * body:(unit -> M) -> M


 The 'while' loop evaluates the condition and then either ends
 (returning 'Zero'), or evaluates body once and then runs recursively
member LazyMulBuilder.For : xs:seq<'T> * f:('T -> M) -> M

Full name: TryJoinads.LazyMulBuilder.For


 The 'for' loop can be defined using 'While' and 'Using'
val xs : seq<'T>
  type: seq<'T>
  inherits: System.Collections.IEnumerable
Multiple items
val seq : seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
  type: seq<'T>
  inherits: System.Collections.IEnumerable
val f : ('T -> M)
val en : System.Collections.Generic.IEnumerator<'T>
  type: System.Collections.Generic.IEnumerator<'T>
  inherits: System.IDisposable
  inherits: System.Collections.IEnumerator
System.Collections.Generic.IEnumerable.GetEnumerator() : System.Collections.Generic.IEnumerator<'T>
member LazyMulBuilder.TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a


 The finalizer is defined similarly (but the body of the
 finalizer cannot be monoidal - just a `unit -> unit` function)
System.Collections.IEnumerator.MoveNext() : bool
property System.Collections.Generic.IEnumerator.Current: 'T
System.IDisposable.Dispose() : unit
val factorial : int -> M

Full name: TryJoinads.AnotherFactorial.factorial


 Calculate the factorial of a number
val x : int
  type: int
  inherits: System.ValueType
val num : int
  type: int
  inherits: System.ValueType